Google OR-Tools: ortools/base/linked_hash

Google OR-Tools: ortools/base/linked_hash_map.h Source File

27#ifndef ORTOOLS_BASE_LINKED_HASH_MAP_H_

28#define ORTOOLS_BASE_LINKED_HASH_MAP_H_

30#include <list>

31#include <tuple>

32#include <type_traits>

33#include <utility>

35#include "absl/container/flat_hash_set.h"

36#include "absl/container/internal/common.h"

39namespace gtl {

47template <typename Key, typename Value,

48 typename KeyHash = typename absl::flat_hash_set<Key>::hasher,

49 typename KeyEq =

50 typename absl::flat_hash_set<Key, KeyHash>::key_equal,

51 typename Alloc = std::allocator<std::pair<const Key, Value>>>

53 using KeyArgImpl = absl::container_internal::KeyArg<

54 absl::container_internal::IsTransparent<KeyEq>::value &&

55 absl::container_internal::IsTransparent<KeyHash>::value>;

60 template <class K>

61 using key_arg = typename KeyArgImpl::template type<K, Key>;

63 public:

68 using value_type = std::pair<const key_type, mapped_type>;

72 private:

73 using ListType = std::list<value_type, Alloc>;

75 template <class Fn>

76 class Wrapped {

77 template <typename K>

78 static const K& ToKey(const K& k) {

79 return k;

80 }

81 static const key_type& ToKey(typename ListType::const_iterator it) {

82 return it->first;

83 }

84 static const key_type& ToKey(typename ListType::iterator it) {

85 return it->first;

86 }

88 Fn fn_;

92 public:

93 using is_transparent = void;

95 Wrapped() = default;

96 explicit Wrapped(Fn fn) : fn_(std::move(fn)) {}

98 template <class... Args>

99 auto operator()(Args&&... args) const

100 -> decltype(this->fn_(ToKey(args)...)) {

101 return fn_(ToKey(args)...);

102 }

103 };

104 using SetType =

105 absl::flat_hash_set<typename ListType::iterator, Wrapped<hasher>,

106 Wrapped<key_equal>, Alloc>;

107

108 class NodeHandle {

109 public:

113

114 constexpr NodeHandle() noexcept = default;

115 NodeHandle(NodeHandle&& nh) noexcept = default;

116 ~NodeHandle() = default;

117 NodeHandle& operator=(NodeHandle&& node) noexcept = default;

118 bool empty() const noexcept { return list_.empty(); }

119 explicit operator bool() const noexcept { return !empty(); }

120 allocator_type get_allocator() const { return list_.get_allocator(); }

121 const key_type& key() const { return list_.front().first; }

122 mapped_type& mapped() { return list_.front().second; }

123 void swap(NodeHandle& nh) noexcept { list_.swap(nh.list_); }

124

125 private:

126 friend linked_hash_map;

127

128 explicit NodeHandle(ListType list) : list_(std::move(list)) {}

129 ListType list_;

130 };

131

132 template <class Iterator, class NodeType>

133 struct InsertReturnType {

134 Iterator position;

135 bool inserted;

136 NodeType node;

137 };

138

139 public:

140 using iterator = typename ListType::iterator;

144 using reference = typename ListType::reference;

146 using size_type = typename ListType::size_type;

147 using pointer = typename std::allocator_traits<allocator_type>::pointer;

149 typename std::allocator_traits<allocator_type>::const_pointer;

152

154

159 alloc),

160 list_(alloc) {}

161

165

168

171

172 template <class InputIt>

180

181 template <class InputIt>

185

186 template <class InputIt>

191

192 template <class InputIt>

196

203

207

211

216

220 CopyFrom(other);

221 }

222

225 other.key_eq(), alloc) {

226 CopyFrom(other);

227 }

228

230 : set_(std::move(other.set_)), list_(std::move(other.list_)) {

231

232

233 other.set_.clear();

234 other.list_.clear();

235 }

