xref: /aosp_15_r20/external/pigweed/pw_containers/intrusive_multiset_test.cc (revision 61c4878ac05f98d0ceed94b57d316916de578985) 
1 // Copyright 2024 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 //     https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14 
15 #include "pw_containers/intrusive_multiset.h"
16 
17 #include "pw_compilation_testing/negative_compilation.h"
18 #include "pw_containers/intrusive_set.h"
19 #include "pw_span/span.h"
20 #include "pw_unit_test/framework.h"
21 
22 namespace {
23 
24 // Base item.
25 class BaseItem {
26  public:
BaseItem(size_t key,const char * name)27   BaseItem(size_t key, const char* name) : key_(key), name_(name) {}
28 
key() const29   constexpr const size_t& key() const { return key_; }
name() const30   constexpr const char* name() const { return name_; }
set_name(const char * name)31   void set_name(const char* name) { name_ = name; }
32 
operator <(const BaseItem & rhs) const33   constexpr bool operator<(const BaseItem& rhs) const {
34     return key() < rhs.key();
35   }
36 
37  private:
38   size_t key_;
39   const char* name_;
40 };
41 
42 // A basic item that can be used in a set.
43 struct TestItem : public ::pw::IntrusiveMultiSet<TestItem>::Item,
44                   public BaseItem {
TestItem__anond2d57d780111::TestItem45   TestItem(size_t key, const char* name) : BaseItem(key, name) {}
46 };
47 
48 // Test fixture.
49 class IntrusiveMultiSetTest : public ::testing::Test {
50  protected:
51   using IntrusiveMultiSet = ::pw::IntrusiveMultiSet<TestItem>;
52   static constexpr size_t kNumItems = 10;
53 
SetUp()54   void SetUp() override { multiset_.insert(items_.begin(), items_.end()); }
55 
TearDown()56   void TearDown() override { multiset_.clear(); }
57 
58   std::array<TestItem, kNumItems> items_ = {{
59       {30, "a"},
60       {50, "b"},
61       {20, "c"},
62       {40, "d"},
63       {10, "e"},
64       {35, "A"},
65       {55, "B"},
66       {25, "C"},
67       {45, "D"},
68       {15, "E"},
69   }};
70 
71   IntrusiveMultiSet multiset_;
72 };
73 
74 // Unit tests.
75 
TEST_F(IntrusiveMultiSetTest,Construct_Default)76 TEST_F(IntrusiveMultiSetTest, Construct_Default) {
77   IntrusiveMultiSet multiset;
78   EXPECT_TRUE(multiset.empty());
79   EXPECT_EQ(multiset.begin(), multiset.end());
80   EXPECT_EQ(multiset.rbegin(), multiset.rend());
81   EXPECT_EQ(multiset.size(), 0U);
82   EXPECT_EQ(multiset.lower_bound({0, "."}), multiset.end());
83   EXPECT_EQ(multiset.upper_bound({0, "."}), multiset.end());
84 }
85 
TEST_F(IntrusiveMultiSetTest,Construct_ObjectIterators)86 TEST_F(IntrusiveMultiSetTest, Construct_ObjectIterators) {
87   multiset_.clear();
88   IntrusiveMultiSet multiset(items_.begin(), items_.end());
89   EXPECT_FALSE(multiset.empty());
90   EXPECT_EQ(multiset.size(), items_.size());
91   multiset.clear();
92 }
93 
TEST_F(IntrusiveMultiSetTest,Construct_ObjectIterators_Empty)94 TEST_F(IntrusiveMultiSetTest, Construct_ObjectIterators_Empty) {
95   IntrusiveMultiSet multiset(items_.end(), items_.end());
96   EXPECT_TRUE(multiset.empty());
97   EXPECT_EQ(multiset.size(), 0U);
98 }
99 
TEST_F(IntrusiveMultiSetTest,Construct_PointerIterators)100 TEST_F(IntrusiveMultiSetTest, Construct_PointerIterators) {
101   std::array<TestItem*, 3> ptrs = {&items_[0], &items_[1], &items_[2]};
102   multiset_.clear();
103   IntrusiveMultiSet multiset(ptrs.begin(), ptrs.end());
104   EXPECT_FALSE(multiset.empty());
105   EXPECT_EQ(multiset.size(), 3U);
106   multiset.clear();
107 }
108 
TEST_F(IntrusiveMultiSetTest,Construct_PointerIterators_Empty)109 TEST_F(IntrusiveMultiSetTest, Construct_PointerIterators_Empty) {
110   std::array<TestItem*, 0> ptrs;
111   IntrusiveMultiSet multiset(ptrs.begin(), ptrs.end());
112   EXPECT_TRUE(multiset.empty());
113   EXPECT_EQ(multiset.size(), 0U);
114   multiset.clear();
115 }
116 
TEST_F(IntrusiveMultiSetTest,Construct_InitializerList)117 TEST_F(IntrusiveMultiSetTest, Construct_InitializerList) {
118   multiset_.clear();
119   IntrusiveMultiSet multiset({&items_[0], &items_[2], &items_[4]});
120   auto iter = multiset.begin();
121   EXPECT_EQ((iter++)->key(), 10U);
122   EXPECT_EQ((iter++)->key(), 20U);
123   EXPECT_EQ((iter++)->key(), 30U);
124   EXPECT_EQ(iter, multiset.end());
125   multiset.clear();
126 }
127 
TEST_F(IntrusiveMultiSetTest,Construct_InitializerList_Empty)128 TEST_F(IntrusiveMultiSetTest, Construct_InitializerList_Empty) {
129   IntrusiveMultiSet multiset({});
130   EXPECT_TRUE(multiset.empty());
131   EXPECT_EQ(multiset.size(), 0U);
132 }
133 
TEST_F(IntrusiveMultiSetTest,Construct_CustomCompare)134 TEST_F(IntrusiveMultiSetTest, Construct_CustomCompare) {
135   auto greater_than = [](const BaseItem& lhs, const BaseItem& rhs) {
136     return lhs.key() > rhs.key();
137   };
138   multiset_.clear();
139   IntrusiveMultiSet multiset({&items_[0], &items_[2], &items_[4]},
140                              std::move(greater_than));
141   auto iter = multiset.begin();
142   EXPECT_EQ((iter++)->key(), 30U);
143   EXPECT_EQ((iter++)->key(), 20U);
144   EXPECT_EQ((iter++)->key(), 10U);
145   EXPECT_EQ(iter, multiset.end());
146   multiset.clear();
147 }
148 
149 //  A struct that is not a multiset item.
150 struct NotAnItem : public BaseItem {
NotAnItem__anond2d57d780111::NotAnItem151   NotAnItem(size_t key, const char* name) : BaseItem(key, name) {}
152 };
153 
154 #if PW_NC_TEST(IncompatibleItem)
155 PW_NC_EXPECT(
156     "IntrusiveMultiSet items must be derived from IntrusiveMultiSet<T>::Item");
157 
158 class BadItem : public ::pw::IntrusiveMultiSet<NotAnItem>::Item {
159  public:
operator <(const BadItem & rhs) const160   constexpr bool operator<(const BadItem& rhs) const { return this < &rhs; }
161 };
162 
163 [[maybe_unused]] ::pw::IntrusiveMultiSet<BadItem> bad_multiset1;
164 
165 #elif PW_NC_TEST(DoesNotInheritFromItem)
166 PW_NC_EXPECT(
167     "IntrusiveMultiSet items must be derived from IntrusiveMultiSet<T>::Item");
168 
169 [[maybe_unused]] ::pw::IntrusiveMultiSet<NotAnItem> bad_multiset2;
170 
171 #endif  // PW_NC_TEST
172 
173 // Iterators
174 
TEST_F(IntrusiveMultiSetTest,Iterator)175 TEST_F(IntrusiveMultiSetTest, Iterator) {
176   const IntrusiveMultiSet& multiset = multiset_;
177   auto iter = multiset.begin();
178   size_t key = 10;
179   for (size_t i = 0; i < kNumItems; ++i) {
180     auto& item = *iter++;
181     EXPECT_EQ(item.key(), key);
182     key += 5;
183   }
184   EXPECT_EQ(key, 60U);
185   EXPECT_EQ(iter, multiset.end());
186   EXPECT_EQ(iter, multiset.cend());
187   for (size_t i = 0; i < kNumItems; ++i) {
188     key -= 5;
189     EXPECT_EQ((--iter)->key(), key);
190   }
191   EXPECT_EQ(key, 10U);
192   EXPECT_EQ(iter, multiset.begin());
193   EXPECT_EQ(iter, multiset.cbegin());
194 }
195 
TEST_F(IntrusiveMultiSetTest,ReverseIterator)196 TEST_F(IntrusiveMultiSetTest, ReverseIterator) {
197   const IntrusiveMultiSet& multiset = multiset_;
198   auto iter = multiset.rbegin();
199   size_t key = 55;
200   for (size_t i = 0; i < kNumItems; ++i) {
201     auto& item = *iter++;
202     EXPECT_EQ(item.key(), key);
203     key -= 5;
204   }
205   EXPECT_EQ(key, 5U);
206   EXPECT_EQ(iter, multiset.rend());
207   EXPECT_EQ(iter, multiset.crend());
208   for (size_t i = 0; i < kNumItems; ++i) {
209     key += 5;
210     EXPECT_EQ((--iter)->key(), key);
211   }
212   EXPECT_EQ(key, 55U);
213   EXPECT_EQ(iter, multiset.rbegin());
214   EXPECT_EQ(iter, multiset.crbegin());
215 }
216 
TEST_F(IntrusiveMultiSetTest,ConstIterator_CompareNonConst)217 TEST_F(IntrusiveMultiSetTest, ConstIterator_CompareNonConst) {
218   EXPECT_EQ(multiset_.end(), multiset_.cend());
219 }
220 
221 // A multiset item that is distinct from TestItem
222 struct OtherItem : public ::pw::IntrusiveMultiSet<OtherItem>::Item,
223                    public BaseItem {
OtherItem__anond2d57d780111::OtherItem224   OtherItem(size_t key, const char* name) : BaseItem(key, name) {}
225 };
226 
TEST_F(IntrusiveMultiSetTest,ConstIterator_CompareNonConst_CompilationFails)227 TEST_F(IntrusiveMultiSetTest, ConstIterator_CompareNonConst_CompilationFails) {
228   ::pw::IntrusiveMultiSet<OtherItem> multiset;
229 #if PW_NC_TEST(CannotCompareIncompatibleIteratorsEqual)
230   PW_NC_EXPECT("multiset_\.end\(\) == multiset\.end\(\)");
231   static_cast<void>(multiset_.end() == multiset.end());
232 #elif PW_NC_TEST(CannotCompareIncompatibleIteratorsInequal)
233   PW_NC_EXPECT("multiset_\.end\(\) != multiset\.end\(\)");
234   static_cast<void>(multiset_.end() != multiset.end());
235 #endif  // PW_NC_TEST
236 }
237 
238 #if PW_NC_TEST(CannotModifyThroughConstIterator)
239 PW_NC_EXPECT("function is not marked const|discards qualifiers");
240 
TEST_F(IntrusiveMultiSetTest,ConstIterator_Modify)241 TEST_F(IntrusiveMultiSetTest, ConstIterator_Modify) {
242   const IntrusiveMultiSet& multiset = multiset_;
243   auto iter = multiset.begin();
244   iter->set_name("nope");
245 }
246 
247 #endif  // PW_NC_TEST
248 
249 // Capacity
250 
TEST_F(IntrusiveMultiSetTest,IsEmpty)251 TEST_F(IntrusiveMultiSetTest, IsEmpty) {
252   const IntrusiveMultiSet& multiset = multiset_;
253   EXPECT_FALSE(multiset.empty());
254   multiset_.clear();
255   EXPECT_TRUE(multiset.empty());
256 }
257 
TEST_F(IntrusiveMultiSetTest,GetSize)258 TEST_F(IntrusiveMultiSetTest, GetSize) {
259   const IntrusiveMultiSet& multiset = multiset_;
260   EXPECT_EQ(multiset.size(), kNumItems);
261   multiset_.clear();
262   EXPECT_EQ(multiset.size(), 0U);
263 }
264 
TEST_F(IntrusiveMultiSetTest,GetMaxSize)265 TEST_F(IntrusiveMultiSetTest, GetMaxSize) {
266   const IntrusiveMultiSet& multiset = multiset_;
267   EXPECT_EQ(multiset.max_size(), size_t(std::numeric_limits<ptrdiff_t>::max()));
268 }
269 
270 // Modifiers
271 
272 // This functions allows tests to use `std::is_sorted` without specializing
273 // `std::less<TestItem>`. Since `std::less` is the default value for the
274 // `Compare` template parameter, leaving it untouched avoids accidentally
275 // masking type-handling errors.
LessThan(const TestItem & lhs,const TestItem & rhs)276 constexpr bool LessThan(const TestItem& lhs, const TestItem& rhs) {
277   return lhs < rhs;
278 }
279 
TEST_F(IntrusiveMultiSetTest,Insert)280 TEST_F(IntrusiveMultiSetTest, Insert) {
281   multiset_.clear();
282   bool sorted = true;
283   size_t prev_key = 0;
284   for (auto& item : items_) {
285     sorted &= prev_key < item.key();
286 
287     // Use the "hinted" version of insert.
288     multiset_.insert(multiset_.end(), item);
289     prev_key = item.key();
290   }
291   EXPECT_FALSE(sorted);
292 
293   EXPECT_EQ(multiset_.size(), kNumItems);
294   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
295 }
296 
TEST_F(IntrusiveMultiSetTest,Insert_Duplicate)297 TEST_F(IntrusiveMultiSetTest, Insert_Duplicate) {
298   TestItem item1(60, "1");
299   TestItem item2(60, "2");
300 
301   auto iter = multiset_.insert(item1);
302   EXPECT_STREQ(iter->name(), "1");
303 
304   iter = multiset_.insert(item2);
305   EXPECT_STREQ(iter->name(), "2");
306 
307   EXPECT_EQ(multiset_.size(), kNumItems + 2);
308   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
309 
310   // Explicitly clear the multiset before item 1 goes out of scope.
311   multiset_.clear();
312 }
313 
TEST_F(IntrusiveMultiSetTest,Insert_ObjectIterators)314 TEST_F(IntrusiveMultiSetTest, Insert_ObjectIterators) {
315   multiset_.clear();
316   multiset_.insert(items_.begin(), items_.end());
317   EXPECT_EQ(multiset_.size(), kNumItems);
318   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
319 }
320 
TEST_F(IntrusiveMultiSetTest,Insert_ObjectIterators_Empty)321 TEST_F(IntrusiveMultiSetTest, Insert_ObjectIterators_Empty) {
322   multiset_.insert(items_.end(), items_.end());
323   EXPECT_EQ(multiset_.size(), kNumItems);
324   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
325 }
326 
TEST_F(IntrusiveMultiSetTest,Insert_ObjectIterators_WithDuplicates)327 TEST_F(IntrusiveMultiSetTest, Insert_ObjectIterators_WithDuplicates) {
328   std::array<TestItem, 3> items = {{
329       {50, "B"},
330       {40, "D"},
331       {60, "F"},
332   }};
333 
334   multiset_.insert(items.begin(), items.end());
335   EXPECT_EQ(multiset_.size(), kNumItems + 3);
336   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
337 
338   auto iter = multiset_.find(items[0]);
339   ASSERT_NE(iter, multiset_.end());
340   EXPECT_STREQ((iter++)->name(), "b");
341   EXPECT_STREQ(iter->name(), "B");
342 
343   iter = multiset_.find(items[1]);
344   ASSERT_NE(iter, multiset_.end());
345   EXPECT_STREQ((iter++)->name(), "d");
346   EXPECT_STREQ(iter->name(), "D");
347 
348   iter = multiset_.find(items[2]);
349   ASSERT_NE(iter, multiset_.end());
350   EXPECT_STREQ(iter->name(), "F");
351 
352   // Explicitly clear the multiset before items goes out of scope.
353   multiset_.clear();
354 }
355 
TEST_F(IntrusiveMultiSetTest,Insert_PointerIterators)356 TEST_F(IntrusiveMultiSetTest, Insert_PointerIterators) {
357   multiset_.clear();
358   std::array<TestItem*, 3> ptrs = {&items_[0], &items_[1], &items_[2]};
359 
360   multiset_.insert(ptrs.begin(), ptrs.end());
361   EXPECT_EQ(multiset_.size(), 3U);
362   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
363 }
364 
TEST_F(IntrusiveMultiSetTest,Insert_PointerIterators_Empty)365 TEST_F(IntrusiveMultiSetTest, Insert_PointerIterators_Empty) {
366   std::array<TestItem*, 0> ptrs;
367 
368   multiset_.insert(ptrs.begin(), ptrs.end());
369   EXPECT_EQ(multiset_.size(), kNumItems);
370   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
371 }
372 
TEST_F(IntrusiveMultiSetTest,Insert_PointerIterators_WithDuplicates)373 TEST_F(IntrusiveMultiSetTest, Insert_PointerIterators_WithDuplicates) {
374   TestItem item1(50, "B");
375   TestItem item2(40, "D");
376   TestItem item3(60, "F");
377   std::array<TestItem*, 3> ptrs = {&item1, &item2, &item3};
378 
379   multiset_.insert(ptrs.begin(), ptrs.end());
380   EXPECT_EQ(multiset_.size(), kNumItems + 3);
381   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
382 
383   auto iter = multiset_.find(item1);
384   ASSERT_NE(iter, multiset_.end());
385   EXPECT_STREQ((iter++)->name(), "b");
386   EXPECT_STREQ(iter->name(), "B");
387 
388   iter = multiset_.find(item2);
389   ASSERT_NE(iter, multiset_.end());
390   EXPECT_STREQ((iter++)->name(), "d");
391   EXPECT_STREQ(iter->name(), "D");
392 
393   iter = multiset_.find(item3);
394   ASSERT_NE(iter, multiset_.end());
395   EXPECT_STREQ(iter->name(), "F");
396 
397   // Explicitly clear the multiset before items goes out of scope.
398   multiset_.clear();
399 }
400 
TEST_F(IntrusiveMultiSetTest,Insert_InitializerList)401 TEST_F(IntrusiveMultiSetTest, Insert_InitializerList) {
402   multiset_.clear();
403   multiset_.insert({&items_[0], &items_[2], &items_[4]});
404   EXPECT_EQ(multiset_.size(), 3U);
405   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
406 }
407 
TEST_F(IntrusiveMultiSetTest,Insert_InitializerList_Empty)408 TEST_F(IntrusiveMultiSetTest, Insert_InitializerList_Empty) {
409   multiset_.insert({});
410   EXPECT_EQ(multiset_.size(), kNumItems);
411   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
412 }
413 
TEST_F(IntrusiveMultiSetTest,Insert_InitializerList_WithDuplicates)414 TEST_F(IntrusiveMultiSetTest, Insert_InitializerList_WithDuplicates) {
415   TestItem item1(50, "B");
416   TestItem item2(40, "D");
417   TestItem item3(60, "F");
418 
419   multiset_.insert({&item1, &item2, &item3});
420   EXPECT_EQ(multiset_.size(), kNumItems + 3);
421   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
422 
423   auto iter = multiset_.find(item1);
424   ASSERT_NE(iter, multiset_.end());
425   EXPECT_STREQ((iter++)->name(), "b");
426   EXPECT_STREQ(iter->name(), "B");
427 
428   iter = multiset_.find(item2);
429   ASSERT_NE(iter, multiset_.end());
430   EXPECT_STREQ((iter++)->name(), "d");
431   EXPECT_STREQ(iter->name(), "D");
432 
433   iter = multiset_.find(item3);
434   ASSERT_NE(iter, multiset_.end());
435   EXPECT_STREQ(iter->name(), "F");
436 
437   // Explicitly clear the multiset before items goes out of scope.
438   multiset_.clear();
439 }
440 
441 // An item derived from TestItem.
442 struct DerivedItem : public TestItem {
DerivedItem__anond2d57d780111::DerivedItem443   DerivedItem(size_t n, const char* name) : TestItem(n * 10, name) {}
444 };
445 
TEST_F(IntrusiveMultiSetTest,Insert_DerivedItems)446 TEST_F(IntrusiveMultiSetTest, Insert_DerivedItems) {
447   DerivedItem item1(6, "f");
448   multiset_.insert(item1);
449 
450   DerivedItem item2(7, "g");
451   multiset_.insert(item2);
452 
453   EXPECT_EQ(multiset_.size(), kNumItems + 2);
454   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
455 
456   // Explicitly clear the multiset before items goes out of scope.
457   multiset_.clear();
458 }
459 
TEST_F(IntrusiveMultiSetTest,Insert_DerivedItems_CompilationFails)460 TEST_F(IntrusiveMultiSetTest, Insert_DerivedItems_CompilationFails) {
461   ::pw::IntrusiveMultiSet<DerivedItem> derived_from_compatible_item_type;
462 
463   DerivedItem item1(6, "f");
464   derived_from_compatible_item_type.insert(item1);
465 
466   EXPECT_EQ(derived_from_compatible_item_type.size(), 1U);
467 
468 #if PW_NC_TEST(CannotAddBaseClassToDerivedClassSet)
469   PW_NC_EXPECT("derived_from_compatible_item_type\.insert\(item2\)");
470 
471   TestItem item2(70, "g");
472   derived_from_compatible_item_type.insert(item2);
473 #endif
474   derived_from_compatible_item_type.clear();
475 }
476 
TEST_F(IntrusiveMultiSetTest,Erase_OneItem)477 TEST_F(IntrusiveMultiSetTest, Erase_OneItem) {
478   for (size_t i = 0; i < kNumItems; ++i) {
479     EXPECT_EQ(multiset_.size(), kNumItems);
480     EXPECT_EQ(multiset_.erase(items_[i]), 1U);
481     EXPECT_EQ(multiset_.size(), kNumItems - 1);
482     auto iter = multiset_.find(items_[i]);
483     EXPECT_EQ(iter, multiset_.end());
484     multiset_.insert(items_[i]);
485   }
486 }
487 
TEST_F(IntrusiveMultiSetTest,Erase_OnlyItem)488 TEST_F(IntrusiveMultiSetTest, Erase_OnlyItem) {
489   multiset_.clear();
490   multiset_.insert(items_[0]);
491   EXPECT_EQ(multiset_.size(), 1U);
492 
493   EXPECT_EQ(multiset_.erase(items_[0]), 1U);
494   EXPECT_EQ(multiset_.size(), 0U);
495 }
496 
TEST_F(IntrusiveMultiSetTest,Erase_AllOnebyOne)497 TEST_F(IntrusiveMultiSetTest, Erase_AllOnebyOne) {
498   auto iter = multiset_.begin();
499   for (size_t n = kNumItems; n != 0; --n) {
500     ASSERT_NE(iter, multiset_.end());
501     iter = multiset_.erase(iter);
502   }
503   EXPECT_EQ(iter, multiset_.end());
504   EXPECT_EQ(multiset_.size(), 0U);
505 }
506 
TEST_F(IntrusiveMultiSetTest,Erase_Range)507 TEST_F(IntrusiveMultiSetTest, Erase_Range) {
508   auto first = multiset_.begin();
509   auto last = multiset_.end();
510   ++first;
511   --last;
512   auto iter = multiset_.erase(first, last);
513   EXPECT_EQ(multiset_.size(), 2U);
514   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
515   EXPECT_EQ(iter->key(), 55U);
516 }
517 
TEST_F(IntrusiveMultiSetTest,Erase_MissingItem)518 TEST_F(IntrusiveMultiSetTest, Erase_MissingItem) {
519   EXPECT_EQ(multiset_.erase({100, "-"}), 0U);
520 }
521 
TEST_F(IntrusiveMultiSetTest,Erase_Reinsert)522 TEST_F(IntrusiveMultiSetTest, Erase_Reinsert) {
523   EXPECT_EQ(multiset_.size(), items_.size());
524 
525   EXPECT_EQ(multiset_.erase(items_[0]), 1U);
526   EXPECT_EQ(multiset_.find(items_[0]), multiset_.end());
527 
528   EXPECT_EQ(multiset_.erase(items_[2]), 1U);
529   EXPECT_EQ(multiset_.find(items_[2]), multiset_.end());
530 
531   EXPECT_EQ(multiset_.erase(items_[4]), 1U);
532   EXPECT_EQ(multiset_.find(items_[4]), multiset_.end());
533 
534   EXPECT_EQ(multiset_.size(), items_.size() - 3);
535 
536   multiset_.insert(items_[4]);
537   auto iter = multiset_.find(items_[4]);
538   EXPECT_NE(iter, multiset_.end());
539 
540   multiset_.insert(items_[0]);
541   iter = multiset_.find(items_[0]);
542   EXPECT_NE(iter, multiset_.end());
543 
544   multiset_.insert(items_[2]);
545   iter = multiset_.find(items_[2]);
546   EXPECT_NE(iter, multiset_.end());
547 
548   EXPECT_EQ(multiset_.size(), items_.size());
549 }
550 
TEST_F(IntrusiveMultiSetTest,Erase_Duplicate)551 TEST_F(IntrusiveMultiSetTest, Erase_Duplicate) {
552   TestItem item1(32, "1");
553   TestItem item2(32, "2");
554   TestItem item3(32, "3");
555   multiset_.insert(item1);
556   multiset_.insert(item2);
557   multiset_.insert(item3);
558 
559   auto iter = multiset_.find({32, "?"});
560   ASSERT_NE(iter, multiset_.end());
561   EXPECT_STREQ(iter->name(), "1");
562 
563   iter = multiset_.erase(iter);
564   ASSERT_NE(iter, multiset_.end());
565   EXPECT_STREQ(iter->name(), "2");
566 
567   iter = multiset_.erase(iter);
568   ASSERT_NE(iter, multiset_.end());
569   EXPECT_STREQ(iter->name(), "3");
570 
571   multiset_.erase(iter);
572   EXPECT_EQ(multiset_.find({32, "?"}), multiset_.end());
573 }
574 
TEST_F(IntrusiveMultiSetTest,Swap)575 TEST_F(IntrusiveMultiSetTest, Swap) {
576   std::array<TestItem, 3> items = {{
577       {50, "B"},
578       {40, "D"},
579       {60, "F"},
580   }};
581   IntrusiveMultiSet multiset(items.begin(), items.end());
582 
583   multiset_.swap(multiset);
584   EXPECT_EQ(multiset.size(), kNumItems);
585   EXPECT_TRUE(std::is_sorted(multiset.begin(), multiset.end(), LessThan));
586   auto iter = multiset.begin();
587   EXPECT_STREQ((iter++)->name(), "e");
588   EXPECT_STREQ((iter++)->name(), "E");
589   EXPECT_STREQ((iter++)->name(), "c");
590   EXPECT_STREQ((iter++)->name(), "C");
591   EXPECT_STREQ((iter++)->name(), "a");
592   EXPECT_STREQ((iter++)->name(), "A");
593   EXPECT_STREQ((iter++)->name(), "d");
594   EXPECT_STREQ((iter++)->name(), "D");
595   EXPECT_STREQ((iter++)->name(), "b");
596   EXPECT_STREQ((iter++)->name(), "B");
597   EXPECT_EQ(iter, multiset.end());
598   multiset.clear();
599 
600   EXPECT_EQ(multiset_.size(), 3U);
601   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
602   iter = multiset_.begin();
603   EXPECT_STREQ((iter++)->name(), "D");
604   EXPECT_STREQ((iter++)->name(), "B");
605   EXPECT_STREQ((iter++)->name(), "F");
606   EXPECT_EQ(iter, multiset_.end());
607 
608   // Explicitly clear the multiset before items goes out of scope.
609   multiset_.clear();
610 }
611 
TEST_F(IntrusiveMultiSetTest,Swap_Empty)612 TEST_F(IntrusiveMultiSetTest, Swap_Empty) {
613   IntrusiveMultiSet multiset;
614 
615   multiset_.swap(multiset);
616   EXPECT_EQ(multiset.size(), kNumItems);
617   EXPECT_TRUE(std::is_sorted(multiset.begin(), multiset.end(), LessThan));
618   auto iter = multiset.begin();
619   EXPECT_STREQ((iter++)->name(), "e");
620   EXPECT_STREQ((iter++)->name(), "E");
621   EXPECT_STREQ((iter++)->name(), "c");
622   EXPECT_STREQ((iter++)->name(), "C");
623   EXPECT_STREQ((iter++)->name(), "a");
624   EXPECT_STREQ((iter++)->name(), "A");
625   EXPECT_STREQ((iter++)->name(), "d");
626   EXPECT_STREQ((iter++)->name(), "D");
627   EXPECT_STREQ((iter++)->name(), "b");
628   EXPECT_STREQ((iter++)->name(), "B");
629   EXPECT_EQ(iter, multiset.end());
630   multiset.clear();
631 
632   EXPECT_EQ(multiset_.size(), 0U);
633 }
634 
TEST_F(IntrusiveMultiSetTest,Merge)635 TEST_F(IntrusiveMultiSetTest, Merge) {
636   std::array<TestItem, 3> items = {{
637       {5, "f"},
638       {75, "g"},
639       {85, "h"},
640   }};
641   IntrusiveMultiSet multiset(items.begin(), items.end());
642 
643   multiset_.merge(multiset);
644   EXPECT_TRUE(multiset.empty());
645   EXPECT_EQ(multiset_.size(), kNumItems + 3);
646   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
647   auto iter = multiset_.begin();
648   EXPECT_STREQ((iter++)->name(), "f");
649   EXPECT_STREQ((iter++)->name(), "e");
650   EXPECT_STREQ((iter++)->name(), "E");
651   EXPECT_STREQ((iter++)->name(), "c");
652   EXPECT_STREQ((iter++)->name(), "C");
653   EXPECT_STREQ((iter++)->name(), "a");
654   EXPECT_STREQ((iter++)->name(), "A");
655   EXPECT_STREQ((iter++)->name(), "d");
656   EXPECT_STREQ((iter++)->name(), "D");
657   EXPECT_STREQ((iter++)->name(), "b");
658   EXPECT_STREQ((iter++)->name(), "B");
659   EXPECT_STREQ((iter++)->name(), "g");
660   EXPECT_STREQ((iter++)->name(), "h");
661   EXPECT_EQ(iter, multiset_.end());
662 
663   // Explicitly clear the multiset before items goes out of scope.
664   multiset_.clear();
665 }
666 
TEST_F(IntrusiveMultiSetTest,Merge_Empty)667 TEST_F(IntrusiveMultiSetTest, Merge_Empty) {
668   IntrusiveMultiSet multiset;
669 
670   multiset_.merge(multiset);
671   EXPECT_EQ(multiset_.size(), kNumItems);
672   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
673 
674   multiset.merge(multiset_);
675   EXPECT_TRUE(multiset_.empty());
676   EXPECT_EQ(multiset.size(), kNumItems);
677   EXPECT_TRUE(std::is_sorted(multiset.begin(), multiset.end(), LessThan));
678 
679   multiset.clear();
680 }
681 
TEST_F(IntrusiveMultiSetTest,Merge_WithDuplicates)682 TEST_F(IntrusiveMultiSetTest, Merge_WithDuplicates) {
683   std::array<TestItem, 3> items = {{
684       {15, "f"},
685       {45, "g"},
686       {55, "h"},
687   }};
688   IntrusiveMultiSet multiset(items.begin(), items.end());
689 
690   multiset_.merge(multiset);
691   EXPECT_TRUE(multiset.empty());
692   EXPECT_EQ(multiset_.size(), kNumItems + 3);
693   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
694   auto iter = multiset_.begin();
695   EXPECT_STREQ((iter++)->name(), "e");
696   EXPECT_STREQ((iter++)->name(), "E");
697   EXPECT_STREQ((iter++)->name(), "f");
698   EXPECT_STREQ((iter++)->name(), "c");
699   EXPECT_STREQ((iter++)->name(), "C");
700   EXPECT_STREQ((iter++)->name(), "a");
701   EXPECT_STREQ((iter++)->name(), "A");
702   EXPECT_STREQ((iter++)->name(), "d");
703   EXPECT_STREQ((iter++)->name(), "D");
704   EXPECT_STREQ((iter++)->name(), "g");
705   EXPECT_STREQ((iter++)->name(), "b");
706   EXPECT_STREQ((iter++)->name(), "B");
707   EXPECT_STREQ((iter++)->name(), "h");
708   EXPECT_EQ(iter, multiset_.end());
709 
710   // Explicitly clear the multiset before items goes out of scope.
711   multiset_.clear();
712 }
713 
TEST_F(IntrusiveMultiSetTest,Merge_Set)714 TEST_F(IntrusiveMultiSetTest, Merge_Set) {
715   std::array<TestItem, 3> items = {{
716       {15, "f"},
717       {45, "g"},
718       {55, "h"},
719   }};
720   ::pw::IntrusiveSet<TestItem> set(items.begin(), items.end());
721 
722   multiset_.merge(set);
723   EXPECT_TRUE(set.empty());
724   EXPECT_EQ(multiset_.size(), kNumItems + 3);
725   EXPECT_TRUE(std::is_sorted(multiset_.begin(), multiset_.end(), LessThan));
726   auto iter = multiset_.begin();
727   EXPECT_STREQ((iter++)->name(), "e");
728   EXPECT_STREQ((iter++)->name(), "E");
729   EXPECT_STREQ((iter++)->name(), "f");
730   EXPECT_STREQ((iter++)->name(), "c");
731   EXPECT_STREQ((iter++)->name(), "C");
732   EXPECT_STREQ((iter++)->name(), "a");
733   EXPECT_STREQ((iter++)->name(), "A");
734   EXPECT_STREQ((iter++)->name(), "d");
735   EXPECT_STREQ((iter++)->name(), "D");
736   EXPECT_STREQ((iter++)->name(), "g");
737   EXPECT_STREQ((iter++)->name(), "b");
738   EXPECT_STREQ((iter++)->name(), "B");
739   EXPECT_STREQ((iter++)->name(), "h");
740   EXPECT_EQ(iter, multiset_.end());
741 
742   // Explicitly clear the multiset before items goes out of scope.
743   multiset_.clear();
744 }
745 
TEST_F(IntrusiveMultiSetTest,Count)746 TEST_F(IntrusiveMultiSetTest, Count) {
747   const IntrusiveMultiSet& multiset = multiset_;
748   EXPECT_EQ(multiset.count({10, "?"}), 1U);
749   EXPECT_EQ(multiset.count({20, "?"}), 1U);
750   EXPECT_EQ(multiset.count({30, "?"}), 1U);
751   EXPECT_EQ(multiset.count({40, "?"}), 1U);
752   EXPECT_EQ(multiset.count({50, "?"}), 1U);
753 }
754 
TEST_F(IntrusiveMultiSetTest,Count_NoSuchKey)755 TEST_F(IntrusiveMultiSetTest, Count_NoSuchKey) {
756   const IntrusiveMultiSet& multiset = multiset_;
757   EXPECT_EQ(multiset.count({60, "?"}), 0U);
758 }
759 
TEST_F(IntrusiveMultiSetTest,Count_WithDuplicates)760 TEST_F(IntrusiveMultiSetTest, Count_WithDuplicates) {
761   std::array<TestItem, 3> items = {{
762       {50, "B"},
763       {40, "D"},
764       {60, "F"},
765   }};
766   multiset_.insert(items.begin(), items.end());
767 
768   EXPECT_EQ(multiset_.count({10, "?"}), 1U);
769   EXPECT_EQ(multiset_.count({20, "?"}), 1U);
770   EXPECT_EQ(multiset_.count({30, "?"}), 1U);
771   EXPECT_EQ(multiset_.count({40, "?"}), 2U);
772   EXPECT_EQ(multiset_.count({50, "?"}), 2U);
773   EXPECT_EQ(multiset_.count({60, "?"}), 1U);
774 
775   // Explicitly clear the multiset before items goes out of scope.
776   multiset_.clear();
777 }
778 
TEST_F(IntrusiveMultiSetTest,Find)779 TEST_F(IntrusiveMultiSetTest, Find) {
780   const IntrusiveMultiSet& multiset = multiset_;
781   size_t key = 10;
782   for (size_t i = 0; i < kNumItems; ++i) {
783     auto iter = multiset.find({key, "?"});
784     ASSERT_NE(iter, multiset.end());
785     EXPECT_EQ(iter->key(), key);
786     key += 5;
787   }
788 }
789 
TEST_F(IntrusiveMultiSetTest,Find_NoSuchKey)790 TEST_F(IntrusiveMultiSetTest, Find_NoSuchKey) {
791   const IntrusiveMultiSet& multiset = multiset_;
792   auto iter = multiset.find({60, "?"});
793   EXPECT_EQ(iter, multiset.end());
794 }
795 
TEST_F(IntrusiveMultiSetTest,Find_WithDuplicates)796 TEST_F(IntrusiveMultiSetTest, Find_WithDuplicates) {
797   std::array<TestItem, 3> items = {{
798       {50, "B"},
799       {40, "D"},
800       {60, "F"},
801   }};
802   multiset_.insert(items.begin(), items.end());
803 
804   auto iter = multiset_.find({40, "?"});
805   ASSERT_NE(iter, multiset_.end());
806   EXPECT_EQ(iter->key(), 40U);
807   EXPECT_EQ((iter++)->name(), "d");
808   EXPECT_EQ(iter->key(), 40U);
809   EXPECT_EQ(iter->name(), "D");
810 
811   iter = multiset_.find({50, "?"});
812   ASSERT_NE(iter, multiset_.end());
813   EXPECT_EQ(iter->key(), 50U);
814   EXPECT_EQ((iter++)->name(), "b");
815   EXPECT_EQ(iter->key(), 50U);
816   EXPECT_EQ(iter->name(), "B");
817 
818   // Explicitly clear the multiset before items goes out of scope.
819   multiset_.clear();
820 }
821 
TEST_F(IntrusiveMultiSetTest,LowerBound)822 TEST_F(IntrusiveMultiSetTest, LowerBound) {
823   const IntrusiveMultiSet& multiset = multiset_;
824   auto iter = multiset.lower_bound({10, "?"});
825   ASSERT_NE(iter, multiset.end());
826   EXPECT_STREQ(iter->name(), "e");
827 
828   iter = multiset.lower_bound({20, "?"});
829   ASSERT_NE(iter, multiset.end());
830   EXPECT_STREQ(iter->name(), "c");
831 
832   iter = multiset.lower_bound({30, "?"});
833   ASSERT_NE(iter, multiset.end());
834   EXPECT_STREQ(iter->name(), "a");
835 
836   iter = multiset.lower_bound({40, "?"});
837   ASSERT_NE(iter, multiset.end());
838   EXPECT_STREQ(iter->name(), "d");
839 
840   iter = multiset.lower_bound({50, "?"});
841   ASSERT_NE(iter, multiset.end());
842   EXPECT_STREQ(iter->name(), "b");
843 }
844 
TEST_F(IntrusiveMultiSetTest,LowerBound_NoExactKey)845 TEST_F(IntrusiveMultiSetTest, LowerBound_NoExactKey) {
846   const IntrusiveMultiSet& multiset = multiset_;
847   auto iter = multiset.lower_bound({6, "?"});
848   ASSERT_NE(iter, multiset.end());
849   EXPECT_STREQ(iter->name(), "e");
850 
851   iter = multiset.lower_bound({16, "?"});
852   ASSERT_NE(iter, multiset.end());
853   EXPECT_STREQ(iter->name(), "c");
854 
855   iter = multiset.lower_bound({26, "?"});
856   ASSERT_NE(iter, multiset.end());
857   EXPECT_STREQ(iter->name(), "a");
858 
859   iter = multiset.lower_bound({36, "?"});
860   ASSERT_NE(iter, multiset.end());
861   EXPECT_STREQ(iter->name(), "d");
862 
863   iter = multiset.lower_bound({46, "?"});
864   ASSERT_NE(iter, multiset.end());
865   EXPECT_STREQ(iter->name(), "b");
866 }
867 
TEST_F(IntrusiveMultiSetTest,LowerBound_OutOfRange)868 TEST_F(IntrusiveMultiSetTest, LowerBound_OutOfRange) {
869   const IntrusiveMultiSet& multiset = multiset_;
870   EXPECT_EQ(multiset.lower_bound({56, "?"}), multiset.end());
871 }
872 
TEST_F(IntrusiveMultiSetTest,LowerBound_WithDuplicates)873 TEST_F(IntrusiveMultiSetTest, LowerBound_WithDuplicates) {
874   TestItem item1(20, "1");
875   TestItem item2(40, "1");
876   TestItem item3(40, "1");
877   multiset_.insert(item1);
878   multiset_.insert(item2);
879   multiset_.insert(item3);
880   EXPECT_EQ(multiset_.size(), items_.size() + 3);
881 
882   auto iter = multiset_.lower_bound({20, "?"});
883   EXPECT_LT((--iter)->key(), 20U);
884   EXPECT_EQ((++iter)->key(), 20U);
885   EXPECT_EQ((++iter)->key(), 20U);
886   EXPECT_GT((++iter)->key(), 20U);
887 
888   iter = multiset_.lower_bound({40, "?"});
889   EXPECT_LT((--iter)->key(), 40U);
890   EXPECT_EQ((++iter)->key(), 40U);
891   EXPECT_EQ((++iter)->key(), 40U);
892   EXPECT_EQ((++iter)->key(), 40U);
893   EXPECT_GT((++iter)->key(), 40U);
894 
895   // Explicitly clear the multiset before items 1-3 go out of scope.
896   multiset_.clear();
897 }
898 
TEST_F(IntrusiveMultiSetTest,UpperBound)899 TEST_F(IntrusiveMultiSetTest, UpperBound) {
900   const IntrusiveMultiSet& multiset = multiset_;
901   auto iter = multiset.upper_bound({15, "?"});
902   ASSERT_NE(iter, multiset.end());
903   EXPECT_STREQ(iter->name(), "c");
904 
905   iter = multiset.upper_bound({25, "?"});
906   ASSERT_NE(iter, multiset.end());
907   EXPECT_STREQ(iter->name(), "a");
908 
909   iter = multiset.upper_bound({35, "?"});
910   ASSERT_NE(iter, multiset.end());
911   EXPECT_STREQ(iter->name(), "d");
912 
913   iter = multiset.upper_bound({45, "?"});
914   ASSERT_NE(iter, multiset.end());
915   EXPECT_STREQ(iter->name(), "b");
916 }
917 
TEST_F(IntrusiveMultiSetTest,UpperBound_NoExactKey)918 TEST_F(IntrusiveMultiSetTest, UpperBound_NoExactKey) {
919   const IntrusiveMultiSet& multiset = multiset_;
920   auto iter = multiset.upper_bound({6, "?"});
921   ASSERT_NE(iter, multiset.end());
922   EXPECT_STREQ(iter->name(), "e");
923 
924   iter = multiset.upper_bound({16, "?"});
925   ASSERT_NE(iter, multiset.end());
926   EXPECT_STREQ(iter->name(), "c");
927 
928   iter = multiset.upper_bound({26, "?"});
929   ASSERT_NE(iter, multiset.end());
930   EXPECT_STREQ(iter->name(), "a");
931 
932   iter = multiset.upper_bound({36, "?"});
933   ASSERT_NE(iter, multiset.end());
934   EXPECT_STREQ(iter->name(), "d");
935 
936   iter = multiset.upper_bound({46, "?"});
937   ASSERT_NE(iter, multiset.end());
938   EXPECT_STREQ(iter->name(), "b");
939 }
940 
TEST_F(IntrusiveMultiSetTest,UpperBound_OutOfRange)941 TEST_F(IntrusiveMultiSetTest, UpperBound_OutOfRange) {
942   const IntrusiveMultiSet& multiset = multiset_;
943   EXPECT_EQ(multiset.upper_bound({56, "?"}), multiset.end());
944 }
945 
TEST_F(IntrusiveMultiSetTest,UpperBound_WithDuplicates)946 TEST_F(IntrusiveMultiSetTest, UpperBound_WithDuplicates) {
947   TestItem item1(20, "1");
948   TestItem item2(40, "1");
949   TestItem item3(40, "1");
950   multiset_.insert(item1);
951   multiset_.insert(item2);
952   multiset_.insert(item3);
953   EXPECT_EQ(multiset_.size(), items_.size() + 3);
954 
955   auto iter = multiset_.upper_bound({20, "?"});
956   EXPECT_GT(iter->key(), 20U);
957 
958   iter = multiset_.upper_bound({40, "?"});
959   EXPECT_GT(iter->key(), 40U);
960 
961   // Explicitly clear the multiset before items 1-3 go out of scope.
962   multiset_.clear();
963 }
964 
TEST_F(IntrusiveMultiSetTest,EqualRange)965 TEST_F(IntrusiveMultiSetTest, EqualRange) {
966   const IntrusiveMultiSet& multiset = multiset_;
967 
968   auto pair = multiset.equal_range({10, "?"});
969   IntrusiveMultiSet::const_iterator lower = pair.first;
970   IntrusiveMultiSet::const_iterator upper = pair.second;
971   ASSERT_NE(lower, multiset.end());
972   EXPECT_STREQ(lower->name(), "e");
973   ASSERT_NE(upper, multiset.end());
974   EXPECT_STREQ(upper->name(), "E");
975 
976   std::tie(lower, upper) = multiset.equal_range({20, "?"});
977   ASSERT_NE(lower, multiset.end());
978   EXPECT_STREQ(lower->name(), "c");
979   ASSERT_NE(upper, multiset.end());
980   EXPECT_STREQ(upper->name(), "C");
981 
982   std::tie(lower, upper) = multiset.equal_range({30, "?"});
983   ASSERT_NE(lower, multiset.end());
984   EXPECT_STREQ(lower->name(), "a");
985   ASSERT_NE(upper, multiset.end());
986   EXPECT_STREQ(upper->name(), "A");
987 
988   std::tie(lower, upper) = multiset.equal_range({40, "?"});
989   ASSERT_NE(lower, multiset.end());
990   EXPECT_STREQ(lower->name(), "d");
991   ASSERT_NE(upper, multiset.end());
992   EXPECT_STREQ(upper->name(), "D");
993 
994   std::tie(lower, upper) = multiset.equal_range({50, "?"});
995   ASSERT_NE(lower, multiset.end());
996   EXPECT_STREQ(lower->name(), "b");
997   ASSERT_NE(upper, multiset.end());
998   EXPECT_STREQ(upper->name(), "B");
999 }
1000 
TEST_F(IntrusiveMultiSetTest,EqualRange_NoExactKey)1001 TEST_F(IntrusiveMultiSetTest, EqualRange_NoExactKey) {
1002   const IntrusiveMultiSet& multiset = multiset_;
1003 
1004   auto pair = multiset.equal_range({6, "?"});
1005   IntrusiveMultiSet::const_iterator lower = pair.first;
1006   IntrusiveMultiSet::const_iterator upper = pair.second;
1007   ASSERT_NE(lower, multiset.end());
1008   EXPECT_STREQ(lower->name(), "e");
1009   ASSERT_NE(upper, multiset.end());
1010   EXPECT_STREQ(upper->name(), "e");
1011 
1012   std::tie(lower, upper) = multiset.equal_range({16, "?"});
1013   ASSERT_NE(lower, multiset.end());
1014   EXPECT_STREQ(lower->name(), "c");
1015   ASSERT_NE(upper, multiset.end());
1016   EXPECT_STREQ(upper->name(), "c");
1017 
1018   std::tie(lower, upper) = multiset.equal_range({26, "?"});
1019   ASSERT_NE(lower, multiset.end());
1020   EXPECT_STREQ(lower->name(), "a");
1021   ASSERT_NE(upper, multiset.end());
1022   EXPECT_STREQ(upper->name(), "a");
1023 
1024   std::tie(lower, upper) = multiset.equal_range({36, "?"});
1025   ASSERT_NE(lower, multiset.end());
1026   EXPECT_STREQ(lower->name(), "d");
1027   ASSERT_NE(upper, multiset.end());
1028   EXPECT_STREQ(upper->name(), "d");
1029 
1030   std::tie(lower, upper) = multiset.equal_range({46, "?"});
1031   ASSERT_NE(lower, multiset.end());
1032   EXPECT_STREQ(lower->name(), "b");
1033   ASSERT_NE(upper, multiset.end());
1034   EXPECT_STREQ(upper->name(), "b");
1035 }
1036 
TEST_F(IntrusiveMultiSetTest,EqualRange_OutOfRange)1037 TEST_F(IntrusiveMultiSetTest, EqualRange_OutOfRange) {
1038   const IntrusiveMultiSet& multiset = multiset_;
1039 
1040   auto pair = multiset.equal_range({56, "?"});
1041   IntrusiveMultiSet::const_iterator lower = pair.first;
1042   IntrusiveMultiSet::const_iterator upper = pair.second;
1043   EXPECT_EQ(lower, multiset.end());
1044   EXPECT_EQ(upper, multiset.end());
1045 }
1046 
TEST_F(IntrusiveMultiSetTest,EqualRange_WithDuplicates)1047 TEST_F(IntrusiveMultiSetTest, EqualRange_WithDuplicates) {
1048   TestItem item1(40, "1");
1049   TestItem item2(40, "2");
1050   TestItem item3(40, "3");
1051   multiset_.insert(item1);
1052   multiset_.insert(item2);
1053   multiset_.insert(item3);
1054 
1055   auto result = multiset_.equal_range({40, "?"});
1056   EXPECT_EQ(std::distance(result.first, result.second), 4);
1057 
1058   // Explicitly clear the multiset before items 1-3 go out of scope.
1059   multiset_.clear();
1060 }
1061 
1062 }  // namespace
1063