flat_tree_unittest.cc 50 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541
  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. #include "base/containers/flat_tree.h"
  5. // Following tests are ported and extended tests from libcpp for std::set.
  6. // They can be found here:
  7. // https://github.com/llvm/llvm-project/tree/main/libcxx/test/std/containers/associative/set
  8. //
  9. // Not ported tests:
  10. // * No tests with PrivateConstructor and std::less<> changed to std::less<T>
  11. // These tests have to do with C++14 std::less<>
  12. // http://en.cppreference.com/w/cpp/utility/functional/less_void
  13. // and add support for templated versions of lookup functions.
  14. // Because we use same implementation, we figured that it's OK just to check
  15. // compilation and this is what we do in flat_set_unittest/flat_map_unittest.
  16. // * No tests for max_size()
  17. // Has to do with allocator support.
  18. // * No tests with DefaultOnly.
  19. // Standard containers allocate each element in the separate node on the heap
  20. // and then manipulate these nodes. Flat containers store their elements in
  21. // contiguous memory and move them around, type is required to be movable.
  22. // * No tests for N3644.
  23. // This proposal suggests that all default constructed iterators compare
  24. // equal. Currently we use std::vector iterators and they don't implement
  25. // this.
  26. // * No tests with min_allocator and no tests counting allocations.
  27. // Flat sets currently don't support allocators.
  28. #include <deque>
  29. #include <forward_list>
  30. #include <functional>
  31. #include <iterator>
  32. #include <list>
  33. #include <string>
  34. #include <vector>
  35. #include "base/functional/identity.h"
  36. #include "base/ranges/algorithm.h"
  37. #include "base/template_util.h"
  38. #include "base/test/gtest_util.h"
  39. #include "base/test/move_only_int.h"
  40. #include "testing/gmock/include/gmock/gmock.h"
  41. #include "testing/gtest/include/gtest/gtest.h"
  42. namespace base {
  43. namespace internal {
  44. namespace {
  45. template <class It>
  46. class InputIterator {
  47. public:
  48. using iterator_category = std::input_iterator_tag;
  49. using value_type = typename std::iterator_traits<It>::value_type;
  50. using difference_type = typename std::iterator_traits<It>::difference_type;
  51. using pointer = It;
  52. using reference = typename std::iterator_traits<It>::reference;
  53. InputIterator() : it_() {}
  54. explicit InputIterator(It it) : it_(it) {}
  55. reference operator*() const { return *it_; }
  56. pointer operator->() const { return it_; }
  57. InputIterator& operator++() {
  58. ++it_;
  59. return *this;
  60. }
  61. InputIterator operator++(int) {
  62. InputIterator tmp(*this);
  63. ++(*this);
  64. return tmp;
  65. }
  66. friend bool operator==(const InputIterator& lhs, const InputIterator& rhs) {
  67. return lhs.it_ == rhs.it_;
  68. }
  69. friend bool operator!=(const InputIterator& lhs, const InputIterator& rhs) {
  70. return !(lhs == rhs);
  71. }
  72. private:
  73. It it_;
  74. };
  75. template <typename It>
  76. InputIterator<It> MakeInputIterator(It it) {
  77. return InputIterator<It>(it);
  78. }
  79. class Emplaceable {
  80. public:
  81. Emplaceable() : Emplaceable(0, 0.0) {}
  82. Emplaceable(int i, double d) : int_(i), double_(d) {}
  83. Emplaceable(Emplaceable&& other) : int_(other.int_), double_(other.double_) {
  84. other.int_ = 0;
  85. other.double_ = 0.0;
  86. }
  87. Emplaceable(const Emplaceable&) = delete;
  88. Emplaceable& operator=(const Emplaceable&) = delete;
  89. Emplaceable& operator=(Emplaceable&& other) {
  90. int_ = other.int_;
  91. other.int_ = 0;
  92. double_ = other.double_;
  93. other.double_ = 0.0;
  94. return *this;
  95. }
  96. friend bool operator==(const Emplaceable& lhs, const Emplaceable& rhs) {
  97. return std::tie(lhs.int_, lhs.double_) == std::tie(rhs.int_, rhs.double_);
  98. }
  99. friend bool operator<(const Emplaceable& lhs, const Emplaceable& rhs) {
  100. return std::tie(lhs.int_, lhs.double_) < std::tie(rhs.int_, rhs.double_);
  101. }
  102. private:
  103. int int_;
  104. double double_;
  105. };
  106. struct TemplateConstructor {
  107. template <typename T>
  108. TemplateConstructor(const T&) {}
  109. friend bool operator<(const TemplateConstructor&,
  110. const TemplateConstructor&) {
  111. return false;
  112. }
  113. };
  114. class NonDefaultConstructibleCompare {
  115. public:
  116. explicit NonDefaultConstructibleCompare(int) {}
  117. template <typename T>
  118. bool operator()(const T& lhs, const T& rhs) const {
  119. return std::less<T>()(lhs, rhs);
  120. }
  121. };
  122. template <class PairType>
  123. struct LessByFirst {
  124. bool operator()(const PairType& lhs, const PairType& rhs) const {
  125. return lhs.first < rhs.first;
  126. }
  127. };
  128. // Common test trees.
  129. template <typename ContainerT>
  130. using TypedTree = flat_tree<typename ContainerT::value_type,
  131. base::identity,
  132. std::less<>,
  133. ContainerT>;
  134. using IntTree = TypedTree<std::vector<int>>;
  135. using IntPair = std::pair<int, int>;
  136. using IntPairTree = flat_tree<IntPair,
  137. base::identity,
  138. LessByFirst<IntPair>,
  139. std::vector<IntPair>>;
  140. using MoveOnlyTree = flat_tree<MoveOnlyInt,
  141. base::identity,
  142. std::less<>,
  143. std::vector<MoveOnlyInt>>;
  144. using EmplaceableTree = flat_tree<Emplaceable,
  145. base::identity,
  146. std::less<>,
  147. std::vector<Emplaceable>>;
  148. using ReversedTree =
  149. flat_tree<int, base::identity, std::greater<int>, std::vector<int>>;
  150. using TreeWithStrangeCompare = flat_tree<int,
  151. base::identity,
  152. NonDefaultConstructibleCompare,
  153. std::vector<int>>;
  154. using ::testing::ElementsAre;
  155. using ::testing::IsEmpty;
  156. } // namespace
  157. template <typename T>
  158. class FlatTreeTest : public testing::Test {};
  159. TYPED_TEST_SUITE_P(FlatTreeTest);
  160. TEST(FlatTree, IsMultipass) {
  161. static_assert(!is_multipass<std::istream_iterator<int>>(),
  162. "InputIterator is not multipass");
  163. static_assert(!is_multipass<std::ostream_iterator<int>>(),
  164. "OutputIterator is not multipass");
  165. static_assert(is_multipass<std::forward_list<int>::iterator>(),
  166. "ForwardIterator is multipass");
  167. static_assert(is_multipass<std::list<int>::iterator>(),
  168. "BidirectionalIterator is multipass");
  169. static_assert(is_multipass<std::vector<int>::iterator>(),
  170. "RandomAccessIterator is multipass");
  171. }
  172. // Tests that the compiler generated move operators propagrate noexcept
  173. // specifiers.
  174. TEST(FlatTree, NoExcept) {
  175. struct MoveThrows {
  176. MoveThrows(MoveThrows&&) noexcept(false) {}
  177. MoveThrows& operator=(MoveThrows&&) noexcept(false) { return *this; }
  178. };
  179. using MoveThrowsTree = flat_tree<MoveThrows, base::identity, std::less<>,
  180. std::array<MoveThrows, 1>>;
  181. static_assert(std::is_nothrow_move_constructible<IntTree>::value,
  182. "Error: IntTree is not nothrow move constructible");
  183. static_assert(std::is_nothrow_move_assignable<IntTree>::value,
  184. "Error: IntTree is not nothrow move assignable");
  185. static_assert(!std::is_nothrow_move_constructible<MoveThrowsTree>::value,
  186. "Error: MoveThrowsTree is nothrow move constructible");
  187. static_assert(!std::is_nothrow_move_assignable<MoveThrowsTree>::value,
  188. "Error: MoveThrowsTree is nothrow move assignable");
  189. }
  190. // ----------------------------------------------------------------------------
  191. // Class.
  192. // Check that flat_tree and its iterators can be instantiated with an
  193. // incomplete type.
  194. TEST(FlatTree, IncompleteType) {
  195. struct A {
  196. using Tree = flat_tree<A, base::identity, std::less<A>, std::vector<A>>;
  197. int data;
  198. Tree set_with_incomplete_type;
  199. Tree::iterator it;
  200. Tree::const_iterator cit;
  201. // We do not declare operator< because clang complains that it's unused.
  202. };
  203. A a;
  204. }
  205. TEST(FlatTree, Stability) {
  206. using Pair = std::pair<int, int>;
  207. using Tree =
  208. flat_tree<Pair, base::identity, LessByFirst<Pair>, std::vector<Pair>>;
  209. // Constructors are stable.
  210. Tree cont({{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}});
  211. auto AllOfSecondsAreZero = [&cont] {
  212. return ranges::all_of(cont,
  213. [](const Pair& elem) { return elem.second == 0; });
  214. };
  215. EXPECT_TRUE(AllOfSecondsAreZero()) << "constructor should be stable";
  216. // Should not replace existing.
  217. cont.insert(Pair(0, 2));
  218. cont.insert(Pair(1, 2));
  219. cont.insert(Pair(2, 2));
  220. EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
  221. cont.insert(Pair(3, 0));
  222. cont.insert(Pair(3, 2));
  223. EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
  224. }
  225. // ----------------------------------------------------------------------------
  226. // Types.
  227. // key_type
  228. // key_compare
  229. // value_type
  230. // value_compare
  231. // pointer
  232. // const_pointer
  233. // reference
  234. // const_reference
  235. // size_type
  236. // difference_type
  237. // iterator
  238. // const_iterator
  239. // reverse_iterator
  240. // const_reverse_iterator
  241. TEST(FlatTree, Types) {
  242. // These are guaranteed to be portable.
  243. static_assert((std::is_same<int, IntTree::key_type>::value), "");
  244. static_assert((std::is_same<int, IntTree::value_type>::value), "");
  245. static_assert((std::is_same<std::less<>, IntTree::key_compare>::value), "");
  246. static_assert((std::is_same<int&, IntTree::reference>::value), "");
  247. static_assert((std::is_same<const int&, IntTree::const_reference>::value),
  248. "");
  249. static_assert((std::is_same<int*, IntTree::pointer>::value), "");
  250. static_assert((std::is_same<const int*, IntTree::const_pointer>::value), "");
  251. }
  252. // ----------------------------------------------------------------------------
  253. // Lifetime.
  254. // flat_tree()
  255. // flat_tree(const Compare& comp)
  256. TYPED_TEST_P(FlatTreeTest, DefaultConstructor) {
  257. {
  258. TypedTree<TypeParam> cont;
  259. EXPECT_THAT(cont, ElementsAre());
  260. }
  261. {
  262. TreeWithStrangeCompare cont(NonDefaultConstructibleCompare(0));
  263. EXPECT_THAT(cont, ElementsAre());
  264. }
  265. }
  266. // flat_tree(const flat_tree& x)
  267. TYPED_TEST_P(FlatTreeTest, CopyConstructor) {
  268. TypedTree<TypeParam> original({1, 2, 3, 4});
  269. TypedTree<TypeParam> copied(original);
  270. EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
  271. EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
  272. EXPECT_THAT(original, ElementsAre(1, 2, 3, 4));
  273. EXPECT_EQ(original, copied);
  274. }
  275. // flat_tree(flat_tree&& x)
  276. TEST(FlatTree, MoveConstructor) {
  277. int input_range[] = {1, 2, 3, 4};
  278. MoveOnlyTree original(std::begin(input_range), std::end(input_range));
  279. MoveOnlyTree moved(std::move(original));
  280. EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
  281. EXPECT_EQ(1U, moved.count(MoveOnlyInt(2)));
  282. EXPECT_EQ(1U, moved.count(MoveOnlyInt(3)));
  283. EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
  284. }
  285. // flat_tree(InputIterator first,
  286. // InputIterator last,
  287. // const Compare& comp = Compare())
  288. TEST(FlatTree, RangeConstructor) {
  289. {
  290. IntPair input_vals[] = {{1, 1}, {1, 2}, {2, 1}, {2, 2}, {1, 3},
  291. {2, 3}, {3, 1}, {3, 2}, {3, 3}};
  292. IntPairTree first_of(MakeInputIterator(std::begin(input_vals)),
  293. MakeInputIterator(std::end(input_vals)));
  294. EXPECT_THAT(first_of,
  295. ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1)));
  296. }
  297. {
  298. TreeWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2,
  299. 2, 3, 3, 3};
  300. TreeWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)),
  301. MakeInputIterator(std::end(input_vals)),
  302. NonDefaultConstructibleCompare(0));
  303. EXPECT_THAT(cont, ElementsAre(1, 2, 3));
  304. }
  305. }
  306. // flat_tree(const container_type&)
  307. TYPED_TEST_P(FlatTreeTest, ContainerCopyConstructor) {
  308. TypeParam items = {1, 2, 3, 4};
  309. TypedTree<TypeParam> tree(items);
  310. EXPECT_THAT(tree, ElementsAre(1, 2, 3, 4));
  311. EXPECT_THAT(items, ElementsAre(1, 2, 3, 4));
  312. }
  313. // flat_tree(container_type&&)
  314. TEST(FlatTree, ContainerMoveConstructor) {
  315. using Pair = std::pair<int, MoveOnlyInt>;
  316. // Construct an unsorted vector with a duplicate item in it. Sorted by the
  317. // first item, the second allows us to test for stability. Using a move
  318. // only type to ensure the vector is not copied.
  319. std::vector<Pair> storage;
  320. storage.push_back(Pair(2, MoveOnlyInt(0)));
  321. storage.push_back(Pair(1, MoveOnlyInt(0)));
  322. storage.push_back(Pair(2, MoveOnlyInt(1)));
  323. using Tree =
  324. flat_tree<Pair, base::identity, LessByFirst<Pair>, std::vector<Pair>>;
  325. Tree tree(std::move(storage));
  326. // The list should be two items long, with only the first "2" saved.
  327. ASSERT_EQ(2u, tree.size());
  328. const Pair& zeroth = *tree.begin();
  329. ASSERT_EQ(1, zeroth.first);
  330. ASSERT_EQ(0, zeroth.second.data());
  331. const Pair& first = *(tree.begin() + 1);
  332. ASSERT_EQ(2, first.first);
  333. ASSERT_EQ(0, first.second.data());
  334. }
  335. // flat_tree(std::initializer_list<value_type> ilist,
  336. // const Compare& comp = Compare())
  337. TYPED_TEST_P(FlatTreeTest, InitializerListConstructor) {
  338. {
  339. TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 10, 8});
  340. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
  341. }
  342. {
  343. TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 10, 8});
  344. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
  345. }
  346. {
  347. TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8},
  348. NonDefaultConstructibleCompare(0));
  349. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
  350. }
  351. {
  352. IntPairTree first_of({{1, 1}, {2, 1}, {1, 2}});
  353. EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
  354. }
  355. }
  356. // flat_tree(sorted_unique_t,
  357. // InputIterator first,
  358. // InputIterator last,
  359. // const Compare& comp = Compare())
  360. TEST(FlatTree, SortedUniqueRangeConstructor) {
  361. {
  362. IntPair input_vals[] = {{1, 1}, {2, 1}, {3, 1}};
  363. IntPairTree first_of(sorted_unique,
  364. MakeInputIterator(std::begin(input_vals)),
  365. MakeInputIterator(std::end(input_vals)));
  366. EXPECT_THAT(first_of,
  367. ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1)));
  368. }
  369. {
  370. TreeWithStrangeCompare::value_type input_vals[] = {1, 2, 3};
  371. TreeWithStrangeCompare cont(sorted_unique,
  372. MakeInputIterator(std::begin(input_vals)),
  373. MakeInputIterator(std::end(input_vals)),
  374. NonDefaultConstructibleCompare(0));
  375. EXPECT_THAT(cont, ElementsAre(1, 2, 3));
  376. }
  377. }
  378. // flat_tree(sorted_unique_t, const container_type&)
  379. TYPED_TEST_P(FlatTreeTest, SortedUniqueContainerCopyConstructor) {
  380. TypeParam items = {1, 2, 3, 4};
  381. TypedTree<TypeParam> tree(sorted_unique, items);
  382. EXPECT_THAT(tree, ElementsAre(1, 2, 3, 4));
  383. EXPECT_THAT(items, ElementsAre(1, 2, 3, 4));
  384. }
  385. // flat_tree(sorted_unique_t, std::vector<value_type>&&)
  386. TEST(FlatTree, SortedUniqueVectorMoveConstructor) {
  387. using Pair = std::pair<int, MoveOnlyInt>;
  388. std::vector<Pair> storage;
  389. storage.push_back(Pair(1, MoveOnlyInt(0)));
  390. storage.push_back(Pair(2, MoveOnlyInt(0)));
  391. using Tree =
  392. flat_tree<Pair, base::identity, LessByFirst<Pair>, std::vector<Pair>>;
  393. Tree tree(sorted_unique, std::move(storage));
  394. ASSERT_EQ(2u, tree.size());
  395. const Pair& zeroth = *tree.begin();
  396. ASSERT_EQ(1, zeroth.first);
  397. ASSERT_EQ(0, zeroth.second.data());
  398. const Pair& first = *(tree.begin() + 1);
  399. ASSERT_EQ(2, first.first);
  400. ASSERT_EQ(0, first.second.data());
  401. }
  402. // flat_tree(sorted_unique_t,
  403. // std::initializer_list<value_type> ilist,
  404. // const Compare& comp = Compare())
  405. TYPED_TEST_P(FlatTreeTest, SortedUniqueInitializerListConstructor) {
  406. {
  407. TypedTree<TypeParam> cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10});
  408. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
  409. }
  410. {
  411. TypedTree<TypeParam> cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10});
  412. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
  413. }
  414. {
  415. TreeWithStrangeCompare cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10},
  416. NonDefaultConstructibleCompare(0));
  417. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
  418. }
  419. {
  420. IntPairTree first_of(sorted_unique, {{1, 1}, {2, 1}});
  421. EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
  422. }
  423. }
  424. // ----------------------------------------------------------------------------
  425. // Assignments.
  426. // flat_tree& operator=(const flat_tree&)
  427. TYPED_TEST_P(FlatTreeTest, CopyAssignable) {
  428. TypedTree<TypeParam> original({1, 2, 3, 4});
  429. TypedTree<TypeParam> copied;
  430. copied = original;
  431. EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
  432. EXPECT_THAT(original, ElementsAre(1, 2, 3, 4));
  433. EXPECT_EQ(original, copied);
  434. }
  435. // flat_tree& operator=(flat_tree&&)
  436. TEST(FlatTree, MoveAssignable) {
  437. int input_range[] = {1, 2, 3, 4};
  438. MoveOnlyTree original(std::begin(input_range), std::end(input_range));
  439. MoveOnlyTree moved;
  440. moved = std::move(original);
  441. EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
  442. EXPECT_EQ(1U, moved.count(MoveOnlyInt(2)));
  443. EXPECT_EQ(1U, moved.count(MoveOnlyInt(3)));
  444. EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
  445. }
  446. // flat_tree& operator=(std::initializer_list<value_type> ilist)
  447. TYPED_TEST_P(FlatTreeTest, InitializerListAssignable) {
  448. TypedTree<TypeParam> cont({0});
  449. cont = {1, 2, 3, 4, 5, 6, 10, 8};
  450. EXPECT_EQ(0U, cont.count(0));
  451. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
  452. }
  453. // --------------------------------------------------------------------------
  454. // Memory management.
  455. // void reserve(size_type new_capacity)
  456. TEST(FlatTreeTest, Reserve) {
  457. IntTree cont({1, 2, 3});
  458. cont.reserve(5);
  459. EXPECT_LE(5U, cont.capacity());
  460. }
  461. // size_type capacity() const
  462. TEST(FlatTreeTest, Capacity) {
  463. IntTree cont({1, 2, 3});
  464. EXPECT_LE(cont.size(), cont.capacity());
  465. cont.reserve(5);
  466. EXPECT_LE(cont.size(), cont.capacity());
  467. }
  468. // void shrink_to_fit()
  469. TEST(FlatTreeTest, ShrinkToFit) {
  470. IntTree cont({1, 2, 3});
  471. IntTree::size_type capacity_before = cont.capacity();
  472. cont.shrink_to_fit();
  473. EXPECT_GE(capacity_before, cont.capacity());
  474. }
  475. // ----------------------------------------------------------------------------
  476. // Size management.
  477. // void clear()
  478. TYPED_TEST_P(FlatTreeTest, Clear) {
  479. TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
  480. cont.clear();
  481. EXPECT_THAT(cont, ElementsAre());
  482. }
  483. // size_type size() const
  484. TYPED_TEST_P(FlatTreeTest, Size) {
  485. TypedTree<TypeParam> cont;
  486. EXPECT_EQ(0U, cont.size());
  487. cont.insert(2);
  488. EXPECT_EQ(1U, cont.size());
  489. cont.insert(1);
  490. EXPECT_EQ(2U, cont.size());
  491. cont.insert(3);
  492. EXPECT_EQ(3U, cont.size());
  493. cont.erase(cont.begin());
  494. EXPECT_EQ(2U, cont.size());
  495. cont.erase(cont.begin());
  496. EXPECT_EQ(1U, cont.size());
  497. cont.erase(cont.begin());
  498. EXPECT_EQ(0U, cont.size());
  499. }
  500. // bool empty() const
  501. TYPED_TEST_P(FlatTreeTest, Empty) {
  502. TypedTree<TypeParam> cont;
  503. EXPECT_TRUE(cont.empty());
  504. cont.insert(1);
  505. EXPECT_FALSE(cont.empty());
  506. cont.clear();
  507. EXPECT_TRUE(cont.empty());
  508. }
  509. // ----------------------------------------------------------------------------
  510. // Iterators.
  511. // iterator begin()
  512. // const_iterator begin() const
  513. // iterator end()
  514. // const_iterator end() const
  515. //
  516. // reverse_iterator rbegin()
  517. // const_reverse_iterator rbegin() const
  518. // reverse_iterator rend()
  519. // const_reverse_iterator rend() const
  520. //
  521. // const_iterator cbegin() const
  522. // const_iterator cend() const
  523. // const_reverse_iterator crbegin() const
  524. // const_reverse_iterator crend() const
  525. TYPED_TEST_P(FlatTreeTest, Iterators) {
  526. TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
  527. auto size =
  528. static_cast<typename TypedTree<TypeParam>::difference_type>(cont.size());
  529. EXPECT_EQ(size, std::distance(cont.begin(), cont.end()));
  530. EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend()));
  531. EXPECT_EQ(size, std::distance(cont.rbegin(), cont.rend()));
  532. EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend()));
  533. {
  534. auto it = cont.begin();
  535. auto c_it = cont.cbegin();
  536. EXPECT_EQ(it, c_it);
  537. for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) {
  538. EXPECT_EQ(j, *it);
  539. EXPECT_EQ(j, *c_it);
  540. }
  541. }
  542. {
  543. auto rit = cont.rbegin();
  544. auto c_rit = cont.crbegin();
  545. EXPECT_EQ(rit, c_rit);
  546. for (int j = static_cast<int>(size); rit != cont.rend();
  547. ++rit, ++c_rit, --j) {
  548. EXPECT_EQ(j, *rit);
  549. EXPECT_EQ(j, *c_rit);
  550. }
  551. }
  552. }
  553. // ----------------------------------------------------------------------------
  554. // Insert operations.
  555. // pair<iterator, bool> insert(const value_type& val)
  556. TYPED_TEST_P(FlatTreeTest, InsertLValue) {
  557. TypedTree<TypeParam> cont;
  558. int value = 2;
  559. std::pair<typename TypedTree<TypeParam>::iterator, bool> result =
  560. cont.insert(value);
  561. EXPECT_TRUE(result.second);
  562. EXPECT_EQ(cont.begin(), result.first);
  563. EXPECT_EQ(1U, cont.size());
  564. EXPECT_EQ(2, *result.first);
  565. value = 1;
  566. result = cont.insert(value);
  567. EXPECT_TRUE(result.second);
  568. EXPECT_EQ(cont.begin(), result.first);
  569. EXPECT_EQ(2U, cont.size());
  570. EXPECT_EQ(1, *result.first);
  571. value = 3;
  572. result = cont.insert(value);
  573. EXPECT_TRUE(result.second);
  574. EXPECT_EQ(std::prev(cont.end()), result.first);
  575. EXPECT_EQ(3U, cont.size());
  576. EXPECT_EQ(3, *result.first);
  577. value = 3;
  578. result = cont.insert(value);
  579. EXPECT_FALSE(result.second);
  580. EXPECT_EQ(std::prev(cont.end()), result.first);
  581. EXPECT_EQ(3U, cont.size());
  582. EXPECT_EQ(3, *result.first);
  583. }
  584. // pair<iterator, bool> insert(value_type&& val)
  585. TEST(FlatTree, InsertRValue) {
  586. MoveOnlyTree cont;
  587. std::pair<MoveOnlyTree::iterator, bool> result = cont.insert(MoveOnlyInt(2));
  588. EXPECT_TRUE(result.second);
  589. EXPECT_EQ(cont.begin(), result.first);
  590. EXPECT_EQ(1U, cont.size());
  591. EXPECT_EQ(2, result.first->data());
  592. result = cont.insert(MoveOnlyInt(1));
  593. EXPECT_TRUE(result.second);
  594. EXPECT_EQ(cont.begin(), result.first);
  595. EXPECT_EQ(2U, cont.size());
  596. EXPECT_EQ(1, result.first->data());
  597. result = cont.insert(MoveOnlyInt(3));
  598. EXPECT_TRUE(result.second);
  599. EXPECT_EQ(std::prev(cont.end()), result.first);
  600. EXPECT_EQ(3U, cont.size());
  601. EXPECT_EQ(3, result.first->data());
  602. result = cont.insert(MoveOnlyInt(3));
  603. EXPECT_FALSE(result.second);
  604. EXPECT_EQ(std::prev(cont.end()), result.first);
  605. EXPECT_EQ(3U, cont.size());
  606. EXPECT_EQ(3, result.first->data());
  607. }
  608. // iterator insert(const_iterator position_hint, const value_type& val)
  609. TYPED_TEST_P(FlatTreeTest, InsertPositionLValue) {
  610. TypedTree<TypeParam> cont;
  611. auto result = cont.insert(cont.cend(), 2);
  612. EXPECT_EQ(cont.begin(), result);
  613. EXPECT_EQ(1U, cont.size());
  614. EXPECT_EQ(2, *result);
  615. result = cont.insert(cont.cend(), 1);
  616. EXPECT_EQ(cont.begin(), result);
  617. EXPECT_EQ(2U, cont.size());
  618. EXPECT_EQ(1, *result);
  619. result = cont.insert(cont.cend(), 3);
  620. EXPECT_EQ(std::prev(cont.end()), result);
  621. EXPECT_EQ(3U, cont.size());
  622. EXPECT_EQ(3, *result);
  623. result = cont.insert(cont.cend(), 3);
  624. EXPECT_EQ(std::prev(cont.end()), result);
  625. EXPECT_EQ(3U, cont.size());
  626. EXPECT_EQ(3, *result);
  627. }
  628. // iterator insert(const_iterator position_hint, value_type&& val)
  629. TEST(FlatTree, InsertPositionRValue) {
  630. MoveOnlyTree cont;
  631. auto result = cont.insert(cont.cend(), MoveOnlyInt(2));
  632. EXPECT_EQ(cont.begin(), result);
  633. EXPECT_EQ(1U, cont.size());
  634. EXPECT_EQ(2, result->data());
  635. result = cont.insert(cont.cend(), MoveOnlyInt(1));
  636. EXPECT_EQ(cont.begin(), result);
  637. EXPECT_EQ(2U, cont.size());
  638. EXPECT_EQ(1, result->data());
  639. result = cont.insert(cont.cend(), MoveOnlyInt(3));
  640. EXPECT_EQ(std::prev(cont.end()), result);
  641. EXPECT_EQ(3U, cont.size());
  642. EXPECT_EQ(3, result->data());
  643. result = cont.insert(cont.cend(), MoveOnlyInt(3));
  644. EXPECT_EQ(std::prev(cont.end()), result);
  645. EXPECT_EQ(3U, cont.size());
  646. EXPECT_EQ(3, result->data());
  647. }
  648. // template <class InputIterator>
  649. // void insert(InputIterator first, InputIterator last);
  650. TEST(FlatTree, InsertIterIter) {
  651. struct GetKeyFromIntIntPair {
  652. const int& operator()(const std::pair<int, int>& p) const {
  653. return p.first;
  654. }
  655. };
  656. using IntIntMap = flat_tree<int, GetKeyFromIntIntPair, std::less<int>,
  657. std::vector<IntPair>>;
  658. {
  659. IntIntMap cont;
  660. IntPair int_pairs[] = {{3, 1}, {1, 1}, {4, 1}, {2, 1}};
  661. cont.insert(std::begin(int_pairs), std::end(int_pairs));
  662. EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
  663. IntPair(4, 1)));
  664. }
  665. {
  666. IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
  667. std::vector<IntPair> int_pairs;
  668. cont.insert(std::begin(int_pairs), std::end(int_pairs));
  669. EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
  670. IntPair(4, 1)));
  671. }
  672. {
  673. IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
  674. IntPair int_pairs[] = {{1, 1}};
  675. cont.insert(std::begin(int_pairs), std::end(int_pairs));
  676. EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
  677. IntPair(4, 1)));
  678. }
  679. {
  680. IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
  681. IntPair int_pairs[] = {{5, 1}};
  682. cont.insert(std::begin(int_pairs), std::end(int_pairs));
  683. EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
  684. IntPair(4, 1), IntPair(5, 1)));
  685. }
  686. {
  687. IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
  688. IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}};
  689. cont.insert(std::begin(int_pairs), std::end(int_pairs));
  690. EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
  691. IntPair(4, 1)));
  692. }
  693. {
  694. IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
  695. IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}, {7, 2}, {6, 2},
  696. {8, 2}, {5, 2}, {5, 3}, {6, 3}, {7, 3}, {8, 3}};
  697. cont.insert(std::begin(int_pairs), std::end(int_pairs));
  698. EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
  699. IntPair(4, 1), IntPair(5, 2), IntPair(6, 2),
  700. IntPair(7, 2), IntPair(8, 2)));
  701. }
  702. }
  703. // template <class... Args>
  704. // pair<iterator, bool> emplace(Args&&... args)
  705. TYPED_TEST_P(FlatTreeTest, Emplace) {
  706. {
  707. EmplaceableTree cont;
  708. std::pair<EmplaceableTree::iterator, bool> result = cont.emplace();
  709. EXPECT_TRUE(result.second);
  710. EXPECT_EQ(cont.begin(), result.first);
  711. EXPECT_EQ(1U, cont.size());
  712. EXPECT_EQ(Emplaceable(), *cont.begin());
  713. result = cont.emplace(2, 3.5);
  714. EXPECT_TRUE(result.second);
  715. EXPECT_EQ(std::next(cont.begin()), result.first);
  716. EXPECT_EQ(2U, cont.size());
  717. EXPECT_EQ(Emplaceable(2, 3.5), *result.first);
  718. result = cont.emplace(2, 3.5);
  719. EXPECT_FALSE(result.second);
  720. EXPECT_EQ(std::next(cont.begin()), result.first);
  721. EXPECT_EQ(2U, cont.size());
  722. EXPECT_EQ(Emplaceable(2, 3.5), *result.first);
  723. }
  724. {
  725. TypedTree<TypeParam> cont;
  726. std::pair<typename TypedTree<TypeParam>::iterator, bool> result =
  727. cont.emplace(2);
  728. EXPECT_TRUE(result.second);
  729. EXPECT_EQ(cont.begin(), result.first);
  730. EXPECT_EQ(1U, cont.size());
  731. EXPECT_EQ(2, *result.first);
  732. }
  733. }
  734. // template <class... Args>
  735. // iterator emplace_hint(const_iterator position_hint, Args&&... args)
  736. TYPED_TEST_P(FlatTreeTest, EmplacePosition) {
  737. {
  738. EmplaceableTree cont;
  739. auto result = cont.emplace_hint(cont.cend());
  740. EXPECT_EQ(cont.begin(), result);
  741. EXPECT_EQ(1U, cont.size());
  742. EXPECT_EQ(Emplaceable(), *cont.begin());
  743. result = cont.emplace_hint(cont.cend(), 2, 3.5);
  744. EXPECT_EQ(std::next(cont.begin()), result);
  745. EXPECT_EQ(2U, cont.size());
  746. EXPECT_EQ(Emplaceable(2, 3.5), *result);
  747. result = cont.emplace_hint(cont.cbegin(), 2, 3.5);
  748. EXPECT_EQ(std::next(cont.begin()), result);
  749. EXPECT_EQ(2U, cont.size());
  750. EXPECT_EQ(Emplaceable(2, 3.5), *result);
  751. }
  752. {
  753. TypedTree<TypeParam> cont;
  754. auto result = cont.emplace_hint(cont.cend(), 2);
  755. EXPECT_EQ(cont.begin(), result);
  756. EXPECT_EQ(1U, cont.size());
  757. EXPECT_EQ(2, *result);
  758. }
  759. }
  760. // ----------------------------------------------------------------------------
  761. // Underlying type operations.
  762. // underlying_type extract() &&
  763. TYPED_TEST_P(FlatTreeTest, Extract) {
  764. TypedTree<TypeParam> cont;
  765. cont.emplace(3);
  766. cont.emplace(1);
  767. cont.emplace(2);
  768. cont.emplace(4);
  769. TypeParam body = std::move(cont).extract();
  770. EXPECT_THAT(cont, IsEmpty());
  771. EXPECT_THAT(body, ElementsAre(1, 2, 3, 4));
  772. }
  773. // replace(underlying_type&&)
  774. TYPED_TEST_P(FlatTreeTest, Replace) {
  775. TypeParam body = {1, 2, 3, 4};
  776. TypedTree<TypeParam> cont;
  777. cont.replace(std::move(body));
  778. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4));
  779. }
  780. // ----------------------------------------------------------------------------
  781. // Erase operations.
  782. // iterator erase(const_iterator position_hint)
  783. TYPED_TEST_P(FlatTreeTest, ErasePosition) {
  784. {
  785. TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
  786. auto it = cont.erase(std::next(cont.cbegin(), 3));
  787. EXPECT_EQ(std::next(cont.begin(), 3), it);
  788. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
  789. it = cont.erase(std::next(cont.cbegin(), 0));
  790. EXPECT_EQ(cont.begin(), it);
  791. EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
  792. it = cont.erase(std::next(cont.cbegin(), 5));
  793. EXPECT_EQ(cont.end(), it);
  794. EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7));
  795. it = cont.erase(std::next(cont.cbegin(), 1));
  796. EXPECT_EQ(std::next(cont.begin()), it);
  797. EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7));
  798. it = cont.erase(std::next(cont.cbegin(), 2));
  799. EXPECT_EQ(std::next(cont.begin(), 2), it);
  800. EXPECT_THAT(cont, ElementsAre(2, 5, 7));
  801. it = cont.erase(std::next(cont.cbegin(), 2));
  802. EXPECT_EQ(std::next(cont.begin(), 2), it);
  803. EXPECT_THAT(cont, ElementsAre(2, 5));
  804. it = cont.erase(std::next(cont.cbegin(), 0));
  805. EXPECT_EQ(std::next(cont.begin(), 0), it);
  806. EXPECT_THAT(cont, ElementsAre(5));
  807. it = cont.erase(cont.cbegin());
  808. EXPECT_EQ(cont.begin(), it);
  809. EXPECT_EQ(cont.end(), it);
  810. }
  811. // This is LWG #2059.
  812. // There is a potential ambiguity between erase with an iterator and erase
  813. // with a key, if key has a templated constructor.
  814. {
  815. using T = TemplateConstructor;
  816. flat_tree<T, base::identity, std::less<>, std::vector<T>> cont;
  817. T v(0);
  818. auto it = cont.find(v);
  819. if (it != cont.end())
  820. cont.erase(it);
  821. }
  822. }
  823. // iterator erase(const_iterator first, const_iterator last)
  824. TYPED_TEST_P(FlatTreeTest, EraseRange) {
  825. TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
  826. auto it =
  827. cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5));
  828. EXPECT_EQ(std::next(cont.begin(), 5), it);
  829. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8));
  830. it = cont.erase(std::next(cont.cbegin(), 3), std::next(cont.cbegin(), 4));
  831. EXPECT_EQ(std::next(cont.begin(), 3), it);
  832. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
  833. it = cont.erase(std::next(cont.cbegin(), 2), std::next(cont.cbegin(), 5));
  834. EXPECT_EQ(std::next(cont.begin(), 2), it);
  835. EXPECT_THAT(cont, ElementsAre(1, 2, 7, 8));
  836. it = cont.erase(std::next(cont.cbegin(), 0), std::next(cont.cbegin(), 2));
  837. EXPECT_EQ(std::next(cont.begin(), 0), it);
  838. EXPECT_THAT(cont, ElementsAre(7, 8));
  839. it = cont.erase(cont.cbegin(), cont.cend());
  840. EXPECT_EQ(cont.begin(), it);
  841. EXPECT_EQ(cont.end(), it);
  842. }
  843. // size_type erase(const key_type& key)
  844. TYPED_TEST_P(FlatTreeTest, EraseKey) {
  845. TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
  846. EXPECT_EQ(0U, cont.erase(9));
  847. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8));
  848. EXPECT_EQ(1U, cont.erase(4));
  849. EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
  850. EXPECT_EQ(1U, cont.erase(1));
  851. EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
  852. EXPECT_EQ(1U, cont.erase(8));
  853. EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7));
  854. EXPECT_EQ(1U, cont.erase(3));
  855. EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7));
  856. EXPECT_EQ(1U, cont.erase(6));
  857. EXPECT_THAT(cont, ElementsAre(2, 5, 7));
  858. EXPECT_EQ(1U, cont.erase(7));
  859. EXPECT_THAT(cont, ElementsAre(2, 5));
  860. EXPECT_EQ(1U, cont.erase(2));
  861. EXPECT_THAT(cont, ElementsAre(5));
  862. EXPECT_EQ(1U, cont.erase(5));
  863. EXPECT_THAT(cont, ElementsAre());
  864. }
  865. TYPED_TEST_P(FlatTreeTest, EraseEndDeath) {
  866. {
  867. TypedTree<TypeParam> tree;
  868. ASSERT_DEATH_IF_SUPPORTED(tree.erase(tree.cend()), "");
  869. }
  870. {
  871. TypedTree<TypeParam> tree = {1, 2, 3, 4};
  872. ASSERT_DEATH_IF_SUPPORTED(tree.erase(tree.find(5)), "");
  873. }
  874. }
  875. // ----------------------------------------------------------------------------
  876. // Comparators.
  877. // key_compare key_comp() const
  878. TEST(FlatTree, KeyComp) {
  879. ReversedTree cont({1, 2, 3, 4, 5});
  880. EXPECT_TRUE(ranges::is_sorted(cont, cont.key_comp()));
  881. int new_elements[] = {6, 7, 8, 9, 10};
  882. std::copy(std::begin(new_elements), std::end(new_elements),
  883. std::inserter(cont, cont.end()));
  884. EXPECT_TRUE(ranges::is_sorted(cont, cont.key_comp()));
  885. }
  886. // value_compare value_comp() const
  887. TEST(FlatTree, ValueComp) {
  888. ReversedTree cont({1, 2, 3, 4, 5});
  889. EXPECT_TRUE(ranges::is_sorted(cont, cont.value_comp()));
  890. int new_elements[] = {6, 7, 8, 9, 10};
  891. std::copy(std::begin(new_elements), std::end(new_elements),
  892. std::inserter(cont, cont.end()));
  893. EXPECT_TRUE(ranges::is_sorted(cont, cont.value_comp()));
  894. }
  895. // ----------------------------------------------------------------------------
  896. // Search operations.
  897. // size_type count(const key_type& key) const
  898. TYPED_TEST_P(FlatTreeTest, Count) {
  899. const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12});
  900. EXPECT_EQ(1U, cont.count(5));
  901. EXPECT_EQ(1U, cont.count(6));
  902. EXPECT_EQ(1U, cont.count(7));
  903. EXPECT_EQ(1U, cont.count(8));
  904. EXPECT_EQ(1U, cont.count(9));
  905. EXPECT_EQ(1U, cont.count(10));
  906. EXPECT_EQ(1U, cont.count(11));
  907. EXPECT_EQ(1U, cont.count(12));
  908. EXPECT_EQ(0U, cont.count(4));
  909. }
  910. // iterator find(const key_type& key)
  911. // const_iterator find(const key_type& key) const
  912. TYPED_TEST_P(FlatTreeTest, Find) {
  913. {
  914. TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12});
  915. EXPECT_EQ(cont.begin(), cont.find(5));
  916. EXPECT_EQ(std::next(cont.begin()), cont.find(6));
  917. EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
  918. EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
  919. EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
  920. EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
  921. EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
  922. EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
  923. EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
  924. }
  925. {
  926. const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12});
  927. EXPECT_EQ(cont.begin(), cont.find(5));
  928. EXPECT_EQ(std::next(cont.begin()), cont.find(6));
  929. EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
  930. EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
  931. EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
  932. EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
  933. EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
  934. EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
  935. EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
  936. }
  937. }
  938. // bool contains(const key_type& key) const
  939. TYPED_TEST_P(FlatTreeTest, Contains) {
  940. const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12});
  941. EXPECT_TRUE(cont.contains(5));
  942. EXPECT_TRUE(cont.contains(6));
  943. EXPECT_TRUE(cont.contains(7));
  944. EXPECT_TRUE(cont.contains(8));
  945. EXPECT_TRUE(cont.contains(9));
  946. EXPECT_TRUE(cont.contains(10));
  947. EXPECT_TRUE(cont.contains(11));
  948. EXPECT_TRUE(cont.contains(12));
  949. EXPECT_FALSE(cont.contains(4));
  950. }
  951. // pair<iterator, iterator> equal_range(const key_type& key)
  952. // pair<const_iterator, const_iterator> equal_range(const key_type& key) const
  953. TYPED_TEST_P(FlatTreeTest, EqualRange) {
  954. {
  955. TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
  956. std::pair<typename TypedTree<TypeParam>::iterator,
  957. typename TypedTree<TypeParam>::iterator>
  958. result = cont.equal_range(5);
  959. EXPECT_EQ(std::next(cont.begin(), 0), result.first);
  960. EXPECT_EQ(std::next(cont.begin(), 1), result.second);
  961. result = cont.equal_range(7);
  962. EXPECT_EQ(std::next(cont.begin(), 1), result.first);
  963. EXPECT_EQ(std::next(cont.begin(), 2), result.second);
  964. result = cont.equal_range(9);
  965. EXPECT_EQ(std::next(cont.begin(), 2), result.first);
  966. EXPECT_EQ(std::next(cont.begin(), 3), result.second);
  967. result = cont.equal_range(11);
  968. EXPECT_EQ(std::next(cont.begin(), 3), result.first);
  969. EXPECT_EQ(std::next(cont.begin(), 4), result.second);
  970. result = cont.equal_range(13);
  971. EXPECT_EQ(std::next(cont.begin(), 4), result.first);
  972. EXPECT_EQ(std::next(cont.begin(), 5), result.second);
  973. result = cont.equal_range(15);
  974. EXPECT_EQ(std::next(cont.begin(), 5), result.first);
  975. EXPECT_EQ(std::next(cont.begin(), 6), result.second);
  976. result = cont.equal_range(17);
  977. EXPECT_EQ(std::next(cont.begin(), 6), result.first);
  978. EXPECT_EQ(std::next(cont.begin(), 7), result.second);
  979. result = cont.equal_range(19);
  980. EXPECT_EQ(std::next(cont.begin(), 7), result.first);
  981. EXPECT_EQ(std::next(cont.begin(), 8), result.second);
  982. result = cont.equal_range(4);
  983. EXPECT_EQ(std::next(cont.begin(), 0), result.first);
  984. EXPECT_EQ(std::next(cont.begin(), 0), result.second);
  985. result = cont.equal_range(6);
  986. EXPECT_EQ(std::next(cont.begin(), 1), result.first);
  987. EXPECT_EQ(std::next(cont.begin(), 1), result.second);
  988. result = cont.equal_range(8);
  989. EXPECT_EQ(std::next(cont.begin(), 2), result.first);
  990. EXPECT_EQ(std::next(cont.begin(), 2), result.second);
  991. result = cont.equal_range(10);
  992. EXPECT_EQ(std::next(cont.begin(), 3), result.first);
  993. EXPECT_EQ(std::next(cont.begin(), 3), result.second);
  994. result = cont.equal_range(12);
  995. EXPECT_EQ(std::next(cont.begin(), 4), result.first);
  996. EXPECT_EQ(std::next(cont.begin(), 4), result.second);
  997. result = cont.equal_range(14);
  998. EXPECT_EQ(std::next(cont.begin(), 5), result.first);
  999. EXPECT_EQ(std::next(cont.begin(), 5), result.second);
  1000. result = cont.equal_range(16);
  1001. EXPECT_EQ(std::next(cont.begin(), 6), result.first);
  1002. EXPECT_EQ(std::next(cont.begin(), 6), result.second);
  1003. result = cont.equal_range(18);
  1004. EXPECT_EQ(std::next(cont.begin(), 7), result.first);
  1005. EXPECT_EQ(std::next(cont.begin(), 7), result.second);
  1006. result = cont.equal_range(20);
  1007. EXPECT_EQ(std::next(cont.begin(), 8), result.first);
  1008. EXPECT_EQ(std::next(cont.begin(), 8), result.second);
  1009. }
  1010. {
  1011. const TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
  1012. std::pair<typename TypedTree<TypeParam>::const_iterator,
  1013. typename TypedTree<TypeParam>::const_iterator>
  1014. result = cont.equal_range(5);
  1015. EXPECT_EQ(std::next(cont.begin(), 0), result.first);
  1016. EXPECT_EQ(std::next(cont.begin(), 1), result.second);
  1017. result = cont.equal_range(7);
  1018. EXPECT_EQ(std::next(cont.begin(), 1), result.first);
  1019. EXPECT_EQ(std::next(cont.begin(), 2), result.second);
  1020. result = cont.equal_range(9);
  1021. EXPECT_EQ(std::next(cont.begin(), 2), result.first);
  1022. EXPECT_EQ(std::next(cont.begin(), 3), result.second);
  1023. result = cont.equal_range(11);
  1024. EXPECT_EQ(std::next(cont.begin(), 3), result.first);
  1025. EXPECT_EQ(std::next(cont.begin(), 4), result.second);
  1026. result = cont.equal_range(13);
  1027. EXPECT_EQ(std::next(cont.begin(), 4), result.first);
  1028. EXPECT_EQ(std::next(cont.begin(), 5), result.second);
  1029. result = cont.equal_range(15);
  1030. EXPECT_EQ(std::next(cont.begin(), 5), result.first);
  1031. EXPECT_EQ(std::next(cont.begin(), 6), result.second);
  1032. result = cont.equal_range(17);
  1033. EXPECT_EQ(std::next(cont.begin(), 6), result.first);
  1034. EXPECT_EQ(std::next(cont.begin(), 7), result.second);
  1035. result = cont.equal_range(19);
  1036. EXPECT_EQ(std::next(cont.begin(), 7), result.first);
  1037. EXPECT_EQ(std::next(cont.begin(), 8), result.second);
  1038. result = cont.equal_range(4);
  1039. EXPECT_EQ(std::next(cont.begin(), 0), result.first);
  1040. EXPECT_EQ(std::next(cont.begin(), 0), result.second);
  1041. result = cont.equal_range(6);
  1042. EXPECT_EQ(std::next(cont.begin(), 1), result.first);
  1043. EXPECT_EQ(std::next(cont.begin(), 1), result.second);
  1044. result = cont.equal_range(8);
  1045. EXPECT_EQ(std::next(cont.begin(), 2), result.first);
  1046. EXPECT_EQ(std::next(cont.begin(), 2), result.second);
  1047. result = cont.equal_range(10);
  1048. EXPECT_EQ(std::next(cont.begin(), 3), result.first);
  1049. EXPECT_EQ(std::next(cont.begin(), 3), result.second);
  1050. result = cont.equal_range(12);
  1051. EXPECT_EQ(std::next(cont.begin(), 4), result.first);
  1052. EXPECT_EQ(std::next(cont.begin(), 4), result.second);
  1053. result = cont.equal_range(14);
  1054. EXPECT_EQ(std::next(cont.begin(), 5), result.first);
  1055. EXPECT_EQ(std::next(cont.begin(), 5), result.second);
  1056. result = cont.equal_range(16);
  1057. EXPECT_EQ(std::next(cont.begin(), 6), result.first);
  1058. EXPECT_EQ(std::next(cont.begin(), 6), result.second);
  1059. result = cont.equal_range(18);
  1060. EXPECT_EQ(std::next(cont.begin(), 7), result.first);
  1061. EXPECT_EQ(std::next(cont.begin(), 7), result.second);
  1062. result = cont.equal_range(20);
  1063. EXPECT_EQ(std::next(cont.begin(), 8), result.first);
  1064. EXPECT_EQ(std::next(cont.begin(), 8), result.second);
  1065. }
  1066. }
  1067. // iterator lower_bound(const key_type& key);
  1068. // const_iterator lower_bound(const key_type& key) const;
  1069. TYPED_TEST_P(FlatTreeTest, LowerBound) {
  1070. {
  1071. TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
  1072. EXPECT_EQ(cont.begin(), cont.lower_bound(5));
  1073. EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
  1074. EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9));
  1075. EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11));
  1076. EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13));
  1077. EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15));
  1078. EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17));
  1079. EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19));
  1080. EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
  1081. EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
  1082. EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
  1083. EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
  1084. EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
  1085. EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
  1086. EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
  1087. EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
  1088. EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
  1089. }
  1090. {
  1091. const TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
  1092. EXPECT_EQ(cont.begin(), cont.lower_bound(5));
  1093. EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
  1094. EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9));
  1095. EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11));
  1096. EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13));
  1097. EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15));
  1098. EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17));
  1099. EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19));
  1100. EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
  1101. EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
  1102. EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
  1103. EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
  1104. EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
  1105. EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
  1106. EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
  1107. EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
  1108. EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
  1109. }
  1110. }
  1111. // iterator upper_bound(const key_type& key)
  1112. // const_iterator upper_bound(const key_type& key) const
  1113. TYPED_TEST_P(FlatTreeTest, UpperBound) {
  1114. {
  1115. TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
  1116. EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
  1117. EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
  1118. EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9));
  1119. EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11));
  1120. EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13));
  1121. EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15));
  1122. EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17));
  1123. EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19));
  1124. EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
  1125. EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
  1126. EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
  1127. EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
  1128. EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
  1129. EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
  1130. EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
  1131. EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
  1132. EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
  1133. }
  1134. {
  1135. const TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
  1136. EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
  1137. EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
  1138. EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9));
  1139. EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11));
  1140. EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13));
  1141. EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15));
  1142. EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17));
  1143. EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19));
  1144. EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
  1145. EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
  1146. EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
  1147. EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
  1148. EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
  1149. EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
  1150. EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
  1151. EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
  1152. EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
  1153. }
  1154. }
  1155. // ----------------------------------------------------------------------------
  1156. // General operations.
  1157. // void swap(flat_tree& other)
  1158. // void swap(flat_tree& lhs, flat_tree& rhs)
  1159. TYPED_TEST_P(FlatTreeTest, Swap) {
  1160. TypedTree<TypeParam> x({1, 2, 3});
  1161. TypedTree<TypeParam> y({4});
  1162. swap(x, y);
  1163. EXPECT_THAT(x, ElementsAre(4));
  1164. EXPECT_THAT(y, ElementsAre(1, 2, 3));
  1165. y.swap(x);
  1166. EXPECT_THAT(x, ElementsAre(1, 2, 3));
  1167. EXPECT_THAT(y, ElementsAre(4));
  1168. }
  1169. // bool operator==(const flat_tree& lhs, const flat_tree& rhs)
  1170. // bool operator!=(const flat_tree& lhs, const flat_tree& rhs)
  1171. // bool operator<(const flat_tree& lhs, const flat_tree& rhs)
  1172. // bool operator>(const flat_tree& lhs, const flat_tree& rhs)
  1173. // bool operator<=(const flat_tree& lhs, const flat_tree& rhs)
  1174. // bool operator>=(const flat_tree& lhs, const flat_tree& rhs)
  1175. TEST(FlatTree, Comparison) {
  1176. // Provided comparator does not participate in comparison.
  1177. ReversedTree biggest({3});
  1178. ReversedTree smallest({1});
  1179. ReversedTree middle({1, 2});
  1180. EXPECT_EQ(biggest, biggest);
  1181. EXPECT_NE(biggest, smallest);
  1182. EXPECT_LT(smallest, middle);
  1183. EXPECT_LE(smallest, middle);
  1184. EXPECT_LE(middle, middle);
  1185. EXPECT_GT(biggest, middle);
  1186. EXPECT_GE(biggest, middle);
  1187. EXPECT_GE(biggest, biggest);
  1188. }
  1189. TYPED_TEST_P(FlatTreeTest, EraseIf) {
  1190. TypedTree<TypeParam> x;
  1191. EXPECT_EQ(0u, base::EraseIf(x, [](int) { return false; }));
  1192. EXPECT_THAT(x, ElementsAre());
  1193. x = {1, 2, 3};
  1194. EXPECT_EQ(1u, base::EraseIf(x, [](int elem) { return !(elem & 1); }));
  1195. EXPECT_THAT(x, ElementsAre(1, 3));
  1196. x = {1, 2, 3, 4};
  1197. EXPECT_EQ(2u, base::EraseIf(x, [](int elem) { return elem & 1; }));
  1198. EXPECT_THAT(x, ElementsAre(2, 4));
  1199. }
  1200. // Test unsorted containers or containers with repeated elements cause a DCHECK
  1201. // if used with the sorted_unique tag.
  1202. TYPED_TEST_P(FlatTreeTest, SortedUniqueRangeConstructorDCHECKs) {
  1203. int unsorted[] = {2, 1};
  1204. EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, std::begin(unsorted),
  1205. std::end(unsorted)));
  1206. int repeated[] = {1, 2, 2};
  1207. EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, std::begin(repeated),
  1208. std::end(repeated)));
  1209. }
  1210. TYPED_TEST_P(FlatTreeTest, SortedUniqueVectorCopyConstructorDCHECKs) {
  1211. TypeParam unsorted = {2, 1};
  1212. EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, unsorted));
  1213. TypeParam repeated = {1, 2, 2};
  1214. EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, repeated));
  1215. }
  1216. TYPED_TEST_P(FlatTreeTest, SortedUniqueVectorMoveConstructorDCHECKs) {
  1217. TypeParam unsorted = {2, 1};
  1218. EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, std::move(unsorted)));
  1219. TypeParam repeated = {1, 2, 2};
  1220. EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, std::move(repeated)));
  1221. }
  1222. TYPED_TEST_P(FlatTreeTest, SortedUniqueInitializerListConstructorDCHECKs) {
  1223. std::initializer_list<int> unsorted = {2, 1};
  1224. EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, unsorted));
  1225. std::initializer_list<int> repeated = {1, 2, 2};
  1226. EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, repeated));
  1227. }
  1228. TYPED_TEST_P(FlatTreeTest, ReplaceDCHECKs) {
  1229. TypedTree<TypeParam> tree;
  1230. TypeParam unsorted = {2, 1};
  1231. EXPECT_DCHECK_DEATH(tree.replace(std::move(unsorted)));
  1232. TypeParam repeated = {1, 2, 2};
  1233. EXPECT_DCHECK_DEATH(tree.replace(std::move(repeated)));
  1234. }
  1235. REGISTER_TYPED_TEST_SUITE_P(FlatTreeTest,
  1236. DefaultConstructor,
  1237. CopyConstructor,
  1238. ContainerCopyConstructor,
  1239. InitializerListConstructor,
  1240. SortedUniqueContainerCopyConstructor,
  1241. SortedUniqueInitializerListConstructor,
  1242. CopyAssignable,
  1243. InitializerListAssignable,
  1244. Clear,
  1245. Size,
  1246. Empty,
  1247. Iterators,
  1248. InsertLValue,
  1249. InsertPositionLValue,
  1250. Emplace,
  1251. EmplacePosition,
  1252. Extract,
  1253. Replace,
  1254. ErasePosition,
  1255. EraseRange,
  1256. EraseKey,
  1257. EraseEndDeath,
  1258. Count,
  1259. Find,
  1260. Contains,
  1261. EqualRange,
  1262. LowerBound,
  1263. UpperBound,
  1264. Swap,
  1265. EraseIf,
  1266. SortedUniqueRangeConstructorDCHECKs,
  1267. SortedUniqueVectorCopyConstructorDCHECKs,
  1268. SortedUniqueVectorMoveConstructorDCHECKs,
  1269. SortedUniqueInitializerListConstructorDCHECKs,
  1270. ReplaceDCHECKs);
  1271. using IntSequenceContainers =
  1272. ::testing::Types<std::deque<int>, std::vector<int>>;
  1273. INSTANTIATE_TYPED_TEST_SUITE_P(My, FlatTreeTest, IntSequenceContainers);
  1274. } // namespace internal
  1275. } // namespace base