236

240 *this = std::move(other);

241 } else {

242 CopyFrom(std::move(other));

243 }

244 }

245

247 if (this == &other) return *this;

248

249 set_ = SetType(other.bucket_count(), other.set_.hash_function(),

251

253 CopyFrom(other);

254 return *this;

255 }

256

258

259 set_ = std::move(other.set_);

260 list_ = std::move(other.list_);

261 other.set_.clear();

262 other.list_.clear();

263 return *this;

264 }

265

268 insert(values.begin(), values.end());

269 return *this;

270 }

271

272

275 bool empty() const { return set_.empty(); }

276

277

278

295

298

299 ABSL_ATTRIBUTE_REINITIALIZES void clear() {

300 set_.clear();

301 list_.clear();

302 }

303

304 void reserve(size_t n) { set_.reserve(n); }

305 size_t capacity() const { return set_.capacity(); }

306 size_t bucket_count() const { return set_.bucket_count(); }

307 float load_factor() const { return set_.load_factor(); }

308

312

313 template <class K = key_type>

315 auto found = set_.find(key);

316 if (found == set_.end()) return 0;

317 auto list_it = *found;

318

319 set_.erase(found);

320 list_.erase(list_it);

321 return 1;

322 }

323

325 auto found = set_.find(position);

326 CHECK(*found == position) << "Inconsistent iterator for set and list, "

327 "or the iterator is invalid.";

328 set_.erase(found);

329 return list_.erase(position);

330 }

331

335

337 while (first != last) first = erase(first);

338 return first;

339 }

340

342 while (first != last) first = erase(first);

343 if (first == end()) return end();

344 return *set_.find(first);

345 }

346

347 template <class K = key_type>

349 auto found = set_.find(key);

350 if (found == set_.end()) return end();

351 return *found;

352 }

353

354 template <class K = key_type>

356 auto found = set_.find(key);

357 if (found == set_.end()) return end();

358 return *found;

359 }

360

361 template <class K = key_type>

365 template <class K = key_type>

366 bool contains(const key_arg<K>& key) const {

367 return set_.contains(key);

368 }

369

370 template <class K = key_type>

372 auto it = find(key);

373 if (ABSL_PREDICT_FALSE(it == end())) {

374 LOG(FATAL) << "linked_hash_map::at failed bounds check";

375 }

376 return it->second;

377 }

378

379 template <class K = key_type>

383

384 template <class K = key_type>

385 std::pair<iterator, iterator> equal_range(const key_arg<K>& key) {

386 auto iter = set_.find(key);

387 if (iter == set_.end()) return {end(), end()};

388 return {*iter, std::next(*iter)};

389 }

390

391 template <class K = key_type>

392 std::pair<const_iterator, const_iterator> equal_range(

393 const key_arg<K>& key) const {

394 auto iter = set_.find(key);

395 if (iter == set_.end()) return {end(), end()};

396 return {*iter, std::next(*iter)};

397 }

398

399 template <class K = key_type>

401 return LazyEmplaceInternal(key).first->second;

402 }

403

404 template <class K = key_type, K* = nullptr>

406 return LazyEmplaceInternal(std::forward<K>(key)).first->second;

407 }

408

410 return InsertInternal(v);

411 }

412 std::pair<iterator, bool> insert(value_type&& v) {

413 return InsertInternal(std::move(v));

414 }

415

417 return insert(v).first;

418 }

420 return insert(std::move(v)).first;

421 }

422

423 void insert(std::initializer_list<value_type> ilist) {

424 insert(ilist.begin(), ilist.end());

425 }

426

427 template <class InputIt>

428 void insert(InputIt first, InputIt last) {

429 for (; first != last; ++first) insert(*first);

430 }

431

433 if (!node) return {end(), false, node_type()};

434 auto itr = find(node.key());

