intrusive_heap.h 41 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133
  1. // Copyright 2019 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef BASE_CONTAINERS_INTRUSIVE_HEAP_H_
  5. #define BASE_CONTAINERS_INTRUSIVE_HEAP_H_
  6. // Implements a standard max-heap, but with arbitrary element removal. To
  7. // facilitate this, each element has associated with it a HeapHandle (an opaque
  8. // wrapper around the index at which the element is stored), which is maintained
  9. // by the heap as elements move within it.
  10. //
  11. // An IntrusiveHeap is implemented as a standard max-heap over a std::vector<T>,
  12. // like std::make_heap. Insertion, removal and updating are amortized O(lg size)
  13. // (occasional O(size) cost if a new vector allocation is required). Retrieving
  14. // an element by handle is O(1). Looking up the top element is O(1). Insertions,
  15. // removals and updates invalidate all iterators, but handles remain valid.
  16. // Similar to a std::set, all iterators are read-only so as to disallow changing
  17. // elements and violating the heap property. That being said, if the type you
  18. // are storing is able to have its sort key be changed externally you can
  19. // repair the heap by resorting the modified element via a call to "Update".
  20. //
  21. // Example usage:
  22. //
  23. // // Create a heap, wrapping integer elements with WithHeapHandle in order to
  24. // // endow them with heap handles.
  25. // IntrusiveHeap<WithHeapHandle<int>> heap;
  26. //
  27. // // WithHeapHandle<T> is for simple or opaque types. In cases where you
  28. // // control the type declaration you can also provide HeapHandle storage by
  29. // // deriving from InternalHeapHandleStorage.
  30. // class Foo : public InternalHeapHandleStorage {
  31. // public:
  32. // explicit Foo(int);
  33. // ...
  34. // };
  35. // IntrusiveHeap<Foo> heap2;
  36. //
  37. // // Insert some elements. Like most containers, "insert" returns an iterator
  38. // // to the element in the container.
  39. // heap.insert(3);
  40. // heap.insert(1);
  41. // auto it = heap.insert(4);
  42. //
  43. // // By default this is a max heap, so the top element should be 4 at this
  44. // // point.
  45. // EXPECT_EQ(4, heap.top().value());
  46. //
  47. // // Iterators are invalidated by further heap operations, but handles are
  48. // // not. Grab a handle to the current top element so we can track it across
  49. // // changes.
  50. // HeapHandle* handle = it->handle();
  51. //
  52. // // Insert a new max element. 4 should no longer be the top.
  53. // heap.insert(5);
  54. // EXPECT_EQ(5, heap.top().value());
  55. //
  56. // // We can lookup and erase element 4 by its handle, even though it has
  57. // // moved. Note that erasing the element invalidates the handle to it.
  58. // EXPECT_EQ(4, heap.at(*handle).value());
  59. // heap.erase(*handle);
  60. // handle = nullptr;
  61. //
  62. // // Popping the current max (5), makes 3 the new max, as we already erased
  63. // // element 4.
  64. // heap.pop();
  65. // EXPECT_EQ(3, heap.top().value());
  66. //
  67. // Under the hood the HeapHandle is managed by an object implementing the
  68. // HeapHandleAccess interface, which is passed as a parameter to the
  69. // IntrusiveHeap template:
  70. //
  71. // // Gets the heap handle associated with the element. This should return the
  72. // // most recently set handle value, or HeapHandle::Invalid(). This is only
  73. // // called in DCHECK builds.
  74. // HeapHandle GetHeapHandle(const T*);
  75. //
  76. // // Changes the result of GetHeapHandle. GetHeapHandle() must return the
  77. // // most recent value provided to SetHeapHandle() or HeapHandle::Invalid().
  78. // // In some implementations, where GetHeapHandle() can independently
  79. // // reproduce the correct value, it is possible that SetHeapHandle() does
  80. // // nothing.
  81. // void SetHeapHandle(T*, HeapHandle);
  82. //
  83. // // Clears the heap handle associated with the given element. After calling
  84. // // this GetHeapHandle() must return HeapHandle::Invalid().
  85. // void ClearHeapHandle(T*);
  86. //
  87. // The default implementation of HeapHandleAccess assumes that your type
  88. // provides HeapHandle storage and will simply forward these calls to equivalent
  89. // member functions on the type T:
  90. //
  91. // void T::SetHeapHandle(HeapHandle)
  92. // void T::ClearHeapHandle()
  93. // HeapHandle T::GetHeapHandle() const
  94. //
  95. // The WithHeapHandle and InternalHeapHandleStorage classes in turn provide
  96. // implementations of that contract.
  97. //
  98. // In summary, to provide heap handle support for your type, you can do one of
  99. // the following (from most manual / least magical, to least manual / most
  100. // magical):
  101. //
  102. // 0. use a custom HeapHandleAccessor, and implement storage however you want;
  103. // 1. use the default HeapHandleAccessor, and manually provide storage on your
  104. // your element type and implement the IntrusiveHeap contract;
  105. // 2. use the default HeapHandleAccessor, and endow your type with handle
  106. // storage by deriving from a helper class (see InternalHeapHandleStorage);
  107. // or,
  108. // 3. use the default HeapHandleAccessor, and wrap your type in a container that
  109. // provides handle storage (see WithHeapHandle<T>).
  110. //
  111. // Approach 0 is suitable for custom types that already implement something akin
  112. // to heap handles, via back pointers or any other mechanism, but where the
  113. // storage is external to the objects in the heap. If you already have the
  114. // ability to determine where in a container an object lives despite it
  115. // being moved, then you don't need the overhead of storing an actual HeapHandle
  116. // whose value can be inferred.
  117. //
  118. // Approach 1 is is suitable in cases like the above, but where the data
  119. // allowing you to determine the index of an element in a container is stored
  120. // directly in the object itself.
  121. //
  122. // Approach 2 is suitable for types whose declarations you control, where you
  123. // are able to use inheritance.
  124. //
  125. // Finally, approach 3 is suitable when you are storing PODs, or a type whose
  126. // declaration you can not change.
  127. //
  128. // Most users should be using approach 2 or 3.
  129. #include <algorithm>
  130. #include <functional>
  131. #include <limits>
  132. #include <memory>
  133. #include <type_traits>
  134. #include <utility>
  135. #include <vector>
  136. #include "base/base_export.h"
  137. #include "base/check.h"
  138. #include "base/check_op.h"
  139. #include "base/containers/stack_container.h"
  140. #include "base/memory/ptr_util.h"
  141. #include "base/ranges/algorithm.h"
  142. namespace base {
  143. // Intended as a wrapper around an |index_| in the vector storage backing an
  144. // IntrusiveHeap. A HeapHandle is associated with each element in an
  145. // IntrusiveHeap, and is maintained by the heap as the object moves around
  146. // within it. It can be used to subsequently remove the element, or update it
  147. // in place.
  148. class BASE_EXPORT HeapHandle {
  149. public:
  150. enum : size_t { kInvalidIndex = std::numeric_limits<size_t>::max() };
  151. constexpr HeapHandle() = default;
  152. constexpr HeapHandle(const HeapHandle& other) = default;
  153. HeapHandle(HeapHandle&& other) noexcept
  154. : index_(std::exchange(other.index_, kInvalidIndex)) {}
  155. ~HeapHandle() = default;
  156. HeapHandle& operator=(const HeapHandle& other) = default;
  157. HeapHandle& operator=(HeapHandle&& other) noexcept {
  158. index_ = std::exchange(other.index_, kInvalidIndex);
  159. return *this;
  160. }
  161. static HeapHandle Invalid();
  162. // Resets this handle back to an invalid state.
  163. void reset() { index_ = kInvalidIndex; }
  164. // Accessors.
  165. size_t index() const { return index_; }
  166. bool IsValid() const { return index_ != kInvalidIndex; }
  167. // Comparison operators.
  168. friend bool operator==(const HeapHandle& lhs, const HeapHandle& rhs) {
  169. return lhs.index_ == rhs.index_;
  170. }
  171. friend bool operator!=(const HeapHandle& lhs, const HeapHandle& rhs) {
  172. return lhs.index_ != rhs.index_;
  173. }
  174. friend bool operator<(const HeapHandle& lhs, const HeapHandle& rhs) {
  175. return lhs.index_ < rhs.index_;
  176. }
  177. friend bool operator>(const HeapHandle& lhs, const HeapHandle& rhs) {
  178. return lhs.index_ > rhs.index_;
  179. }
  180. friend bool operator<=(const HeapHandle& lhs, const HeapHandle& rhs) {
  181. return lhs.index_ <= rhs.index_;
  182. }
  183. friend bool operator>=(const HeapHandle& lhs, const HeapHandle& rhs) {
  184. return lhs.index_ >= rhs.index_;
  185. }
  186. private:
  187. template <typename T, typename Compare, typename HeapHandleAccessor>
  188. friend class IntrusiveHeap;
  189. // Only IntrusiveHeaps can create valid HeapHandles.
  190. explicit HeapHandle(size_t index) : index_(index) {}
  191. size_t index_ = kInvalidIndex;
  192. };
  193. // The default HeapHandleAccessor, which simply forwards calls to the underlying
  194. // type.
  195. template <typename T>
  196. struct DefaultHeapHandleAccessor {
  197. void SetHeapHandle(T* element, HeapHandle handle) const {
  198. element->SetHeapHandle(handle);
  199. }
  200. void ClearHeapHandle(T* element) const { element->ClearHeapHandle(); }
  201. HeapHandle GetHeapHandle(const T* element) const {
  202. return element->GetHeapHandle();
  203. }
  204. };
  205. // Intrusive heap class. This is something like a std::vector (insertion and
  206. // removal are similar, objects don't have a fixed address in memory) crossed
  207. // with a std::set (elements are considered immutable once they're in the
  208. // container).
  209. template <typename T,
  210. typename Compare = std::less<T>,
  211. typename HeapHandleAccessor = DefaultHeapHandleAccessor<T>>
  212. class IntrusiveHeap {
  213. private:
  214. using UnderlyingType = std::vector<T>;
  215. public:
  216. //////////////////////////////////////////////////////////////////////////////
  217. // Types.
  218. using value_type = typename UnderlyingType::value_type;
  219. using size_type = typename UnderlyingType::size_type;
  220. using difference_type = typename UnderlyingType::difference_type;
  221. using value_compare = Compare;
  222. using heap_handle_accessor = HeapHandleAccessor;
  223. using reference = typename UnderlyingType::reference;
  224. using const_reference = typename UnderlyingType::const_reference;
  225. using pointer = typename UnderlyingType::pointer;
  226. using const_pointer = typename UnderlyingType::const_pointer;
  227. // Iterators are read-only.
  228. using iterator = typename UnderlyingType::const_iterator;
  229. using const_iterator = typename UnderlyingType::const_iterator;
  230. using reverse_iterator = typename UnderlyingType::const_reverse_iterator;
  231. using const_reverse_iterator =
  232. typename UnderlyingType::const_reverse_iterator;
  233. //////////////////////////////////////////////////////////////////////////////
  234. // Lifetime.
  235. IntrusiveHeap() = default;
  236. IntrusiveHeap(const value_compare& comp, const heap_handle_accessor& access)
  237. : impl_(comp, access) {}
  238. template <class InputIterator>
  239. IntrusiveHeap(InputIterator first,
  240. InputIterator last,
  241. const value_compare& comp = value_compare(),
  242. const heap_handle_accessor& access = heap_handle_accessor())
  243. : impl_(comp, access) {
  244. insert(first, last);
  245. }
  246. // Moves an intrusive heap. The outstanding handles remain valid and end up
  247. // pointing to the new heap.
  248. IntrusiveHeap(IntrusiveHeap&& other) = default;
  249. // Copy constructor for an intrusive heap.
  250. IntrusiveHeap(const IntrusiveHeap&);
  251. // Initializer list constructor.
  252. template <typename U>
  253. IntrusiveHeap(std::initializer_list<U> ilist,
  254. const value_compare& comp = value_compare(),
  255. const heap_handle_accessor& access = heap_handle_accessor())
  256. : impl_(comp, access) {
  257. insert(std::begin(ilist), std::end(ilist));
  258. }
  259. ~IntrusiveHeap();
  260. //////////////////////////////////////////////////////////////////////////////
  261. // Assignment.
  262. IntrusiveHeap& operator=(IntrusiveHeap&&) noexcept;
  263. IntrusiveHeap& operator=(const IntrusiveHeap&);
  264. IntrusiveHeap& operator=(std::initializer_list<value_type> ilist);
  265. //////////////////////////////////////////////////////////////////////////////
  266. // Element access.
  267. //
  268. // These provide O(1) const access to the elements in the heap. If you wish to
  269. // modify an element in the heap you should first remove it from the heap, and
  270. // then reinsert it into the heap, or use the "Replace*" helper functions. In
  271. // the rare case where you directly modify an element in the heap you can
  272. // subsequently repair the heap with "Update".
  273. const_reference at(size_type pos) const { return impl_.heap_.at(pos); }
  274. const_reference at(HeapHandle pos) const {
  275. return impl_.heap_.at(pos.index());
  276. }
  277. const_reference operator[](size_type pos) const { return impl_.heap_[pos]; }
  278. const_reference operator[](HeapHandle pos) const {
  279. return impl_.heap_[pos.index()];
  280. }
  281. const_reference front() const { return impl_.heap_.front(); }
  282. const_reference back() const { return impl_.heap_.back(); }
  283. const_reference top() const { return impl_.heap_.front(); }
  284. // May or may not return a null pointer if size() is zero.
  285. const_pointer data() const { return impl_.heap_.data(); }
  286. //////////////////////////////////////////////////////////////////////////////
  287. // Memory management.
  288. void reserve(size_type new_capacity) { impl_.heap_.reserve(new_capacity); }
  289. size_type capacity() const { return impl_.heap_.capacity(); }
  290. void shrink_to_fit() { impl_.heap_.shrink_to_fit(); }
  291. //////////////////////////////////////////////////////////////////////////////
  292. // Size management.
  293. void clear();
  294. size_type size() const { return impl_.heap_.size(); }
  295. size_type max_size() const { return impl_.heap_.max_size(); }
  296. bool empty() const { return impl_.heap_.empty(); }
  297. //////////////////////////////////////////////////////////////////////////////
  298. // Iterators.
  299. //
  300. // Only constant iterators are allowed.
  301. const_iterator begin() const { return impl_.heap_.cbegin(); }
  302. const_iterator cbegin() const { return impl_.heap_.cbegin(); }
  303. const_iterator end() const { return impl_.heap_.cend(); }
  304. const_iterator cend() const { return impl_.heap_.cend(); }
  305. const_reverse_iterator rbegin() const { return impl_.heap_.crbegin(); }
  306. const_reverse_iterator crbegin() const { return impl_.heap_.crbegin(); }
  307. const_reverse_iterator rend() const { return impl_.heap_.crend(); }
  308. const_reverse_iterator crend() const { return impl_.heap_.crend(); }
  309. //////////////////////////////////////////////////////////////////////////////
  310. // Insertion (these are std::multiset like, with no position hints).
  311. //
  312. // All insertion operations invalidate iterators, pointers and references.
  313. // Handles remain valid. Insertion of one element is amortized O(lg size)
  314. // (occasional O(size) cost if a new vector allocation is required).
  315. const_iterator insert(const value_type& value) { return InsertImpl(value); }
  316. const_iterator insert(value_type&& value) {
  317. return InsertImpl(std::move_if_noexcept(value));
  318. }
  319. template <class InputIterator>
  320. void insert(InputIterator first, InputIterator last);
  321. template <typename... Args>
  322. const_iterator emplace(Args&&... args);
  323. //////////////////////////////////////////////////////////////////////////////
  324. // Removing elements.
  325. //
  326. // Erasing invalidates all outstanding iterators, pointers and references.
  327. // Handles remain valid. Removing one element is amortized O(lg size)
  328. // (occasional O(size) cost if a new vector allocation is required).
  329. //
  330. // Note that it is safe for the element being removed to be in an invalid
  331. // state (modified such that it may currently violate the heap property)
  332. // when this called.
  333. // Takes the element from the heap at the given position, erasing that entry
  334. // from the heap. This can only be called if |value_type| is movable.
  335. value_type take(size_type pos);
  336. // Version of take that will accept iterators and handles. This can only be
  337. // called if |value_type| is movable.
  338. template <typename P>
  339. value_type take(P pos) {
  340. return take(ToIndex(pos));
  341. }
  342. // Takes the top element from the heap.
  343. value_type take_top() { return take(0u); }
  344. // Erases the element at the given position |pos|.
  345. void erase(size_type pos);
  346. // Version of erase that will accept iterators and handles.
  347. template <typename P>
  348. void erase(P pos) {
  349. erase(ToIndex(pos));
  350. }
  351. // Removes the element at the top of the heap (accessible via "top", or
  352. // "front" or "take").
  353. void pop() { erase(0u); }
  354. // Erases every element that matches the predicate. This is done in-place for
  355. // maximum efficiency. Also, to avoid re-entrancy issues, elements are deleted
  356. // at the very end.
  357. // Note: This function is currently tuned for a use-case where there are
  358. // usually 8 or less elements removed at a time. Consider adding a template
  359. // parameter if a different tuning is needed.
  360. template <typename Functor>
  361. void EraseIf(Functor predicate) {
  362. // Stable partition ensures that if no elements are erased, the heap remains
  363. // intact.
  364. auto erase_start = std::stable_partition(
  365. impl_.heap_.begin(), impl_.heap_.end(),
  366. [&](const auto& element) { return !predicate(element); });
  367. // Clear the heap handle of every element that will be erased.
  368. for (size_t i = static_cast<size_t>(erase_start - impl_.heap_.begin());
  369. i < impl_.heap_.size(); ++i) {
  370. ClearHeapHandle(i);
  371. }
  372. // Deleting an element can potentially lead to reentrancy, we move all the
  373. // elements to be erased into a temporary container before deleting them.
  374. // This is to avoid changing the underlying container during the erase()
  375. // call.
  376. StackVector<value_type, 8> elements_to_delete;
  377. std::move(erase_start, impl_.heap_.end(),
  378. std::back_inserter(elements_to_delete.container()));
  379. impl_.heap_.erase(erase_start, impl_.heap_.end());
  380. // If no elements were removed, then the heap is still intact.
  381. if (elements_to_delete->empty())
  382. return;
  383. // Repair the heap and ensure handles are pointing to the right index.
  384. ranges::make_heap(impl_.heap_, value_comp());
  385. for (size_t i = 0; i < size(); ++i)
  386. SetHeapHandle(i);
  387. // Explicitly delete elements last.
  388. elements_to_delete->clear();
  389. }
  390. //////////////////////////////////////////////////////////////////////////////
  391. // Updating.
  392. //
  393. // Amortized cost of O(lg size).
  394. // Replaces the element corresponding to |handle| with a new |element|.
  395. const_iterator Replace(size_type pos, const T& element) {
  396. return ReplaceImpl(pos, element);
  397. }
  398. const_iterator Replace(size_type pos, T&& element) {
  399. return ReplaceImpl(pos, std::move_if_noexcept(element));
  400. }
  401. // Versions of Replace that will accept handles and iterators.
  402. template <typename P>
  403. const_iterator Replace(P pos, const T& element) {
  404. return ReplaceImpl(ToIndex(pos), element);
  405. }
  406. template <typename P>
  407. const_iterator Replace(P pos, T&& element) {
  408. return ReplaceImpl(ToIndex(pos), std::move_if_noexcept(element));
  409. }
  410. // Replaces the top element in the heap with the provided element.
  411. const_iterator ReplaceTop(const T& element) {
  412. return ReplaceTopImpl(element);
  413. }
  414. const_iterator ReplaceTop(T&& element) {
  415. return ReplaceTopImpl(std::move_if_noexcept(element));
  416. }
  417. // Causes the object at the given location to be resorted into an appropriate
  418. // position in the heap. To be used if the object in the heap was externally
  419. // modified, and the heap needs to be repaired. This only works if a single
  420. // heap element has been modified, otherwise the behaviour is undefined.
  421. const_iterator Update(size_type pos);
  422. template <typename P>
  423. const_iterator Update(P pos) {
  424. return Update(ToIndex(pos));
  425. }
  426. // Applies a modification function to the object at the given location, then
  427. // repairs the heap. To be used to modify an element in the heap in-place
  428. // while keeping the heap intact.
  429. template <typename P, typename UnaryOperation>
  430. const_iterator Modify(P pos, UnaryOperation unary_op) {
  431. size_type index = ToIndex(pos);
  432. unary_op(impl_.heap_.at(index));
  433. return Update(index);
  434. }
  435. //////////////////////////////////////////////////////////////////////////////
  436. // Access to helper functors.
  437. const value_compare& value_comp() const { return impl_.get_value_compare(); }
  438. const heap_handle_accessor& heap_handle_access() const {
  439. return impl_.get_heap_handle_access();
  440. }
  441. //////////////////////////////////////////////////////////////////////////////
  442. // General operations.
  443. void swap(IntrusiveHeap& other) noexcept;
  444. friend void swap(IntrusiveHeap& lhs, IntrusiveHeap& rhs) { lhs.swap(rhs); }
  445. // Comparison operators. These check for exact equality. Two heaps that are
  446. // semantically equivalent (contain the same elements, but in different
  447. // orders) won't compare as equal using these operators.
  448. friend bool operator==(const IntrusiveHeap& lhs, const IntrusiveHeap& rhs) {
  449. return lhs.impl_.heap_ == rhs.impl_.heap_;
  450. }
  451. friend bool operator!=(const IntrusiveHeap& lhs, const IntrusiveHeap& rhs) {
  452. return lhs.impl_.heap_ != rhs.impl_.heap_;
  453. }
  454. //////////////////////////////////////////////////////////////////////////////
  455. // Utility functions.
  456. // Converts iterators and handles to indices. Helpers for templated versions
  457. // of insert/erase/Replace.
  458. size_type ToIndex(HeapHandle handle) { return handle.index(); }
  459. size_type ToIndex(const_iterator pos);
  460. size_type ToIndex(const_reverse_iterator pos);
  461. private:
  462. // Templated version of ToIndex that lets insert/erase/Replace work with all
  463. // integral types.
  464. template <typename I, typename = std::enable_if_t<std::is_integral<I>::value>>
  465. size_type ToIndex(I pos) {
  466. return static_cast<size_type>(pos);
  467. }
  468. // Returns the last valid index in |heap_|.
  469. size_type GetLastIndex() const { return impl_.heap_.size() - 1; }
  470. // Helper functions for setting heap handles.
  471. void SetHeapHandle(size_type i);
  472. void ClearHeapHandle(size_type i);
  473. HeapHandle GetHeapHandle(size_type i);
  474. // Helpers for doing comparisons between elements inside and outside of the
  475. // heap.
  476. bool Less(size_type i, size_type j);
  477. bool Less(const T& element, size_type i);
  478. bool Less(size_type i, const T& element);
  479. // The following function are all related to the basic heap algorithm
  480. // underpinning this data structure. They are templated so that they work with
  481. // both movable (U = T&&) and non-movable (U = const T&) types.
  482. // Primitive helpers for adding removing / elements to the heap. To minimize
  483. // moves, the heap is implemented by making a hole where an element used to
  484. // be (or where a new element will soon be), and moving the hole around,
  485. // before finally filling the hole or deleting the entry corresponding to the
  486. // hole.
  487. void MakeHole(size_type pos);
  488. template <typename U>
  489. void FillHole(size_type hole, U element);
  490. void MoveHole(size_type new_hole_pos, size_type old_hole_pos);
  491. // Moves a hold up the tree and fills it with the provided |element|. Returns
  492. // the final index of the element.
  493. template <typename U>
  494. size_type MoveHoleUpAndFill(size_type hole_pos, U element);
  495. // Moves a hole down the tree and fills it with the provided |element|. If
  496. // |kFillWithLeaf| is true it will deterministically move the hole all the
  497. // way down the tree, avoiding a second comparison per level, before
  498. // potentially moving it back up the tree.
  499. struct WithLeafElement {
  500. static constexpr bool kIsLeafElement = true;
  501. };
  502. struct WithElement {
  503. static constexpr bool kIsLeafElement = false;
  504. };
  505. template <typename FillElementType, typename U>
  506. size_type MoveHoleDownAndFill(size_type hole_pos, U element);
  507. // Implementation of Insert and Replace built on top of the MoveHole
  508. // primitives.
  509. template <typename U>
  510. const_iterator InsertImpl(U element);
  511. template <typename U>
  512. const_iterator ReplaceImpl(size_type pos, U element);
  513. template <typename U>
  514. const_iterator ReplaceTopImpl(U element);
  515. // To support comparators that may not be possible to default-construct, we
  516. // have to store an instance of value_compare. Using this to store all
  517. // internal state of IntrusiveHeap and using private inheritance to store
  518. // compare lets us take advantage of an empty base class optimization to avoid
  519. // extra space in the common case when Compare has no state.
  520. struct Impl : private value_compare, private heap_handle_accessor {
  521. Impl(const value_compare& value_comp,
  522. const heap_handle_accessor& heap_handle_access)
  523. : value_compare(value_comp), heap_handle_accessor(heap_handle_access) {}
  524. Impl() = default;
  525. Impl(Impl&&) = default;
  526. Impl(const Impl&) = default;
  527. Impl& operator=(Impl&& other) = default;
  528. Impl& operator=(const Impl& other) = default;
  529. const value_compare& get_value_compare() const { return *this; }
  530. value_compare& get_value_compare() { return *this; }
  531. const heap_handle_accessor& get_heap_handle_access() const { return *this; }
  532. heap_handle_accessor& get_heap_handle_access() { return *this; }
  533. // The items in the heap.
  534. UnderlyingType heap_;
  535. } impl_;
  536. };
  537. // Helper class to endow an object with internal HeapHandle storage. By deriving
  538. // from this type you endow your class with self-owned storage for a HeapHandle.
  539. // This is a move-only type so that the handle follows the element across moves
  540. // and resizes of the underlying vector.
  541. class BASE_EXPORT InternalHeapHandleStorage {
  542. public:
  543. InternalHeapHandleStorage();
  544. InternalHeapHandleStorage(const InternalHeapHandleStorage&) = delete;
  545. InternalHeapHandleStorage(InternalHeapHandleStorage&& other) noexcept;
  546. virtual ~InternalHeapHandleStorage();
  547. InternalHeapHandleStorage& operator=(const InternalHeapHandleStorage&) =
  548. delete;
  549. InternalHeapHandleStorage& operator=(
  550. InternalHeapHandleStorage&& other) noexcept;
  551. // Allows external clients to get a pointer to the heap handle. This allows
  552. // them to remove the element from the heap regardless of its location.
  553. HeapHandle* handle() const { return handle_.get(); }
  554. // Implementation of IntrusiveHeap contract. Inlined to keep heap code as fast
  555. // as possible.
  556. void SetHeapHandle(HeapHandle handle) {
  557. DCHECK(handle.IsValid());
  558. if (handle_)
  559. *handle_ = handle;
  560. }
  561. void ClearHeapHandle() {
  562. if (handle_)
  563. handle_->reset();
  564. }
  565. HeapHandle GetHeapHandle() const {
  566. if (handle_)
  567. return *handle_;
  568. return HeapHandle::Invalid();
  569. }
  570. // Utility functions.
  571. void swap(InternalHeapHandleStorage& other) noexcept;
  572. friend void swap(InternalHeapHandleStorage& lhs,
  573. InternalHeapHandleStorage& rhs) {
  574. lhs.swap(rhs);
  575. }
  576. private:
  577. std::unique_ptr<HeapHandle> handle_;
  578. };
  579. // Spiritually akin to a std::pair<T, std::unique_ptr<HeapHandle>>. Can be used
  580. // to wrap arbitrary types and provide them with a HeapHandle, making them
  581. // appropriate for use in an IntrusiveHeap. This is a move-only type.
  582. template <typename T>
  583. class WithHeapHandle : public InternalHeapHandleStorage {
  584. public:
  585. WithHeapHandle() = default;
  586. // Allow implicit conversion of any type that T supports for ease of use with
  587. // InstrusiveHeap constructors/insert/emplace.
  588. template <typename U>
  589. WithHeapHandle(U value) : value_(std::move_if_noexcept(value)) {}
  590. WithHeapHandle(T&& value) noexcept : value_(std::move(value)) {}
  591. // Constructor that forwards all arguments along to |value_|.
  592. template <class... Args>
  593. explicit WithHeapHandle(Args&&... args);
  594. WithHeapHandle(const WithHeapHandle&) = delete;
  595. WithHeapHandle(WithHeapHandle&& other) noexcept = default;
  596. ~WithHeapHandle() override = default;
  597. WithHeapHandle& operator=(const WithHeapHandle&) = delete;
  598. WithHeapHandle& operator=(WithHeapHandle&& other) = default;
  599. T& value() { return value_; }
  600. const T& value() const { return value_; }
  601. // Utility functions.
  602. void swap(WithHeapHandle& other) noexcept;
  603. friend void swap(WithHeapHandle& lhs, WithHeapHandle& rhs) { lhs.swap(rhs); }
  604. // Comparison operators, for compatibility with ordered STL containers.
  605. friend bool operator==(const WithHeapHandle& lhs, const WithHeapHandle& rhs) {
  606. return lhs.value_ == rhs.value_;
  607. }
  608. friend bool operator!=(const WithHeapHandle& lhs, const WithHeapHandle& rhs) {
  609. return lhs.value_ != rhs.value_;
  610. }
  611. friend bool operator<=(const WithHeapHandle& lhs, const WithHeapHandle& rhs) {
  612. return lhs.value_ <= rhs.value_;
  613. }
  614. friend bool operator<(const WithHeapHandle& lhs, const WithHeapHandle& rhs) {
  615. return lhs.value_ < rhs.value_;
  616. }
  617. friend bool operator>=(const WithHeapHandle& lhs, const WithHeapHandle& rhs) {
  618. return lhs.value_ >= rhs.value_;
  619. }
  620. friend bool operator>(const WithHeapHandle& lhs, const WithHeapHandle& rhs) {
  621. return lhs.value_ > rhs.value_;
  622. }
  623. private:
  624. T value_;
  625. };
  626. ////////////////////////////////////////////////////////////////////////////////
  627. // IMPLEMENTATION DETAILS
  628. namespace intrusive_heap {
  629. BASE_EXPORT inline size_t ParentIndex(size_t i) {
  630. DCHECK_NE(0u, i);
  631. return (i - 1) / 2;
  632. }
  633. BASE_EXPORT inline size_t LeftIndex(size_t i) {
  634. return 2 * i + 1;
  635. }
  636. template <typename HandleType>
  637. bool IsInvalid(const HandleType& handle) {
  638. return !handle || !handle->IsValid();
  639. }
  640. BASE_EXPORT inline void CheckInvalidOrEqualTo(HeapHandle handle, size_t index) {
  641. if (handle.IsValid())
  642. DCHECK_EQ(index, handle.index());
  643. }
  644. } // namespace intrusive_heap
  645. ////////////////////////////////////////////////////////////////////////////////
  646. // IntrusiveHeap
  647. template <typename T, typename Compare, typename HeapHandleAccessor>
  648. IntrusiveHeap<T, Compare, HeapHandleAccessor>::IntrusiveHeap(
  649. const IntrusiveHeap& other)
  650. : impl_(other.impl_) {
  651. for (size_t i = 0; i < size(); ++i) {
  652. SetHeapHandle(i);
  653. }
  654. }
  655. template <typename T, typename Compare, typename HeapHandleAccessor>
  656. IntrusiveHeap<T, Compare, HeapHandleAccessor>::~IntrusiveHeap() {
  657. clear();
  658. }
  659. template <typename T, typename Compare, typename HeapHandleAccessor>
  660. IntrusiveHeap<T, Compare, HeapHandleAccessor>&
  661. IntrusiveHeap<T, Compare, HeapHandleAccessor>::operator=(
  662. IntrusiveHeap&& other) noexcept {
  663. clear();
  664. impl_ = std::move(other.impl_);
  665. return *this;
  666. }
  667. template <typename T, typename Compare, typename HeapHandleAccessor>
  668. IntrusiveHeap<T, Compare, HeapHandleAccessor>&
  669. IntrusiveHeap<T, Compare, HeapHandleAccessor>::operator=(
  670. const IntrusiveHeap& other) {
  671. clear();
  672. impl_ = other.impl_;
  673. for (size_t i = 0; i < size(); ++i) {
  674. SetHeapHandle(i);
  675. }
  676. return *this;
  677. }
  678. template <typename T, typename Compare, typename HeapHandleAccessor>
  679. IntrusiveHeap<T, Compare, HeapHandleAccessor>&
  680. IntrusiveHeap<T, Compare, HeapHandleAccessor>::operator=(
  681. std::initializer_list<value_type> ilist) {
  682. clear();
  683. insert(std::begin(ilist), std::end(ilist));
  684. }
  685. template <typename T, typename Compare, typename HeapHandleAccessor>
  686. void IntrusiveHeap<T, Compare, HeapHandleAccessor>::clear() {
  687. // Make all of the handles invalid before cleaning up the heap.
  688. for (size_type i = 0; i < size(); ++i) {
  689. ClearHeapHandle(i);
  690. }
  691. // Clear the heap.
  692. impl_.heap_.clear();
  693. }
  694. template <typename T, typename Compare, typename HeapHandleAccessor>
  695. template <class InputIterator>
  696. void IntrusiveHeap<T, Compare, HeapHandleAccessor>::insert(InputIterator first,
  697. InputIterator last) {
  698. for (auto it = first; it != last; ++it) {
  699. insert(value_type(*it));
  700. }
  701. }
  702. template <typename T, typename Compare, typename HeapHandleAccessor>
  703. template <typename... Args>
  704. typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::const_iterator
  705. IntrusiveHeap<T, Compare, HeapHandleAccessor>::emplace(Args&&... args) {
  706. value_type value(std::forward<Args>(args)...);
  707. return InsertImpl(std::move_if_noexcept(value));
  708. }
  709. template <typename T, typename Compare, typename HeapHandleAccessor>
  710. typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::value_type
  711. IntrusiveHeap<T, Compare, HeapHandleAccessor>::take(size_type pos) {
  712. // Make a hole by taking the element out of the heap.
  713. MakeHole(pos);
  714. value_type val = std::move(impl_.heap_[pos]);
  715. // If the element being taken is already the last element then the heap
  716. // doesn't need to be repaired.
  717. if (pos != GetLastIndex()) {
  718. MakeHole(GetLastIndex());
  719. // Move the hole down the heap, filling it with the current leaf at the
  720. // very end of the heap.
  721. MoveHoleDownAndFill<WithLeafElement>(
  722. pos, std::move(impl_.heap_[GetLastIndex()]));
  723. }
  724. impl_.heap_.pop_back();
  725. return val;
  726. }
  727. // This is effectively identical to "take", but it avoids an unnecessary move.
  728. template <typename T, typename Compare, typename HeapHandleAccessor>
  729. void IntrusiveHeap<T, Compare, HeapHandleAccessor>::erase(size_type pos) {
  730. DCHECK_LT(pos, size());
  731. // Make a hole by taking the element out of the heap.
  732. MakeHole(pos);
  733. // If the element being erased is already the last element then the heap
  734. // doesn't need to be repaired.
  735. if (pos != GetLastIndex()) {
  736. MakeHole(GetLastIndex());
  737. // Move the hole down the heap, filling it with the current leaf at the
  738. // very end of the heap.
  739. MoveHoleDownAndFill<WithLeafElement>(
  740. pos, std::move_if_noexcept(impl_.heap_[GetLastIndex()]));
  741. }
  742. impl_.heap_.pop_back();
  743. }
  744. template <typename T, typename Compare, typename HeapHandleAccessor>
  745. typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::const_iterator
  746. IntrusiveHeap<T, Compare, HeapHandleAccessor>::Update(size_type pos) {
  747. DCHECK_LT(pos, size());
  748. MakeHole(pos);
  749. // Determine if we're >= parent, in which case we may need to go up.
  750. bool child_greater_eq_parent = false;
  751. size_type i = 0;
  752. if (pos > 0) {
  753. i = intrusive_heap::ParentIndex(pos);
  754. child_greater_eq_parent = !Less(pos, i);
  755. }
  756. if (child_greater_eq_parent) {
  757. i = MoveHoleUpAndFill(pos, std::move_if_noexcept(impl_.heap_[pos]));
  758. } else {
  759. i = MoveHoleDownAndFill<WithElement>(
  760. pos, std::move_if_noexcept(impl_.heap_[pos]));
  761. }
  762. return cbegin() + i;
  763. }
  764. template <typename T, typename Compare, typename HeapHandleAccessor>
  765. void IntrusiveHeap<T, Compare, HeapHandleAccessor>::swap(
  766. IntrusiveHeap& other) noexcept {
  767. std::swap(impl_.get_value_compare(), other.impl_.get_value_compare());
  768. std::swap(impl_.get_heap_handle_access(),
  769. other.impl_.get_heap_handle_access());
  770. std::swap(impl_.heap_, other.impl_.heap_);
  771. }
  772. template <typename T, typename Compare, typename HeapHandleAccessor>
  773. typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::size_type
  774. IntrusiveHeap<T, Compare, HeapHandleAccessor>::ToIndex(const_iterator pos) {
  775. DCHECK(cbegin() <= pos);
  776. DCHECK(pos <= cend());
  777. if (pos == cend())
  778. return HeapHandle::kInvalidIndex;
  779. return pos - cbegin();
  780. }
  781. template <typename T, typename Compare, typename HeapHandleAccessor>
  782. typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::size_type
  783. IntrusiveHeap<T, Compare, HeapHandleAccessor>::ToIndex(
  784. const_reverse_iterator pos) {
  785. DCHECK(crbegin() <= pos);
  786. DCHECK(pos <= crend());
  787. if (pos == crend())
  788. return HeapHandle::kInvalidIndex;
  789. return (pos.base() - cbegin()) - 1;
  790. }
  791. template <typename T, typename Compare, typename HeapHandleAccessor>
  792. void IntrusiveHeap<T, Compare, HeapHandleAccessor>::SetHeapHandle(size_type i) {
  793. impl_.get_heap_handle_access().SetHeapHandle(&impl_.heap_[i], HeapHandle(i));
  794. intrusive_heap::CheckInvalidOrEqualTo(GetHeapHandle(i), i);
  795. }
  796. template <typename T, typename Compare, typename HeapHandleAccessor>
  797. void IntrusiveHeap<T, Compare, HeapHandleAccessor>::ClearHeapHandle(
  798. size_type i) {
  799. impl_.get_heap_handle_access().ClearHeapHandle(&impl_.heap_[i]);
  800. DCHECK(!GetHeapHandle(i).IsValid());
  801. }
  802. template <typename T, typename Compare, typename HeapHandleAccessor>
  803. HeapHandle IntrusiveHeap<T, Compare, HeapHandleAccessor>::GetHeapHandle(
  804. size_type i) {
  805. return impl_.get_heap_handle_access().GetHeapHandle(&impl_.heap_[i]);
  806. }
  807. template <typename T, typename Compare, typename HeapHandleAccessor>
  808. bool IntrusiveHeap<T, Compare, HeapHandleAccessor>::Less(size_type i,
  809. size_type j) {
  810. DCHECK_LT(i, size());
  811. DCHECK_LT(j, size());
  812. return impl_.get_value_compare()(impl_.heap_[i], impl_.heap_[j]);
  813. }
  814. template <typename T, typename Compare, typename HeapHandleAccessor>
  815. bool IntrusiveHeap<T, Compare, HeapHandleAccessor>::Less(const T& element,
  816. size_type i) {
  817. DCHECK_LT(i, size());
  818. return impl_.get_value_compare()(element, impl_.heap_[i]);
  819. }
  820. template <typename T, typename Compare, typename HeapHandleAccessor>
  821. bool IntrusiveHeap<T, Compare, HeapHandleAccessor>::Less(size_type i,
  822. const T& element) {
  823. DCHECK_LT(i, size());
  824. return impl_.get_value_compare()(impl_.heap_[i], element);
  825. }
  826. template <typename T, typename Compare, typename HeapHandleAccessor>
  827. void IntrusiveHeap<T, Compare, HeapHandleAccessor>::MakeHole(size_type pos) {
  828. DCHECK_LT(pos, size());
  829. ClearHeapHandle(pos);
  830. }
  831. template <typename T, typename Compare, typename HeapHandleAccessor>
  832. template <typename U>
  833. void IntrusiveHeap<T, Compare, HeapHandleAccessor>::FillHole(size_type hole_pos,
  834. U element) {
  835. // The hole that we're filling may not yet exist. This can occur when
  836. // inserting a new element into the heap.
  837. DCHECK_LE(hole_pos, size());
  838. if (hole_pos == size()) {
  839. impl_.heap_.push_back(std::move_if_noexcept(element));
  840. } else {
  841. impl_.heap_[hole_pos] = std::move_if_noexcept(element);
  842. }
  843. SetHeapHandle(hole_pos);
  844. }
  845. template <typename T, typename Compare, typename HeapHandleAccessor>
  846. void IntrusiveHeap<T, Compare, HeapHandleAccessor>::MoveHole(
  847. size_type new_hole_pos,
  848. size_type old_hole_pos) {
  849. // The old hole position may be one past the end. This occurs when a new
  850. // element is being added.
  851. DCHECK_NE(new_hole_pos, old_hole_pos);
  852. DCHECK_LT(new_hole_pos, size());
  853. DCHECK_LE(old_hole_pos, size());
  854. if (old_hole_pos == size()) {
  855. impl_.heap_.push_back(std::move_if_noexcept(impl_.heap_[new_hole_pos]));
  856. } else {
  857. impl_.heap_[old_hole_pos] =
  858. std::move_if_noexcept(impl_.heap_[new_hole_pos]);
  859. }
  860. SetHeapHandle(old_hole_pos);
  861. }
  862. template <typename T, typename Compare, typename HeapHandleAccessor>
  863. template <typename U>
  864. typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::size_type
  865. IntrusiveHeap<T, Compare, HeapHandleAccessor>::MoveHoleUpAndFill(
  866. size_type hole_pos,
  867. U element) {
  868. // Moving 1 spot beyond the end is fine. This happens when we insert a new
  869. // element.
  870. DCHECK_LE(hole_pos, size());
  871. // Stop when the element is as far up as it can go.
  872. while (hole_pos != 0) {
  873. // If our parent is >= to us, we can stop.
  874. size_type parent = intrusive_heap::ParentIndex(hole_pos);
  875. if (!Less(parent, element))
  876. break;
  877. MoveHole(parent, hole_pos);
  878. hole_pos = parent;
  879. }
  880. FillHole(hole_pos, std::move_if_noexcept(element));
  881. return hole_pos;
  882. }
  883. template <typename T, typename Compare, typename HeapHandleAccessor>
  884. template <typename FillElementType, typename U>
  885. typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::size_type
  886. IntrusiveHeap<T, Compare, HeapHandleAccessor>::MoveHoleDownAndFill(
  887. size_type hole_pos,
  888. U element) {
  889. DCHECK_LT(hole_pos, size());
  890. // If we're filling with a leaf, then that leaf element is about to be erased.
  891. // We pretend that the space doesn't exist in the heap.
  892. const size_type n = size() - (FillElementType::kIsLeafElement ? 1 : 0);
  893. DCHECK_LT(hole_pos, n);
  894. DCHECK(!GetHeapHandle(hole_pos).IsValid());
  895. while (true) {
  896. // If this spot has no children, then we've gone down as far as we can go.
  897. size_type left = intrusive_heap::LeftIndex(hole_pos);
  898. if (left >= n)
  899. break;
  900. size_type right = left + 1;
  901. // Get the larger of the potentially two child nodes.
  902. size_type largest = left;
  903. if (right < n && Less(left, right))
  904. largest = right;
  905. // If we're not deterministically moving the element all the way down to
  906. // become a leaf, then stop when it is >= the largest of the children.
  907. if (!FillElementType::kIsLeafElement && !Less(element, largest))
  908. break;
  909. MoveHole(largest, hole_pos);
  910. hole_pos = largest;
  911. }
  912. if (FillElementType::kIsLeafElement) {
  913. // If we're filling with a leaf node we may need to bubble the leaf back up
  914. // the tree a bit to repair the heap.
  915. hole_pos = MoveHoleUpAndFill(hole_pos, std::move_if_noexcept(element));
  916. } else {
  917. FillHole(hole_pos, std::move_if_noexcept(element));
  918. }
  919. return hole_pos;
  920. }
  921. template <typename T, typename Compare, typename HeapHandleAccessor>
  922. template <typename U>
  923. typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::const_iterator
  924. IntrusiveHeap<T, Compare, HeapHandleAccessor>::InsertImpl(U element) {
  925. // MoveHoleUpAndFill can tolerate the initial hole being in a slot that
  926. // doesn't yet exist. It will be created by MoveHole by copy/move, thus
  927. // removing the need for a default constructor.
  928. size_type i = MoveHoleUpAndFill(size(), std::move_if_noexcept(element));
  929. return cbegin() + static_cast<difference_type>(i);
  930. }
  931. template <typename T, typename Compare, typename HeapHandleAccessor>
  932. template <typename U>
  933. typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::const_iterator
  934. IntrusiveHeap<T, Compare, HeapHandleAccessor>::ReplaceImpl(size_type pos,
  935. U element) {
  936. // If we're greater than our parent we need to go up, otherwise we may need
  937. // to go down.
  938. MakeHole(pos);
  939. size_type i = 0;
  940. if (!Less(element, pos)) {
  941. i = MoveHoleUpAndFill(pos, std::move_if_noexcept(element));
  942. } else {
  943. i = MoveHoleDownAndFill<WithElement>(pos, std::move_if_noexcept(element));
  944. }
  945. return cbegin() + static_cast<difference_type>(i);
  946. }
  947. template <typename T, typename Compare, typename HeapHandleAccessor>
  948. template <typename U>
  949. typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::const_iterator
  950. IntrusiveHeap<T, Compare, HeapHandleAccessor>::ReplaceTopImpl(U element) {
  951. MakeHole(0u);
  952. size_type i =
  953. MoveHoleDownAndFill<WithElement>(0u, std::move_if_noexcept(element));
  954. return cbegin() + static_cast<difference_type>(i);
  955. }
  956. ////////////////////////////////////////////////////////////////////////////////
  957. // WithHeapHandle
  958. template <typename T>
  959. template <class... Args>
  960. WithHeapHandle<T>::WithHeapHandle(Args&&... args)
  961. : value_(std::forward<Args>(args)...) {}
  962. template <typename T>
  963. void WithHeapHandle<T>::swap(WithHeapHandle& other) noexcept {
  964. InternalHeapHandleStorage::swap(other);
  965. std::swap(value_, other.value_);
  966. }
  967. } // namespace base
  968. #endif // BASE_CONTAINERS_INTRUSIVE_HEAP_H_