flat_tree.h 39 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107
  1. // Copyright 2017 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_FLAT_TREE_H_
  5. #define BASE_CONTAINERS_FLAT_TREE_H_
  6. #include <algorithm>
  7. #include <array>
  8. #include <initializer_list>
  9. #include <iterator>
  10. #include <type_traits>
  11. #include <utility>
  12. #include "base/as_const.h"
  13. #include "base/check.h"
  14. #include "base/compiler_specific.h"
  15. #include "base/functional/not_fn.h"
  16. #include "base/ranges/algorithm.h"
  17. namespace base {
  18. // Tag type that allows skipping the sort_and_unique step when constructing a
  19. // flat_tree in case the underlying container is already sorted and has no
  20. // duplicate elements.
  21. struct sorted_unique_t {
  22. constexpr explicit sorted_unique_t() = default;
  23. };
  24. extern sorted_unique_t sorted_unique;
  25. namespace internal {
  26. // Helper functions used in DCHECKs below to make sure that inputs tagged with
  27. // sorted_unique are indeed sorted and unique.
  28. template <typename Range, typename Comp>
  29. constexpr bool is_sorted_and_unique(const Range& range, Comp comp) {
  30. // Being unique implies that there are no adjacent elements that
  31. // compare equal. So this checks that each element is strictly less
  32. // than the element after it.
  33. return ranges::adjacent_find(range, base::not_fn(comp)) == ranges::end(range);
  34. }
  35. // This is a convenience trait inheriting from std::true_type if Iterator is at
  36. // least a ForwardIterator and thus supports multiple passes over a range.
  37. template <class Iterator>
  38. using is_multipass = std::is_base_of<
  39. std::forward_iterator_tag,
  40. typename std::iterator_traits<Iterator>::iterator_category>;
  41. // Uses SFINAE to detect whether type has is_transparent member.
  42. template <typename T, typename = void>
  43. struct IsTransparentCompare : std::false_type {};
  44. template <typename T>
  45. struct IsTransparentCompare<T, std::void_t<typename T::is_transparent>>
  46. : std::true_type {};
  47. // Helper inspired by C++20's std::to_array to convert a C-style array to a
  48. // std::array. As opposed to the C++20 version this implementation does not
  49. // provide an overload for rvalues and does not strip cv qualifers from the
  50. // returned std::array::value_type. The returned value_type needs to be
  51. // specified explicitly, allowing the construction of std::arrays with const
  52. // elements.
  53. //
  54. // Reference: https://en.cppreference.com/w/cpp/container/array/to_array
  55. template <typename U, typename T, size_t N, size_t... I>
  56. constexpr std::array<U, N> ToArrayImpl(const T (&data)[N],
  57. std::index_sequence<I...>) {
  58. return {{data[I]...}};
  59. }
  60. template <typename U, typename T, size_t N>
  61. constexpr std::array<U, N> ToArray(const T (&data)[N]) {
  62. return ToArrayImpl<U>(data, std::make_index_sequence<N>());
  63. }
  64. // Helper that calls `container.reserve(std::size(source))`.
  65. template <typename T, typename U>
  66. constexpr void ReserveIfSupported(const T&, const U&) {}
  67. template <typename T, typename U>
  68. auto ReserveIfSupported(T& container, const U& source)
  69. -> decltype(container.reserve(std::size(source)), void()) {
  70. container.reserve(std::size(source));
  71. }
  72. // std::pair's operator= is not constexpr prior to C++20. Thus we need this
  73. // small helper to invoke operator= on the .first and .second member explicitly.
  74. template <typename T>
  75. constexpr void Assign(T& lhs, T&& rhs) {
  76. lhs = std::move(rhs);
  77. }
  78. template <typename T, typename U>
  79. constexpr void Assign(std::pair<T, U>& lhs, std::pair<T, U>&& rhs) {
  80. Assign(lhs.first, std::move(rhs.first));
  81. Assign(lhs.second, std::move(rhs.second));
  82. }
  83. // constexpr swap implementation. std::swap is not constexpr prior to C++20.
  84. template <typename T>
  85. constexpr void Swap(T& lhs, T& rhs) {
  86. T tmp = std::move(lhs);
  87. Assign(lhs, std::move(rhs));
  88. Assign(rhs, std::move(tmp));
  89. }
  90. // constexpr prev implementation. std::prev is not constexpr prior to C++17.
  91. template <typename BidirIt>
  92. constexpr BidirIt Prev(BidirIt it) {
  93. return --it;
  94. }
  95. // constexpr next implementation. std::next is not constexpr prior to C++17.
  96. template <typename InputIt>
  97. constexpr InputIt Next(InputIt it) {
  98. return ++it;
  99. }
  100. // constexpr sort implementation. std::sort is not constexpr prior to C++20.
  101. // While insertion sort has a quadratic worst case complexity, it was chosen
  102. // because it has linear complexity for nearly sorted data, is stable, and
  103. // simple to implement.
  104. template <typename BidirIt, typename Compare>
  105. constexpr void InsertionSort(BidirIt first, BidirIt last, const Compare& comp) {
  106. if (first == last)
  107. return;
  108. for (auto it = Next(first); it != last; ++it) {
  109. for (auto curr = it; curr != first && comp(*curr, *Prev(curr)); --curr)
  110. Swap(*curr, *Prev(curr));
  111. }
  112. }
  113. // Implementation -------------------------------------------------------------
  114. // Implementation for the sorted associative flat_set and flat_map using a
  115. // sorted vector as the backing store. Do not use directly.
  116. //
  117. // The use of "value" in this is like std::map uses, meaning it's the thing
  118. // contained (in the case of map it's a <Key, Mapped> pair). The Key is how
  119. // things are looked up. In the case of a set, Key == Value. In the case of
  120. // a map, the Key is a component of a Value.
  121. //
  122. // The helper class GetKeyFromValue provides the means to extract a key from a
  123. // value for comparison purposes. It should implement:
  124. // const Key& operator()(const Value&).
  125. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  126. class flat_tree {
  127. public:
  128. // --------------------------------------------------------------------------
  129. // Types.
  130. //
  131. using key_type = Key;
  132. using key_compare = KeyCompare;
  133. using value_type = typename Container::value_type;
  134. // Wraps the templated key comparison to compare values.
  135. struct value_compare {
  136. constexpr bool operator()(const value_type& left,
  137. const value_type& right) const {
  138. GetKeyFromValue extractor;
  139. return comp(extractor(left), extractor(right));
  140. }
  141. NO_UNIQUE_ADDRESS key_compare comp;
  142. };
  143. using pointer = typename Container::pointer;
  144. using const_pointer = typename Container::const_pointer;
  145. using reference = typename Container::reference;
  146. using const_reference = typename Container::const_reference;
  147. using size_type = typename Container::size_type;
  148. using difference_type = typename Container::difference_type;
  149. using iterator = typename Container::iterator;
  150. using const_iterator = typename Container::const_iterator;
  151. using reverse_iterator = typename Container::reverse_iterator;
  152. using const_reverse_iterator = typename Container::const_reverse_iterator;
  153. using container_type = Container;
  154. // --------------------------------------------------------------------------
  155. // Lifetime.
  156. //
  157. // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity
  158. // and take O(N * log(N)) + O(N) if extra memory is available (N is a range
  159. // length).
  160. //
  161. // Assume that move constructors invalidate iterators and references.
  162. //
  163. // The constructors that take ranges, lists, and vectors do not require that
  164. // the input be sorted.
  165. //
  166. // When passing the base::sorted_unique tag as the first argument no sort and
  167. // unique step takes places. This is useful if the underlying container
  168. // already has the required properties.
  169. flat_tree() = default;
  170. flat_tree(const flat_tree&) = default;
  171. flat_tree(flat_tree&&) = default;
  172. explicit flat_tree(const key_compare& comp);
  173. template <class InputIterator>
  174. flat_tree(InputIterator first,
  175. InputIterator last,
  176. const key_compare& comp = key_compare());
  177. flat_tree(const container_type& items,
  178. const key_compare& comp = key_compare());
  179. flat_tree(container_type&& items, const key_compare& comp = key_compare());
  180. flat_tree(std::initializer_list<value_type> ilist,
  181. const key_compare& comp = key_compare());
  182. template <class InputIterator>
  183. flat_tree(sorted_unique_t,
  184. InputIterator first,
  185. InputIterator last,
  186. const key_compare& comp = key_compare());
  187. flat_tree(sorted_unique_t,
  188. const container_type& items,
  189. const key_compare& comp = key_compare());
  190. constexpr flat_tree(sorted_unique_t,
  191. container_type&& items,
  192. const key_compare& comp = key_compare());
  193. flat_tree(sorted_unique_t,
  194. std::initializer_list<value_type> ilist,
  195. const key_compare& comp = key_compare());
  196. ~flat_tree() = default;
  197. // --------------------------------------------------------------------------
  198. // Assignments.
  199. //
  200. // Assume that move assignment invalidates iterators and references.
  201. flat_tree& operator=(const flat_tree&) = default;
  202. flat_tree& operator=(flat_tree&&) = default;
  203. // Takes the first if there are duplicates in the initializer list.
  204. flat_tree& operator=(std::initializer_list<value_type> ilist);
  205. // --------------------------------------------------------------------------
  206. // Memory management.
  207. //
  208. // Beware that shrink_to_fit() simply forwards the request to the
  209. // container_type and its implementation is free to optimize otherwise and
  210. // leave capacity() to be greater that its size.
  211. //
  212. // reserve() and shrink_to_fit() invalidate iterators and references.
  213. void reserve(size_type new_capacity);
  214. size_type capacity() const;
  215. void shrink_to_fit();
  216. // --------------------------------------------------------------------------
  217. // Size management.
  218. //
  219. // clear() leaves the capacity() of the flat_tree unchanged.
  220. void clear();
  221. constexpr size_type size() const;
  222. constexpr size_type max_size() const;
  223. constexpr bool empty() const;
  224. // --------------------------------------------------------------------------
  225. // Iterators.
  226. //
  227. // Iterators follow the ordering defined by the key comparator used in
  228. // construction of the flat_tree.
  229. iterator begin();
  230. constexpr const_iterator begin() const;
  231. const_iterator cbegin() const;
  232. iterator end();
  233. constexpr const_iterator end() const;
  234. const_iterator cend() const;
  235. reverse_iterator rbegin();
  236. const_reverse_iterator rbegin() const;
  237. const_reverse_iterator crbegin() const;
  238. reverse_iterator rend();
  239. const_reverse_iterator rend() const;
  240. const_reverse_iterator crend() const;
  241. // --------------------------------------------------------------------------
  242. // Insert operations.
  243. //
  244. // Assume that every operation invalidates iterators and references.
  245. // Insertion of one element can take O(size). Capacity of flat_tree grows in
  246. // an implementation-defined manner.
  247. //
  248. // NOTE: Prefer to build a new flat_tree from a std::vector (or similar)
  249. // instead of calling insert() repeatedly.
  250. std::pair<iterator, bool> insert(const value_type& val);
  251. std::pair<iterator, bool> insert(value_type&& val);
  252. iterator insert(const_iterator position_hint, const value_type& x);
  253. iterator insert(const_iterator position_hint, value_type&& x);
  254. // This method inserts the values from the range [first, last) into the
  255. // current tree.
  256. template <class InputIterator>
  257. void insert(InputIterator first, InputIterator last);
  258. template <class... Args>
  259. std::pair<iterator, bool> emplace(Args&&... args);
  260. template <class... Args>
  261. iterator emplace_hint(const_iterator position_hint, Args&&... args);
  262. // --------------------------------------------------------------------------
  263. // Underlying type operations.
  264. //
  265. // Assume that either operation invalidates iterators and references.
  266. // Extracts the container_type and returns it to the caller. Ensures that
  267. // `this` is `empty()` afterwards.
  268. container_type extract() &&;
  269. // Replaces the container_type with `body`. Expects that `body` is sorted
  270. // and has no repeated elements with regard to value_comp().
  271. void replace(container_type&& body);
  272. // --------------------------------------------------------------------------
  273. // Erase operations.
  274. //
  275. // Assume that every operation invalidates iterators and references.
  276. //
  277. // erase(position), erase(first, last) can take O(size).
  278. // erase(key) may take O(size) + O(log(size)).
  279. //
  280. // Prefer base::EraseIf() or some other variation on erase(remove(), end())
  281. // idiom when deleting multiple non-consecutive elements.
  282. iterator erase(iterator position);
  283. // Artificially templatized to break ambiguity if `iterator` and
  284. // `const_iterator` are the same type.
  285. template <typename DummyT = void>
  286. iterator erase(const_iterator position);
  287. iterator erase(const_iterator first, const_iterator last);
  288. template <typename K>
  289. size_type erase(const K& key);
  290. // --------------------------------------------------------------------------
  291. // Comparators.
  292. constexpr key_compare key_comp() const;
  293. constexpr value_compare value_comp() const;
  294. // --------------------------------------------------------------------------
  295. // Search operations.
  296. //
  297. // Search operations have O(log(size)) complexity.
  298. template <typename K>
  299. size_type count(const K& key) const;
  300. template <typename K>
  301. iterator find(const K& key);
  302. template <typename K>
  303. const_iterator find(const K& key) const;
  304. template <typename K>
  305. bool contains(const K& key) const;
  306. template <typename K>
  307. std::pair<iterator, iterator> equal_range(const K& key);
  308. template <typename K>
  309. std::pair<const_iterator, const_iterator> equal_range(const K& key) const;
  310. template <typename K>
  311. iterator lower_bound(const K& key);
  312. template <typename K>
  313. const_iterator lower_bound(const K& key) const;
  314. template <typename K>
  315. iterator upper_bound(const K& key);
  316. template <typename K>
  317. const_iterator upper_bound(const K& key) const;
  318. // --------------------------------------------------------------------------
  319. // General operations.
  320. //
  321. // Assume that swap invalidates iterators and references.
  322. //
  323. // Implementation note: currently we use operator==() and operator<() on
  324. // std::vector, because they have the same contract we need, so we use them
  325. // directly for brevity and in case it is more optimal than calling equal()
  326. // and lexicograhpical_compare(). If the underlying container type is changed,
  327. // this code may need to be modified.
  328. void swap(flat_tree& other) noexcept;
  329. friend bool operator==(const flat_tree& lhs, const flat_tree& rhs) {
  330. return lhs.body_ == rhs.body_;
  331. }
  332. friend bool operator!=(const flat_tree& lhs, const flat_tree& rhs) {
  333. return !(lhs == rhs);
  334. }
  335. friend bool operator<(const flat_tree& lhs, const flat_tree& rhs) {
  336. return lhs.body_ < rhs.body_;
  337. }
  338. friend bool operator>(const flat_tree& lhs, const flat_tree& rhs) {
  339. return rhs < lhs;
  340. }
  341. friend bool operator>=(const flat_tree& lhs, const flat_tree& rhs) {
  342. return !(lhs < rhs);
  343. }
  344. friend bool operator<=(const flat_tree& lhs, const flat_tree& rhs) {
  345. return !(lhs > rhs);
  346. }
  347. friend void swap(flat_tree& lhs, flat_tree& rhs) noexcept { lhs.swap(rhs); }
  348. protected:
  349. // Emplaces a new item into the tree that is known not to be in it. This
  350. // is for implementing map operator[].
  351. template <class... Args>
  352. iterator unsafe_emplace(const_iterator position, Args&&... args);
  353. // Attempts to emplace a new element with key |key|. Only if |key| is not yet
  354. // present, construct value_type from |args| and insert it. Returns an
  355. // iterator to the element with key |key| and a bool indicating whether an
  356. // insertion happened.
  357. template <class K, class... Args>
  358. std::pair<iterator, bool> emplace_key_args(const K& key, Args&&... args);
  359. // Similar to |emplace_key_args|, but checks |hint| first as a possible
  360. // insertion position.
  361. template <class K, class... Args>
  362. std::pair<iterator, bool> emplace_hint_key_args(const_iterator hint,
  363. const K& key,
  364. Args&&... args);
  365. private:
  366. // Helper class for e.g. lower_bound that can compare a value on the left
  367. // to a key on the right.
  368. struct KeyValueCompare {
  369. // The key comparison object must outlive this class.
  370. explicit KeyValueCompare(const key_compare& comp) : comp_(comp) {}
  371. template <typename T, typename U>
  372. bool operator()(const T& lhs, const U& rhs) const {
  373. return comp_(extract_if_value_type(lhs), extract_if_value_type(rhs));
  374. }
  375. private:
  376. const key_type& extract_if_value_type(const value_type& v) const {
  377. GetKeyFromValue extractor;
  378. return extractor(v);
  379. }
  380. template <typename K>
  381. const K& extract_if_value_type(const K& k) const {
  382. return k;
  383. }
  384. const key_compare& comp_;
  385. };
  386. iterator const_cast_it(const_iterator c_it) {
  387. auto distance = std::distance(cbegin(), c_it);
  388. return std::next(begin(), distance);
  389. }
  390. // This method is inspired by both std::map::insert(P&&) and
  391. // std::map::insert_or_assign(const K&, V&&). It inserts val if an equivalent
  392. // element is not present yet, otherwise it overwrites. It returns an iterator
  393. // to the modified element and a flag indicating whether insertion or
  394. // assignment happened.
  395. template <class V>
  396. std::pair<iterator, bool> insert_or_assign(V&& val) {
  397. auto position = lower_bound(GetKeyFromValue()(val));
  398. if (position == end() || value_comp()(val, *position))
  399. return {body_.emplace(position, std::forward<V>(val)), true};
  400. *position = std::forward<V>(val);
  401. return {position, false};
  402. }
  403. // This method is similar to insert_or_assign, with the following differences:
  404. // - Instead of searching [begin(), end()) it only searches [first, last).
  405. // - In case no equivalent element is found, val is appended to the end of the
  406. // underlying body and an iterator to the next bigger element in [first,
  407. // last) is returned.
  408. template <class V>
  409. std::pair<iterator, bool> append_or_assign(iterator first,
  410. iterator last,
  411. V&& val) {
  412. auto position = std::lower_bound(first, last, val, value_comp());
  413. if (position == last || value_comp()(val, *position)) {
  414. // emplace_back might invalidate position, which is why distance needs to
  415. // be cached.
  416. const difference_type distance = std::distance(begin(), position);
  417. body_.emplace_back(std::forward<V>(val));
  418. return {std::next(begin(), distance), true};
  419. }
  420. *position = std::forward<V>(val);
  421. return {position, false};
  422. }
  423. // This method is similar to insert, with the following differences:
  424. // - Instead of searching [begin(), end()) it only searches [first, last).
  425. // - In case no equivalent element is found, val is appended to the end of the
  426. // underlying body and an iterator to the next bigger element in [first,
  427. // last) is returned.
  428. template <class V>
  429. std::pair<iterator, bool> append_unique(iterator first,
  430. iterator last,
  431. V&& val) {
  432. auto position = std::lower_bound(first, last, val, value_comp());
  433. if (position == last || value_comp()(val, *position)) {
  434. // emplace_back might invalidate position, which is why distance needs to
  435. // be cached.
  436. const difference_type distance = std::distance(begin(), position);
  437. body_.emplace_back(std::forward<V>(val));
  438. return {std::next(begin(), distance), true};
  439. }
  440. return {position, false};
  441. }
  442. void sort_and_unique(iterator first, iterator last) {
  443. // Preserve stability for the unique code below.
  444. std::stable_sort(first, last, value_comp());
  445. // lhs is already <= rhs due to sort, therefore !(lhs < rhs) <=> lhs == rhs.
  446. auto equal_comp = base::not_fn(value_comp());
  447. erase(std::unique(first, last, equal_comp), last);
  448. }
  449. void sort_and_unique() { sort_and_unique(begin(), end()); }
  450. // To support comparators that may not be possible to default-construct, we
  451. // have to store an instance of Compare. Since Compare commonly is stateless,
  452. // we use the NO_UNIQUE_ADDRESS attribute to save space.
  453. NO_UNIQUE_ADDRESS key_compare comp_;
  454. // Declare after |key_compare_comp_| to workaround GCC ICE. For details
  455. // see https://crbug.com/1156268
  456. container_type body_;
  457. // If the compare is not transparent we want to construct key_type once.
  458. template <typename K>
  459. using KeyTypeOrK = typename std::
  460. conditional<IsTransparentCompare<key_compare>::value, K, key_type>::type;
  461. };
  462. // ----------------------------------------------------------------------------
  463. // Lifetime.
  464. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  465. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
  466. const KeyCompare& comp)
  467. : comp_(comp) {}
  468. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  469. template <class InputIterator>
  470. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
  471. InputIterator first,
  472. InputIterator last,
  473. const KeyCompare& comp)
  474. : comp_(comp), body_(first, last) {
  475. sort_and_unique();
  476. }
  477. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  478. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
  479. const container_type& items,
  480. const KeyCompare& comp)
  481. : comp_(comp), body_(items) {
  482. sort_and_unique();
  483. }
  484. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  485. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
  486. container_type&& items,
  487. const KeyCompare& comp)
  488. : comp_(comp), body_(std::move(items)) {
  489. sort_and_unique();
  490. }
  491. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  492. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
  493. std::initializer_list<value_type> ilist,
  494. const KeyCompare& comp)
  495. : flat_tree(std::begin(ilist), std::end(ilist), comp) {}
  496. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  497. template <class InputIterator>
  498. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
  499. sorted_unique_t,
  500. InputIterator first,
  501. InputIterator last,
  502. const KeyCompare& comp)
  503. : comp_(comp), body_(first, last) {
  504. DCHECK(is_sorted_and_unique(*this, value_comp()));
  505. }
  506. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  507. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
  508. sorted_unique_t,
  509. const container_type& items,
  510. const KeyCompare& comp)
  511. : comp_(comp), body_(items) {
  512. DCHECK(is_sorted_and_unique(*this, value_comp()));
  513. }
  514. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  515. constexpr flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
  516. sorted_unique_t,
  517. container_type&& items,
  518. const KeyCompare& comp)
  519. : comp_(comp), body_(std::move(items)) {
  520. DCHECK(is_sorted_and_unique(*this, value_comp()));
  521. }
  522. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  523. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree(
  524. sorted_unique_t,
  525. std::initializer_list<value_type> ilist,
  526. const KeyCompare& comp)
  527. : flat_tree(sorted_unique, std::begin(ilist), std::end(ilist), comp) {}
  528. // ----------------------------------------------------------------------------
  529. // Assignments.
  530. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  531. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::operator=(
  532. std::initializer_list<value_type> ilist) -> flat_tree& {
  533. body_ = ilist;
  534. sort_and_unique();
  535. return *this;
  536. }
  537. // ----------------------------------------------------------------------------
  538. // Memory management.
  539. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  540. void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::reserve(
  541. size_type new_capacity) {
  542. body_.reserve(new_capacity);
  543. }
  544. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  545. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::capacity() const
  546. -> size_type {
  547. return body_.capacity();
  548. }
  549. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  550. void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::shrink_to_fit() {
  551. body_.shrink_to_fit();
  552. }
  553. // ----------------------------------------------------------------------------
  554. // Size management.
  555. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  556. void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::clear() {
  557. body_.clear();
  558. }
  559. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  560. constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::size()
  561. const -> size_type {
  562. return body_.size();
  563. }
  564. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  565. constexpr auto
  566. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::max_size() const
  567. -> size_type {
  568. return body_.max_size();
  569. }
  570. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  571. constexpr bool flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::empty()
  572. const {
  573. return body_.empty();
  574. }
  575. // ----------------------------------------------------------------------------
  576. // Iterators.
  577. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  578. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::begin()
  579. -> iterator {
  580. return body_.begin();
  581. }
  582. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  583. constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::begin()
  584. const -> const_iterator {
  585. return ranges::begin(body_);
  586. }
  587. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  588. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::cbegin() const
  589. -> const_iterator {
  590. return body_.cbegin();
  591. }
  592. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  593. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::end() -> iterator {
  594. return body_.end();
  595. }
  596. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  597. constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::end()
  598. const -> const_iterator {
  599. return ranges::end(body_);
  600. }
  601. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  602. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::cend() const
  603. -> const_iterator {
  604. return body_.cend();
  605. }
  606. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  607. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rbegin()
  608. -> reverse_iterator {
  609. return body_.rbegin();
  610. }
  611. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  612. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rbegin() const
  613. -> const_reverse_iterator {
  614. return body_.rbegin();
  615. }
  616. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  617. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::crbegin() const
  618. -> const_reverse_iterator {
  619. return body_.crbegin();
  620. }
  621. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  622. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rend()
  623. -> reverse_iterator {
  624. return body_.rend();
  625. }
  626. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  627. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rend() const
  628. -> const_reverse_iterator {
  629. return body_.rend();
  630. }
  631. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  632. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::crend() const
  633. -> const_reverse_iterator {
  634. return body_.crend();
  635. }
  636. // ----------------------------------------------------------------------------
  637. // Insert operations.
  638. //
  639. // Currently we use position_hint the same way as eastl or boost:
  640. // https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set.h#L493
  641. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  642. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
  643. const value_type& val) -> std::pair<iterator, bool> {
  644. return emplace_key_args(GetKeyFromValue()(val), val);
  645. }
  646. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  647. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
  648. value_type&& val) -> std::pair<iterator, bool> {
  649. return emplace_key_args(GetKeyFromValue()(val), std::move(val));
  650. }
  651. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  652. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
  653. const_iterator position_hint,
  654. const value_type& val) -> iterator {
  655. return emplace_hint_key_args(position_hint, GetKeyFromValue()(val), val)
  656. .first;
  657. }
  658. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  659. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
  660. const_iterator position_hint,
  661. value_type&& val) -> iterator {
  662. return emplace_hint_key_args(position_hint, GetKeyFromValue()(val),
  663. std::move(val))
  664. .first;
  665. }
  666. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  667. template <class InputIterator>
  668. void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert(
  669. InputIterator first,
  670. InputIterator last) {
  671. if (first == last)
  672. return;
  673. // Dispatch to single element insert if the input range contains a single
  674. // element.
  675. if (is_multipass<InputIterator>() && std::next(first) == last) {
  676. insert(end(), *first);
  677. return;
  678. }
  679. // Provide a convenience lambda to obtain an iterator pointing past the last
  680. // old element. This needs to be dymanic due to possible re-allocations.
  681. auto middle = [this, size = size()] {
  682. return std::next(begin(), static_cast<difference_type>(size));
  683. };
  684. // For batch updates initialize the first insertion point.
  685. auto pos_first_new = static_cast<difference_type>(size());
  686. // Loop over the input range while appending new values and overwriting
  687. // existing ones, if applicable. Keep track of the first insertion point.
  688. for (; first != last; ++first) {
  689. std::pair<iterator, bool> result = append_unique(begin(), middle(), *first);
  690. if (result.second) {
  691. pos_first_new =
  692. std::min(pos_first_new, std::distance(begin(), result.first));
  693. }
  694. }
  695. // The new elements might be unordered and contain duplicates, so post-process
  696. // the just inserted elements and merge them with the rest, inserting them at
  697. // the previously found spot.
  698. sort_and_unique(middle(), end());
  699. std::inplace_merge(std::next(begin(), pos_first_new), middle(), end(),
  700. value_comp());
  701. }
  702. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  703. template <class... Args>
  704. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace(
  705. Args&&... args) -> std::pair<iterator, bool> {
  706. return insert(value_type(std::forward<Args>(args)...));
  707. }
  708. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  709. template <class... Args>
  710. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace_hint(
  711. const_iterator position_hint,
  712. Args&&... args) -> iterator {
  713. return insert(position_hint, value_type(std::forward<Args>(args)...));
  714. }
  715. // ----------------------------------------------------------------------------
  716. // Underlying type operations.
  717. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  718. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::
  719. extract() && -> container_type {
  720. return std::exchange(body_, container_type());
  721. }
  722. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  723. void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::replace(
  724. container_type&& body) {
  725. // Ensure that `body` is sorted and has no repeated elements according to
  726. // `value_comp()`.
  727. DCHECK(is_sorted_and_unique(body, value_comp()));
  728. body_ = std::move(body);
  729. }
  730. // ----------------------------------------------------------------------------
  731. // Erase operations.
  732. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  733. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(
  734. iterator position) -> iterator {
  735. CHECK(position != body_.end());
  736. return body_.erase(position);
  737. }
  738. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  739. template <typename DummyT>
  740. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(
  741. const_iterator position) -> iterator {
  742. CHECK(position != body_.end());
  743. return body_.erase(position);
  744. }
  745. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  746. template <typename K>
  747. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(const K& val)
  748. -> size_type {
  749. auto eq_range = equal_range(val);
  750. auto res =
  751. static_cast<size_type>(std::distance(eq_range.first, eq_range.second));
  752. erase(eq_range.first, eq_range.second);
  753. return res;
  754. }
  755. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  756. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(
  757. const_iterator first,
  758. const_iterator last) -> iterator {
  759. return body_.erase(first, last);
  760. }
  761. // ----------------------------------------------------------------------------
  762. // Comparators.
  763. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  764. constexpr auto
  765. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::key_comp() const
  766. -> key_compare {
  767. return comp_;
  768. }
  769. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  770. constexpr auto
  771. flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::value_comp() const
  772. -> value_compare {
  773. return value_compare{comp_};
  774. }
  775. // ----------------------------------------------------------------------------
  776. // Search operations.
  777. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  778. template <typename K>
  779. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::count(
  780. const K& key) const -> size_type {
  781. auto eq_range = equal_range(key);
  782. return static_cast<size_type>(std::distance(eq_range.first, eq_range.second));
  783. }
  784. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  785. template <typename K>
  786. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(const K& key)
  787. -> iterator {
  788. return const_cast_it(base::as_const(*this).find(key));
  789. }
  790. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  791. template <typename K>
  792. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(
  793. const K& key) const -> const_iterator {
  794. auto eq_range = equal_range(key);
  795. return (eq_range.first == eq_range.second) ? end() : eq_range.first;
  796. }
  797. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  798. template <typename K>
  799. bool flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::contains(
  800. const K& key) const {
  801. auto lower = lower_bound(key);
  802. return lower != end() && !comp_(key, GetKeyFromValue()(*lower));
  803. }
  804. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  805. template <typename K>
  806. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range(
  807. const K& key) -> std::pair<iterator, iterator> {
  808. auto res = base::as_const(*this).equal_range(key);
  809. return {const_cast_it(res.first), const_cast_it(res.second)};
  810. }
  811. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  812. template <typename K>
  813. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range(
  814. const K& key) const -> std::pair<const_iterator, const_iterator> {
  815. auto lower = lower_bound(key);
  816. KeyValueCompare comp(comp_);
  817. if (lower == end() || comp(key, *lower))
  818. return {lower, lower};
  819. return {lower, std::next(lower)};
  820. }
  821. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  822. template <typename K>
  823. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::lower_bound(
  824. const K& key) -> iterator {
  825. return const_cast_it(base::as_const(*this).lower_bound(key));
  826. }
  827. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  828. template <typename K>
  829. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::lower_bound(
  830. const K& key) const -> const_iterator {
  831. static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value,
  832. "Requested type cannot be bound to the container's key_type "
  833. "which is required for a non-transparent compare.");
  834. const KeyTypeOrK<K>& key_ref = key;
  835. KeyValueCompare comp(comp_);
  836. return ranges::lower_bound(*this, key_ref, comp);
  837. }
  838. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  839. template <typename K>
  840. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::upper_bound(
  841. const K& key) -> iterator {
  842. return const_cast_it(base::as_const(*this).upper_bound(key));
  843. }
  844. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  845. template <typename K>
  846. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::upper_bound(
  847. const K& key) const -> const_iterator {
  848. static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value,
  849. "Requested type cannot be bound to the container's key_type "
  850. "which is required for a non-transparent compare.");
  851. const KeyTypeOrK<K>& key_ref = key;
  852. KeyValueCompare comp(comp_);
  853. return ranges::upper_bound(*this, key_ref, comp);
  854. }
  855. // ----------------------------------------------------------------------------
  856. // General operations.
  857. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  858. void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::swap(
  859. flat_tree& other) noexcept {
  860. std::swap(*this, other);
  861. }
  862. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  863. template <class... Args>
  864. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::unsafe_emplace(
  865. const_iterator position,
  866. Args&&... args) -> iterator {
  867. return body_.emplace(position, std::forward<Args>(args)...);
  868. }
  869. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  870. template <class K, class... Args>
  871. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace_key_args(
  872. const K& key,
  873. Args&&... args) -> std::pair<iterator, bool> {
  874. auto lower = lower_bound(key);
  875. if (lower == end() || comp_(key, GetKeyFromValue()(*lower)))
  876. return {unsafe_emplace(lower, std::forward<Args>(args)...), true};
  877. return {lower, false};
  878. }
  879. template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
  880. template <class K, class... Args>
  881. auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::
  882. emplace_hint_key_args(const_iterator hint, const K& key, Args&&... args)
  883. -> std::pair<iterator, bool> {
  884. KeyValueCompare comp(comp_);
  885. if ((hint == begin() || comp(*std::prev(hint), key))) {
  886. if (hint == end() || comp(key, *hint)) {
  887. // *(hint - 1) < key < *hint => key did not exist and hint is correct.
  888. return {unsafe_emplace(hint, std::forward<Args>(args)...), true};
  889. }
  890. if (!comp(*hint, key)) {
  891. // key == *hint => no-op, return correct hint.
  892. return {const_cast_it(hint), false};
  893. }
  894. }
  895. // hint was not helpful, dispatch to hintless version.
  896. return emplace_key_args(key, std::forward<Args>(args)...);
  897. }
  898. } // namespace internal
  899. // ----------------------------------------------------------------------------
  900. // Free functions.
  901. // Erases all elements that match predicate. It has O(size) complexity.
  902. template <class Key,
  903. class GetKeyFromValue,
  904. class KeyCompare,
  905. class Container,
  906. typename Predicate>
  907. size_t EraseIf(
  908. base::internal::flat_tree<Key, GetKeyFromValue, KeyCompare, Container>&
  909. container,
  910. Predicate pred) {
  911. auto it = ranges::remove_if(container, pred);
  912. size_t removed = std::distance(it, container.end());
  913. container.erase(it, container.end());
  914. return removed;
  915. }
  916. } // namespace base
  917. #endif // BASE_CONTAINERS_FLAT_TREE_H_