435 if (itr != end()) return {itr, false, std::move(node)};

436 list_.splice(list_.end(), node.list_);

437 set_.insert(--list_.end());

438 return {--list_.end(), true, node_type()};

439 }

440

442 return insert(std::move(node)).first;

443 }

444

445

446

447

448

449

450

451

453 V* = nullptr>

455 return InsertOrAssignInternal(std::forward<K>(k), std::forward<V>(v));

456 }

457

458 template <class K = key_type, class V = mapped_type, K* = nullptr>

460 return InsertOrAssignInternal(std::forward<K>(k), v);

461 }

462

463 template <class K = key_type, class V = mapped_type, V* = nullptr>

465 return InsertOrAssignInternal(k, std::forward<V>(v));

466 }

467

468 template <class K = key_type, class V = mapped_type>

469 std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, const V& v) {

470 return InsertOrAssignInternal(k, v);

471 }

472

474 V* = nullptr>

476 return insert_or_assign(std::forward<K>(k), std::forward<V>(v)).first;

477 }

478

479 template <class K = key_type, class V = mapped_type, K* = nullptr>

483

484 template <class K = key_type, class V = mapped_type, V* = nullptr>

488

489 template <class K = key_type, class V = mapped_type>

493

494 template <typename... Args>

495 std::pair<iterator, bool> emplace(Args&&... args) {

496 ListType node_donor;

497 auto list_iter =

498 node_donor.emplace(node_donor.end(), std::forward<Args>(args)...);

499 auto ins = set_.insert(list_iter);

500 if (!ins.second) return {*ins.first, false};

501 list_.splice(list_.end(), node_donor, list_iter);

502 return {list_iter, true};

503 }

504

505 template <class K = key_type, class... Args, K* = nullptr>

507 return try_emplace(std::forward<K>(k), std::forward<Args>(args)...).first;

508 }

509

510 template <typename... Args>

512 return emplace(std::forward<Args>(args)...).first;

513 }

514

515 template <class K = key_type, typename... Args, K* = nullptr>

516 std::pair<iterator, bool> try_emplace(key_arg<K>&& key, Args&&... args) {

517 return LazyEmplaceInternal(std::forward<key_arg<K>>(key),

518 std::forward<Args>(args)...);

519 }

520

521 template <typename H, typename E>

523 auto itr = src.list_.begin();

524 while (itr != src.list_.end()) {

526 ++itr;

527 } else {

529 }

530 }

531 }

532

533 template <typename H, typename E>

537

539 set_.erase(position->first);

540 ListType extracted_node_list;

541 extracted_node_list.splice(extracted_node_list.end(), list_, position);

542 return node_type(std::move(extracted_node_list));

543 }

544

545 template <class K = key_type,

546 std::enable_if_t<!std::is_same_v<K, iterator>, int> = 0>

548 auto it = find(key);

550 }

551

552 template <class K = key_type, typename... Args>

553 std::pair<iterator, bool> try_emplace(const key_arg<K>& key, Args&&... args) {

554 return LazyEmplaceInternal(key, std::forward<Args>(args)...);

555 }

556

558 using std::swap;

559 swap(set_, other.set_);

560 swap(list_, other.list_);

561 }

562

564 if (a.size() != b.size()) return false;

567 if (outer->capacity() > inner->capacity()) std::swap(outer, inner);

568 for (const value_type& elem : *outer) {

569 auto it = inner->find(elem.first);

570 if (it == inner->end()) return false;

571 if (it->second != elem.second) return false;

572 }

573

574 return true;

575 }

576

578 return !(a == b);

579 }

580

581 void rehash(size_t n) { set_.rehash(n); }

582

583 private:

584 template <typename Other>

585 void CopyFrom(Other&& other) {

586 for (auto& elem : other.list_) {

587 set_.insert(list_.insert(list_.end(), std::move(elem)));

588 }

589 DCHECK_EQ(set_.size(), list_.size()) << "Set and list are inconsistent.";

590 }

