folly/test/sorted_vector_test.cpp

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <folly/sorted_vector_types.h>
  18
  19 #include <iterator>
  20 #include <list>
  21 #include <memory>
  22
  23 #include <folly/portability/GMock.h>
  24 #include <folly/portability/GTest.h>
  25
  26 using folly::sorted_vector_set;
  27 using folly::sorted_vector_map;
  28
  29 namespace {
  30
  31 template <class T>
  32 struct less_invert {
  33   bool operator()(const T& a, const T& b) const {
  34     return b < a;
  35   }
  36 };
  37
  38 template <class Container>
  39 void check_invariant(Container& c) {
  40   auto it = c.begin();
  41   auto end = c.end();
  42   if (it == end) {
  43     return;
  44   }
  45   auto prev = it;
  46   ++it;
  47   for (; it != end; ++it, ++prev) {
  48     EXPECT_TRUE(c.value_comp()(*prev, *it));
  49   }
  50 }
  51
  52 struct OneAtATimePolicy {
  53   template <class Container>
  54   void increase_capacity(Container& c) {
  55     if (c.size() == c.capacity()) {
  56       c.reserve(c.size() + 1);
  57     }
  58   }
  59 };
  60
  61 struct CountCopyCtor {
  62   explicit CountCopyCtor() : val_(0) {}
  63
  64   explicit CountCopyCtor(int val) : val_(val), count_(0) {}
  65
  66   CountCopyCtor(const CountCopyCtor& c)
  67     : val_(c.val_)
  68     , count_(c.count_ + 1)
  69   {}
  70
  71   bool operator<(const CountCopyCtor& o) const {
  72     return val_ < o.val_;
  73   }
  74
  75   int val_;
  76   int count_;
  77 };
  78
  79 } // namespace
  80
  81 TEST(SortedVectorTypes, SimpleSetTest) {
  82   sorted_vector_set<int> s;
  83   EXPECT_TRUE(s.empty());
  84   for (int i = 0; i < 1000; ++i) {
  85     s.insert(rand() % 100000);
  86   }
  87   EXPECT_FALSE(s.empty());
  88   check_invariant(s);
  89
  90   sorted_vector_set<int> s2;
  91   s2.insert(s.begin(), s.end());
  92   check_invariant(s2);
  93   EXPECT_TRUE(s == s2);
  94
  95   auto it = s2.lower_bound(32);
  96   if (*it == 32) {
  97     s2.erase(it);
  98     it = s2.lower_bound(32);
  99   }
 100   check_invariant(s2);
 101   auto oldSz = s2.size();
 102   s2.insert(it, 32);
 103   EXPECT_TRUE(s2.size() == oldSz + 1);
 104   check_invariant(s2);
 105
 106   const sorted_vector_set<int>& cs2 = s2;
 107   auto range = cs2.equal_range(32);
 108   auto lbound = cs2.lower_bound(32);
 109   auto ubound = cs2.upper_bound(32);
 110   EXPECT_TRUE(range.first == lbound);
 111   EXPECT_TRUE(range.second == ubound);
 112   EXPECT_TRUE(range.first != cs2.end());
 113   EXPECT_TRUE(range.second != cs2.end());
 114   EXPECT_TRUE(cs2.count(32) == 1);
 115   EXPECT_FALSE(cs2.find(32) == cs2.end());
 116
 117   // Bad insert hint.
 118   s2.insert(s2.begin() + 3, 33);
 119   EXPECT_TRUE(s2.find(33) != s2.begin());
 120   EXPECT_TRUE(s2.find(33) != s2.end());
 121   check_invariant(s2);
 122   s2.erase(33);
 123   check_invariant(s2);
 124
 125   it = s2.find(32);
 126   EXPECT_FALSE(it == s2.end());
 127   s2.erase(it);
 128   EXPECT_TRUE(s2.size() == oldSz);
 129   check_invariant(s2);
 130
 131   sorted_vector_set<int> cpy(s);
 132   check_invariant(cpy);
 133   EXPECT_TRUE(cpy == s);
 134   sorted_vector_set<int> cpy2(s);
 135   cpy2.insert(100001);
 136   EXPECT_TRUE(cpy2 != cpy);
 137   EXPECT_TRUE(cpy2 != s);
 138   check_invariant(cpy2);
 139   EXPECT_TRUE(cpy2.count(100001) == 1);
 140   s.swap(cpy2);
 141   check_invariant(cpy2);
 142   check_invariant(s);
 143   EXPECT_TRUE(s != cpy);
 144   EXPECT_TRUE(s != cpy2);
 145   EXPECT_TRUE(cpy2 == cpy);
 146 }
 147
 148 TEST(SortedVectorTypes, BadHints) {
 149   for (int toInsert = -1; toInsert <= 7; ++toInsert) {
 150     for (int hintPos = 0; hintPos <= 4; ++hintPos) {
 151       sorted_vector_set<int> s;
 152       for (int i = 0; i <= 3; ++i) {
 153         s.insert(i * 2);
 154       }
 155       s.insert(s.begin() + hintPos, toInsert);
 156       size_t expectedSize = (toInsert % 2) == 0 ? 4 : 5;
 157       EXPECT_EQ(s.size(), expectedSize);
 158       check_invariant(s);
 159     }
 160   }
 161 }
 162
 163 TEST(SortedVectorTypes, SimpleMapTest) {
 164   sorted_vector_map<int,float> m;
 165   for (int i = 0; i < 1000; ++i) {
 166     m[i] = i / 1000.0;
 167   }
 168   check_invariant(m);
 169
 170   m[32] = 100.0;
 171   check_invariant(m);
 172   EXPECT_TRUE(m.count(32) == 1);
 173   EXPECT_DOUBLE_EQ(100.0, m.at(32));
 174   EXPECT_FALSE(m.find(32) == m.end());
 175   m.erase(32);
 176   EXPECT_TRUE(m.find(32) == m.end());
 177   check_invariant(m);
 178   EXPECT_THROW(m.at(32), std::out_of_range);
 179
 180   sorted_vector_map<int,float> m2 = m;
 181   EXPECT_TRUE(m2 == m);
 182   EXPECT_FALSE(m2 != m);
 183   auto it = m2.lower_bound(1 << 20);
 184   EXPECT_TRUE(it == m2.end());
 185   m2.insert(it, std::make_pair(1 << 20, 10.0f));
 186   check_invariant(m2);
 187   EXPECT_TRUE(m2.count(1 << 20) == 1);
 188   EXPECT_TRUE(m < m2);
 189   EXPECT_TRUE(m <= m2);
 190
 191   const sorted_vector_map<int,float>& cm = m;
 192   auto range = cm.equal_range(42);
 193   auto lbound = cm.lower_bound(42);
 194   auto ubound = cm.upper_bound(42);
 195   EXPECT_TRUE(range.first == lbound);
 196   EXPECT_TRUE(range.second == ubound);
 197   EXPECT_FALSE(range.first == cm.end());
 198   EXPECT_FALSE(range.second == cm.end());
 199   m.erase(m.lower_bound(42));
 200   check_invariant(m);
 201
 202   sorted_vector_map<int,float> m3;
 203   m3.insert(m2.begin(), m2.end());
 204   check_invariant(m3);
 205   EXPECT_TRUE(m3 == m2);
 206   EXPECT_FALSE(m3 == m);
 207
 208   EXPECT_TRUE(m != m2);
 209   EXPECT_TRUE(m2 == m3);
 210   EXPECT_TRUE(m3 != m);
 211   m.swap(m3);
 212   check_invariant(m);
 213   check_invariant(m2);
 214   check_invariant(m3);
 215   EXPECT_TRUE(m3 != m2);
 216   EXPECT_TRUE(m3 != m);
 217   EXPECT_TRUE(m == m2);
 218
 219   // Bad insert hint.
 220   m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f));
 221   check_invariant(m);
 222 }
 223
 224 TEST(SortedVectorTypes, Sizes) {
 225   EXPECT_EQ(sizeof(sorted_vector_set<int>),
 226             sizeof(std::vector<int>));
 227   EXPECT_EQ(sizeof(sorted_vector_map<int,int>),
 228             sizeof(std::vector<std::pair<int,int> >));
 229
 230   typedef sorted_vector_set<int,std::less<int>,
 231     std::allocator<int>,OneAtATimePolicy> SetT;
 232   typedef sorted_vector_map<int,int,std::less<int>,
 233     std::allocator<std::pair<int,int>>,OneAtATimePolicy> MapT;
 234
 235   EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
 236   EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
 237 }
 238
 239 TEST(SortedVectorTypes, InitializerLists) {
 240   sorted_vector_set<int> empty_initialized_set{};
 241   EXPECT_TRUE(empty_initialized_set.empty());
 242
 243   sorted_vector_set<int> singleton_initialized_set{1};
 244   EXPECT_EQ(1, singleton_initialized_set.size());
 245   EXPECT_EQ(1, *singleton_initialized_set.begin());
 246
 247   sorted_vector_set<int> forward_initialized_set{1, 2};
 248   sorted_vector_set<int> backward_initialized_set{2, 1};
 249   EXPECT_EQ(2, forward_initialized_set.size());
 250   EXPECT_EQ(1, *forward_initialized_set.begin());
 251   EXPECT_EQ(2, *forward_initialized_set.rbegin());
 252   EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
 253
 254   sorted_vector_map<int,int> empty_initialized_map{};
 255   EXPECT_TRUE(empty_initialized_map.empty());
 256
 257   sorted_vector_map<int,int> singleton_initialized_map{{1,10}};
 258   EXPECT_EQ(1, singleton_initialized_map.size());
 259   EXPECT_EQ(10, singleton_initialized_map[1]);
 260
 261   sorted_vector_map<int,int> forward_initialized_map{{1,10}, {2,20}};
 262   sorted_vector_map<int,int> backward_initialized_map{{2,20}, {1,10}};
 263   EXPECT_EQ(2, forward_initialized_map.size());
 264   EXPECT_EQ(10, forward_initialized_map[1]);
 265   EXPECT_EQ(20, forward_initialized_map[2]);
 266   EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
 267 }
 268
 269 TEST(SortedVectorTypes, CustomCompare) {
 270   sorted_vector_set<int,less_invert<int> > s;
 271   for (int i = 0; i < 200; ++i) {
 272     s.insert(i);
 273   }
 274   check_invariant(s);
 275
 276   sorted_vector_map<int,float,less_invert<int> > m;
 277   for (int i = 0; i < 200; ++i) {
 278     m[i] = 12.0;
 279   }
 280   check_invariant(m);
 281 }
 282
 283 TEST(SortedVectorTypes, GrowthPolicy) {
 284   typedef sorted_vector_set<CountCopyCtor,
 285                             std::less<CountCopyCtor>,
 286                             std::allocator<CountCopyCtor>,
 287                             OneAtATimePolicy>
 288     SetT;
 289
 290   SetT a;
 291   for (int i = 0; i < 20; ++i) {
 292     a.insert(CountCopyCtor(i));
 293   }
 294   check_invariant(a);
 295   SetT::iterator it = a.begin();
 296   EXPECT_FALSE(it == a.end());
 297   if (it != a.end()) {
 298     EXPECT_EQ(it->val_, 0);
 299     // 1 copy for the initial insertion, 19 more for reallocs on the
 300     // additional insertions.
 301     EXPECT_EQ(it->count_, 20);
 302   }
 303
 304   std::list<CountCopyCtor> v;
 305   for (int i = 0; i < 20; ++i) {
 306     v.emplace_back(20 + i);
 307   }
 308   a.insert(v.begin(), v.end());
 309   check_invariant(a);
 310
 311   it = a.begin();
 312   EXPECT_FALSE(it == a.end());
 313   if (it != a.end()) {
 314     EXPECT_EQ(it->val_, 0);
 315     // Should be only 1 more copy for inserting this above range.
 316     EXPECT_EQ(it->count_, 21);
 317   }
 318 }
 319
 320 TEST(SortedVectorTest, EmptyTest) {
 321   sorted_vector_set<int> emptySet;
 322   EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
 323   EXPECT_TRUE(emptySet.find(10) == emptySet.end());
 324
 325   sorted_vector_map<int,int> emptyMap;
 326   EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
 327   EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
 328   EXPECT_THROW(emptyMap.at(10), std::out_of_range);
 329 }
 330
 331 TEST(SortedVectorTest, MoveTest) {
 332   sorted_vector_set<std::unique_ptr<int>> s;
 333   s.insert(std::make_unique<int>(5));
 334   s.insert(s.end(), std::make_unique<int>(10));
 335   EXPECT_EQ(s.size(), 2);
 336
 337   for (const auto& p : s) {
 338     EXPECT_TRUE(*p == 5 || *p == 10);
 339   }
 340
 341   sorted_vector_map<int, std::unique_ptr<int>> m;
 342   m.insert(std::make_pair(5, std::make_unique<int>(5)));
 343   m.insert(m.end(), std::make_pair(10, std::make_unique<int>(10)));
 344
 345   EXPECT_EQ(*m[5], 5);
 346   EXPECT_EQ(*m[10], 10);
 347 }
 348
 349 TEST(SortedVectorTest, ShrinkTest) {
 350   sorted_vector_set<int> s;
 351   int i = 0;
 352   // Hopefully your resize policy doubles when capacity is full, or this will
 353   // hang forever :(
 354   while (s.capacity() == s.size()) {
 355     s.insert(i++);
 356   }
 357   s.shrink_to_fit();
 358   // The standard does not actually enforce that this be true, but assume that
 359   // vector::shrink_to_fit respects the caller.
 360   EXPECT_EQ(s.capacity(), s.size());
 361 }
 362
 363 TEST(SortedVectorTypes, EraseTest) {
 364   sorted_vector_set<int> s1;
 365   s1.insert(1);
 366   sorted_vector_set<int> s2(s1);
 367   EXPECT_EQ(0, s1.erase(0));
 368   EXPECT_EQ(s2, s1);
 369 }
 370
 371 std::vector<int> extractValues(sorted_vector_set<CountCopyCtor> const& in) {
 372   std::vector<int> ret;
 373   std::transform(
 374       in.begin(),
 375       in.end(),
 376       std::back_inserter(ret),
 377       [](const CountCopyCtor& c) { return c.val_; });
 378   return ret;
 379 }
 380
 381 template <typename T, typename S>
 382 std::vector<T> makeVectorOfWrappers(std::vector<S> ss) {
 383   std::vector<T> ts;
 384   ts.reserve(ss.size());
 385   for (auto const& s : ss) {
 386     ts.emplace_back(s);
 387   }
 388   return ts;
 389 }
 390
 391 TEST(SortedVectorTypes, TestSetBulkInsertionSortMerge) {
 392   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 393
 394   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 395   check_invariant(vset);
 396
 397   // Add an unsorted range that will have to be merged in.
 398   s = makeVectorOfWrappers<CountCopyCtor, int>({10, 7, 5, 1});
 399
 400   vset.insert(s.begin(), s.end());
 401   check_invariant(vset);
 402   EXPECT_EQ(vset.rbegin()->count_, 1);
 403
 404   EXPECT_THAT(
 405       extractValues(vset),
 406       testing::ElementsAreArray({1, 2, 4, 5, 6, 7, 8, 10}));
 407 }
 408
 409 TEST(SortedVectorTypes, TestSetBulkInsertionMiddleValuesEqualDuplication) {
 410   auto s = makeVectorOfWrappers<CountCopyCtor, int>({4, 6, 8});
 411
 412   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 413   check_invariant(vset);
 414
 415   s = makeVectorOfWrappers<CountCopyCtor, int>({8, 10, 12});
 416
 417   vset.insert(s.begin(), s.end());
 418   check_invariant(vset);
 419   EXPECT_EQ(vset.rbegin()->count_, 1);
 420
 421   EXPECT_THAT(
 422       extractValues(vset),
 423       testing::ElementsAreArray({4, 6, 8, 10, 12}));
 424 }
 425
 426 TEST(SortedVectorTypes, TestSetBulkInsertionSortMergeDups) {
 427   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 428
 429   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 430   check_invariant(vset);
 431
 432   // Add an unsorted range that will have to be merged in.
 433   s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
 434
 435   vset.insert(s.begin(), s.end());
 436   check_invariant(vset);
 437   EXPECT_EQ(vset.rbegin()->count_, 1);
 438   EXPECT_THAT(
 439       extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
 440 }
 441
 442 TEST(SortedVectorTypes, TestSetInsertionDupsOneByOne) {
 443   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 444
 445   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 446   check_invariant(vset);
 447
 448   // Add an unsorted range that will have to be merged in.
 449   s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
 450
 451   for (const auto& elem : s) {
 452     vset.insert(elem);
 453   }
 454   check_invariant(vset);
 455   EXPECT_EQ(vset.rbegin()->count_, 3);
 456   EXPECT_THAT(
 457       extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
 458 }
 459
 460 TEST(SortedVectorTypes, TestSetBulkInsertionSortNoMerge) {
 461   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 462
 463   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 464   check_invariant(vset);
 465
 466   // Add an unsorted range that will not have to be merged in.
 467   s = makeVectorOfWrappers<CountCopyCtor, int>({20, 15, 16, 13});
 468
 469   vset.insert(s.begin(), s.end());
 470   check_invariant(vset);
 471   EXPECT_EQ(vset.rbegin()->count_, 1);
 472   EXPECT_THAT(
 473       extractValues(vset),
 474       testing::ElementsAreArray({2, 4, 6, 8, 13, 15, 16, 20}));
 475 }
 476
 477 TEST(SortedVectorTypes, TestSetBulkInsertionNoSortMerge) {
 478   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 479
 480   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 481   check_invariant(vset);
 482
 483   // Add a sorted range that will have to be merged in.
 484   s = makeVectorOfWrappers<CountCopyCtor, int>({1, 3, 5, 9});
 485
 486   vset.insert(s.begin(), s.end());
 487   check_invariant(vset);
 488   EXPECT_EQ(vset.rbegin()->count_, 1);
 489   EXPECT_THAT(
 490       extractValues(vset), testing::ElementsAreArray({1, 2, 3, 4, 5, 6, 8, 9}));
 491 }
 492
 493 TEST(SortedVectorTypes, TestSetBulkInsertionNoSortNoMerge) {
 494   auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 495
 496   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 497   check_invariant(vset);
 498
 499   // Add a sorted range that will not have to be merged in.
 500   s = makeVectorOfWrappers<CountCopyCtor, int>({21, 22, 23, 24});
 501
 502   vset.insert(s.begin(), s.end());
 503   check_invariant(vset);
 504   EXPECT_EQ(vset.rbegin()->count_, 1);
 505   EXPECT_THAT(
 506       extractValues(vset),
 507       testing::ElementsAreArray({2, 4, 6, 8, 21, 22, 23, 24}));
 508 }
 509
 510 TEST(SortedVectorTypes, TestSetBulkInsertionEmptyRange) {
 511   std::vector<CountCopyCtor> s;
 512   EXPECT_TRUE(s.empty());
 513
 514   // insertion of empty range into empty container.
 515   sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
 516   check_invariant(vset);
 517
 518   s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
 519
 520   vset.insert(s.begin(), s.end());
 521
 522   // insertion of empty range into non-empty container.
 523   s.clear();
 524   vset.insert(s.begin(), s.end());
 525   check_invariant(vset);
 526
 527   EXPECT_THAT(extractValues(vset), testing::ElementsAreArray({2, 4, 6, 8}));
 528 }
 529
 530 // This is a test of compilation - the behavior has already been tested
 531 // extensively above.
 532 TEST(SortedVectorTypes, TestBulkInsertionUncopyableTypes) {
 533   std::vector<std::pair<int, std::unique_ptr<int>>> s;
 534   s.emplace_back(1, std::make_unique<int>(0));
 535
 536   sorted_vector_map<int, std::unique_ptr<int>> vmap(
 537       std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
 538
 539   s.clear();
 540   s.emplace_back(3, std::make_unique<int>(0));
 541   vmap.insert(
 542       std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
 543 }
 544
 545 // A moveable and copyable struct, which we use to make sure that no copy
 546 // operations are performed during bulk insertion if moving is an option.
 547 struct Movable {
 548   int x_;
 549   explicit Movable(int x) : x_(x) {}
 550   Movable(const Movable&) {
 551     ADD_FAILURE() << "Copy ctor should not be called";
 552   }
 553   Movable& operator=(const Movable&) {
 554     ADD_FAILURE() << "Copy assignment should not be called";
 555     return *this;
 556   }
 557
 558   Movable(Movable&&) = default;
 559   Movable& operator=(Movable&&) = default;
 560 };
 561
 562 TEST(SortedVectorTypes, TestBulkInsertionMovableTypes) {
 563   std::vector<std::pair<int, Movable>> s;
 564   s.emplace_back(3, Movable(2));
 565   s.emplace_back(1, Movable(0));
 566
 567   sorted_vector_map<int, Movable> vmap(
 568       std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
 569
 570   s.clear();
 571   s.emplace_back(4, Movable(3));
 572   s.emplace_back(2, Movable(1));
 573   vmap.insert(
 574       std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
 575 }
 576
 577 TEST(SortedVectorTypes, TestSetCreationFromVector) {
 578   std::vector<int> vec = {3, 1, -1, 5, 0};
 579   sorted_vector_set<int> vset(std::move(vec));
 580   check_invariant(vset);
 581   EXPECT_THAT(vset, testing::ElementsAreArray({-1, 0, 1, 3, 5}));
 582 }
 583
 584 TEST(SortedVectorTypes, TestMapCreationFromVector) {
 585   std::vector<std::pair<int, int>> vec = {
 586       {3, 1}, {1, 5}, {-1, 2}, {5, 3}, {0, 3}};
 587   sorted_vector_map<int, int> vmap(std::move(vec));
 588   check_invariant(vmap);
 589   auto contents = std::vector<std::pair<int, int>>(vmap.begin(), vmap.end());
 590   auto expected_contents = std::vector<std::pair<int, int>>({
 591       {-1, 2}, {0, 3}, {1, 5}, {3, 1}, {5, 3},
 592   });
 593   EXPECT_EQ(contents, expected_contents);
 594 }