591

592 template <typename U>

593 std::pair<iterator, bool> InsertInternal(U&& pair) {

594 auto iter = set_.find(pair.first);

595 if (iter != set_.end()) return {*iter, false};

596 auto list_iter = list_.insert(list_.end(), std::forward<U>(pair));

597 auto inserted = set_.insert(list_iter);

598 DCHECK(inserted.second);

599 return {list_iter, true};

600 }

601

602 template <class K, class V>

603 std::pair<iterator, bool> InsertOrAssignInternal(K&& k, V&& v) {

604 auto iter = set_.find(k);

605 if (iter != set_.end()) {

606 (*iter)->second = std::forward<V>(v);

607 return {*iter, false};

608 }

609 return LazyEmplaceInternal(std::forward<K>(k), std::forward<V>(v));

610 }

611

612 template <typename K, typename... Args>

613 std::pair<iterator, bool> LazyEmplaceInternal(K&& key, Args&&... args) {

614 bool constructed = false;

615 auto set_iter =

616 set_.lazy_emplace(key, [this, &constructed, &key, &args...](auto ctor) {

617 auto list_iter =

618 list_.emplace(list_.end(), std::piecewise_construct,

619 std::forward_as_tuple(std::forward<K>(key)),

620 std::forward_as_tuple(std::forward<Args>(args)...));

621 constructed = true;

622 ctor(list_iter);

623 });

624 return {*set_iter, constructed};

625 }

626

627

628 SetType set_;

629

630

631 ListType list_;

632};

633

634}

635

636#endif

void merge(linked_hash_map< Key, Value, H, E, Alloc > &src)

Definition linked_hash_map.h:522

iterator try_emplace(const_iterator, key_arg< K > &&k, Args &&... args)

Definition linked_hash_map.h:506

hasher hash_function() const

Definition linked_hash_map.h:309

const_iterator find(const key_arg< K > &key) const

Definition linked_hash_map.h:355

iterator emplace_hint(const_iterator, Args &&... args)

Definition linked_hash_map.h:511

linked_hash_map(InputIt first, InputIt last, size_t bucket_count, const allocator_type &alloc)

Definition linked_hash_map.h:187

size_t bucket_count() const

Definition linked_hash_map.h:306

linked_hash_map(linked_hash_map &&other, const allocator_type &alloc)

Definition linked_hash_map.h:237

iterator insert(const_iterator, node_type &&node)

Definition linked_hash_map.h:441

iterator insert(const_iterator, const value_type &v)

Definition linked_hash_map.h:416

void reserve(size_t n)

Definition linked_hash_map.h:304

reverse_iterator rbegin()

Definition linked_hash_map.h:285

iterator end()

Definition linked_hash_map.h:280

void pop_front()

Definition linked_hash_map.h:296

mapped_type & operator[](const key_arg< K > &key)

Definition linked_hash_map.h:400

typename ListType::const_reverse_iterator const_reverse_iterator

Definition linked_hash_map.h:143

KeyHash hasher

Definition linked_hash_map.h:66

allocator_type get_allocator() const

Definition linked_hash_map.h:311

const_reverse_iterator rbegin() const

Definition linked_hash_map.h:287

std::pair< const key_type, mapped_type > value_type

Definition linked_hash_map.h:68

const_iterator cbegin() const

Definition linked_hash_map.h:283

InsertReturnType< iterator, node_type > insert_return_type

Definition linked_hash_map.h:151

bool contains(const key_arg< K > &key) const

Definition linked_hash_map.h:366

ptrdiff_t difference_type

Definition linked_hash_map.h:70

linked_hash_map(size_t bucket_count, const hasher &hash, const allocator_type &alloc)

Definition linked_hash_map.h:162

std::pair< iterator, bool > insert_or_assign(const key_arg< K > &k, const V &v)

Definition linked_hash_map.h:469

std::pair< iterator, bool > insert_or_assign(key_arg< K > &&k, V &&v)

Definition linked_hash_map.h:454

linked_hash_map & operator=(const linked_hash_map &other)

Definition linked_hash_map.h:246

mapped_type & at(const key_arg< K > &key)

Definition linked_hash_map.h:371

const mapped_type & at(const key_arg< K > &key) const

Definition linked_hash_map.h:380

reverse_iterator rend()

Definition linked_hash_map.h:286

std::pair< iterator, bool > insert_or_assign(const key_arg< K > &k, V &&v)

Definition linked_hash_map.h:464

iterator erase(iterator first, iterator last)

Definition linked_hash_map.h:336

const_reverse_iterator crend() const

Definition linked_hash_map.h:290

void swap(linked_hash_map &other)

Definition linked_hash_map.h:557

KeyEq key_equal

Definition linked_hash_map.h:67

iterator erase(const_iterator first, const_iterator last)

Definition linked_hash_map.h:341

linked_hash_map(std::initializer_list< value_type > init, size_t bucket_count, const allocator_type &alloc)

Definition linked_hash_map.h:208

linked_hash_map & operator=(std::initializer_list< value_type > values)

Definition linked_hash_map.h:266

void rehash(size_t n)

Definition linked_hash_map.h:581

reference back()

Definition linked_hash_map.h:292

void merge(linked_hash_map< Key, Value, H, E, Alloc > &&src)

Definition linked_hash_map.h:534

std::pair< iterator, iterator > equal_range(const key_arg< K > &key)

Definition linked_hash_map.h:385

Value mapped_type

Definition linked_hash_map.h:65

const_iterator begin() const

Definition linked_hash_map.h:281

float load_factor() const

Definition linked_hash_map.h:307

linked_hash_map(std::initializer_list< value_type > init, size_t bucket_count, const hasher &hash, const allocator_type &alloc)

Definition linked_hash_map.h:204

size_type max_size() const noexcept

Definition linked_hash_map.h:274

const_reference front() const

Definition linked_hash_map.h:293

std::pair< iterator, bool > try_emplace(const key_arg< K > &key, Args &&... args)

Definition linked_hash_map.h:553

iterator insert_or_assign(const_iterator, const key_arg< K > &k, V &&v)

Definition linked_hash_map.h:485

std::pair< iterator, bool > insert(const value_type &v)

Definition linked_hash_map.h:409

linked_hash_map(std::initializer_list< value_type > init, size_t bucket_count=0, const hasher &hash=hasher(), const key_equal &eq=key_equal(), const allocator_type &alloc=allocator_type())

Definition linked_hash_map.h:197

iterator find(const key_arg< K > &key)

Definition linked_hash_map.h:348

reference front()

Definition linked_hash_map.h:291

typename ListType::iterator iterator

Definition linked_hash_map.h:140

typename std::allocator_traits< allocator_type >::pointer pointer

Definition linked_hash_map.h:147

friend bool operator!=(const linked_hash_map &a, const linked_hash_map &b)

Definition linked_hash_map.h:577

Key key_type

Definition linked_hash_map.h:64

const_reverse_iterator rend() const

Definition linked_hash_map.h:288

typename ListType::const_iterator const_iterator

Definition linked_hash_map.h:141

insert_return_type insert(node_type &&node)

Definition linked_hash_map.h:432

size_type erase(const key_arg< K > &key)

Definition linked_hash_map.h:314

linked_hash_map(linked_hash_map &&other) noexcept

Definition linked_hash_map.h:229

typename ListType::const_reference const_reference

Definition linked_hash_map.h:145

std::pair< iterator, bool > try_emplace(key_arg< K > &&key, Args &&... args)

Definition linked_hash_map.h:516

const_reference back() const

Definition linked_hash_map.h:294

typename ListType::size_type size_type

Definition linked_hash_map.h:146

typename ListType::reference reference

Definition linked_hash_map.h:144

void insert(InputIt first, InputIt last)

Definition linked_hash_map.h:428

linked_hash_map(InputIt first, InputIt last, size_t bucket_count, const hasher &hash, const allocator_type &alloc)

Definition linked_hash_map.h:182

ABSL_ATTRIBUTE_REINITIALIZES void clear()

Definition linked_hash_map.h:299

Alloc allocator_type

Definition linked_hash_map.h:69

iterator erase(iterator position)

Definition linked_hash_map.h:332

bool empty() const

Definition linked_hash_map.h:275

const_iterator end() const

Definition linked_hash_map.h:282

friend bool operator==(const linked_hash_map &a, const linked_hash_map &b)

Definition linked_hash_map.h:563

linked_hash_map(const allocator_type &alloc)

Definition linked_hash_map.h:169

iterator erase(const_iterator position)

Definition linked_hash_map.h:324

iterator insert(const_iterator, value_type &&v)

Definition linked_hash_map.h:419

key_equal key_eq() const

Definition linked_hash_map.h:310

const_reverse_iterator crbegin() const

Definition linked_hash_map.h:289

linked_hash_map(std::initializer_list< value_type > init, const allocator_type &alloc)

Definition linked_hash_map.h:212

iterator insert_or_assign(const_iterator, key_arg< K > &&k, const V &v)

Definition linked_hash_map.h:480

const_iterator cend() const

Definition linked_hash_map.h:284

linked_hash_map & operator=(linked_hash_map &&other) noexcept

Definition linked_hash_map.h:257

std::pair< const_iterator, const_iterator > equal_range(const key_arg< K > &key) const

Definition linked_hash_map.h:392

linked_hash_map()=default

NodeHandle node_type

Definition linked_hash_map.h:150

std::pair< iterator, bool > insert_or_assign(key_arg< K > &&k, const V &v)

Definition linked_hash_map.h:459

void pop_back()

Definition linked_hash_map.h:297

size_type size() const

Definition linked_hash_map.h:273

size_type count(const key_arg< K > &key) const

Definition linked_hash_map.h:362

iterator insert_or_assign(const_iterator, key_arg< K > &&k, V &&v)

Definition linked_hash_map.h:475

linked_hash_map(size_t bucket_count, const allocator_type &alloc)

Definition linked_hash_map.h:166

iterator insert_or_assign(const_iterator, const key_arg< K > &k, const V &v)

Definition linked_hash_map.h:490

linked_hash_map(InputIt first, InputIt last, const allocator_type &alloc)

Definition linked_hash_map.h:193

void insert(std::initializer_list< value_type > ilist)

Definition linked_hash_map.h:423

std::pair< iterator, bool > emplace(Args &&... args)

Definition linked_hash_map.h:495

node_type extract(const key_arg< K > &key)

Definition linked_hash_map.h:547

linked_hash_map(const linked_hash_map &other, const allocator_type &alloc)

Definition linked_hash_map.h:223

linked_hash_map(InputIt first, InputIt last, size_t bucket_count=0, const hasher &hash=hasher(), const key_equal &eq=key_equal(), const allocator_type &alloc=allocator_type())

Definition linked_hash_map.h:173

linked_hash_map(const linked_hash_map &other)

Definition linked_hash_map.h:217

linked_hash_map(size_t bucket_count, const hasher &hash=hasher(), const key_equal &eq=key_equal(), const allocator_type &alloc=allocator_type())

Definition linked_hash_map.h:155

size_t capacity() const

Definition linked_hash_map.h:305

mapped_type & operator[](key_arg< K > &&key)

Definition linked_hash_map.h:405

typename ListType::reverse_iterator reverse_iterator

Definition linked_hash_map.h:142

typename std::allocator_traits< allocator_type >::const_pointer const_pointer