base/stl_util_unittest.cc

   1 // Copyright 2012 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
   5 #include "base/stl_util.h"
   6
   7 #include <array>
   8 #include <deque>
   9 #include <forward_list>
  10 #include <functional>
  11 #include <initializer_list>
  12 #include <iterator>
  13 #include <list>
  14 #include <map>
  15 #include <queue>
  16 #include <set>
  17 #include <stack>
  18 #include <string>
  19 #include <type_traits>
  20 #include <unordered_map>
  21 #include <unordered_set>
  22 #include <vector>
  23
  24 #include "base/containers/flat_set.h"
  25 #include "base/containers/queue.h"
  26 #include "base/strings/string16.h"
  27 #include "base/strings/utf_string_conversions.h"
  28 #include "testing/gmock/include/gmock/gmock.h"
  29 #include "testing/gtest/include/gtest/gtest.h"
  30
  31 namespace {
  32
  33 using ::testing::IsNull;
  34 using ::testing::Pair;
  35
  36 // Used as test case to ensure the various base::STLXxx functions don't require
  37 // more than operators "<" and "==" on values stored in containers.
  38 class ComparableValue {
  39  public:
  40   explicit ComparableValue(int value) : value_(value) {}
  41
  42   bool operator==(const ComparableValue& rhs) const {
  43     return value_ == rhs.value_;
  44   }
  45
  46   bool operator<(const ComparableValue& rhs) const {
  47     return value_ < rhs.value_;
  48   }
  49
  50  private:
  51   int value_;
  52 };
  53
  54 template <typename Container>
  55 size_t GetSize(const Container& c) {
  56   return c.size();
  57 }
  58
  59 template <typename T>
  60 size_t GetSize(const std::forward_list<T>& l) {
  61   return std::distance(l.begin(), l.end());
  62 }
  63
  64 template <typename Container>
  65 void RunEraseTest() {
  66   const std::pair<Container, Container> test_data[] = {
  67       {Container(), Container()}, {{1, 2, 3}, {1, 3}}, {{1, 2, 3, 2}, {1, 3}}};
  68
  69   for (auto test_case : test_data) {
  70     size_t expected_erased =
  71         GetSize(test_case.first) - GetSize(test_case.second);
  72     EXPECT_EQ(expected_erased, base::Erase(test_case.first, 2));
  73     EXPECT_EQ(test_case.second, test_case.first);
  74   }
  75 }
  76
  77 // This test is written for containers of std::pair<int, int> to support maps.
  78 template <typename Container>
  79 void RunEraseIfTest() {
  80   struct {
  81     Container input;
  82     Container erase_even;
  83     Container erase_odd;
  84   } test_data[] = {
  85       {Container(), Container(), Container()},
  86       {{{1, 1}, {2, 2}, {3, 3}}, {{1, 1}, {3, 3}}, {{2, 2}}},
  87       {{{1, 1}, {2, 2}, {3, 3}, {4, 4}}, {{1, 1}, {3, 3}}, {{2, 2}, {4, 4}}},
  88   };
  89
  90   for (auto test_case : test_data) {
  91     size_t expected_erased =
  92         GetSize(test_case.input) - GetSize(test_case.erase_even);
  93     EXPECT_EQ(expected_erased,
  94               base::EraseIf(test_case.input, [](const auto& elem) {
  95                 return !(elem.first & 1);
  96               }));
  97     EXPECT_EQ(test_case.erase_even, test_case.input);
  98   }
  99
 100   for (auto test_case : test_data) {
 101     size_t expected_erased =
 102         GetSize(test_case.input) - GetSize(test_case.erase_odd);
 103     EXPECT_EQ(expected_erased,
 104               base::EraseIf(test_case.input,
 105                             [](const auto& elem) { return elem.first & 1; }));
 106     EXPECT_EQ(test_case.erase_odd, test_case.input);
 107   }
 108 }
 109
 110 template <typename Container>
 111 void RunConstCastIteratorTest() {
 112   using std::begin;
 113   using std::cbegin;
 114
 115   Container c = {1, 2, 3, 4, 5};
 116   auto c_it = std::next(cbegin(c), 3);
 117   auto it = base::ConstCastIterator(c, c_it);
 118   static_assert(std::is_same<decltype(cbegin(std::declval<Container&>())),
 119                              decltype(c_it)>::value,
 120                 "c_it is not a constant iterator.");
 121   static_assert(std::is_same<decltype(begin(std::declval<Container&>())),
 122                              decltype(it)>::value,
 123                 "it is not a iterator.");
 124   EXPECT_EQ(c_it, it);
 125   // Const casting the iterator should not modify the underlying container.
 126   Container other = {1, 2, 3, 4, 5};
 127   EXPECT_THAT(c, testing::ContainerEq(other));
 128 }
 129
 130 struct CustomIntHash {
 131   size_t operator()(int elem) const { return std::hash<int>()(elem) + 1; }
 132 };
 133
 134 struct HashByFirst {
 135   size_t operator()(const std::pair<int, int>& elem) const {
 136     return std::hash<int>()(elem.first);
 137   }
 138 };
 139
 140 }  // namespace
 141
 142 namespace base {
 143 namespace {
 144
 145 TEST(STLUtilTest, Size) {
 146   {
 147     std::vector<int> vector = {1, 2, 3, 4, 5};
 148     static_assert(
 149         std::is_same<decltype(base::size(vector)),
 150                      decltype(vector.size())>::value,
 151         "base::size(vector) should have the same type as vector.size()");
 152     EXPECT_EQ(vector.size(), base::size(vector));
 153   }
 154
 155   {
 156     std::string empty_str;
 157     static_assert(
 158         std::is_same<decltype(base::size(empty_str)),
 159                      decltype(empty_str.size())>::value,
 160         "base::size(empty_str) should have the same type as empty_str.size()");
 161     EXPECT_EQ(0u, base::size(empty_str));
 162   }
 163
 164   {
 165     std::array<int, 4> array = {{1, 2, 3, 4}};
 166     static_assert(
 167         std::is_same<decltype(base::size(array)),
 168                      decltype(array.size())>::value,
 169         "base::size(array) should have the same type as array.size()");
 170     static_assert(base::size(array) == array.size(),
 171                   "base::size(array) should be equal to array.size()");
 172   }
 173
 174   {
 175     int array[] = {1, 2, 3};
 176     static_assert(std::is_same<size_t, decltype(base::size(array))>::value,
 177                   "base::size(array) should be of type size_t");
 178     static_assert(3u == base::size(array), "base::size(array) should be 3");
 179   }
 180 }
 181
 182 TEST(STLUtilTest, Empty) {
 183   {
 184     std::vector<int> vector;
 185     static_assert(
 186         std::is_same<decltype(base::empty(vector)),
 187                      decltype(vector.empty())>::value,
 188         "base::empty(vector) should have the same type as vector.empty()");
 189     EXPECT_EQ(vector.empty(), base::empty(vector));
 190   }
 191
 192   {
 193     std::array<int, 4> array = {{1, 2, 3, 4}};
 194     static_assert(
 195         std::is_same<decltype(base::empty(array)),
 196                      decltype(array.empty())>::value,
 197         "base::empty(array) should have the same type as array.empty()");
 198     static_assert(base::empty(array) == array.empty(),
 199                   "base::empty(array) should be equal to array.empty()");
 200   }
 201
 202   {
 203     int array[] = {1, 2, 3};
 204     static_assert(std::is_same<bool, decltype(base::empty(array))>::value,
 205                   "base::empty(array) should be of type bool");
 206     static_assert(!base::empty(array), "base::empty(array) should be false");
 207   }
 208
 209   {
 210     constexpr std::initializer_list<int> il;
 211     static_assert(std::is_same<bool, decltype(base::empty(il))>::value,
 212                   "base::empty(il) should be of type bool");
 213     static_assert(base::empty(il), "base::empty(il) should be true");
 214   }
 215 }
 216
 217 TEST(STLUtilTest, Data) {
 218   {
 219     std::vector<int> vector = {1, 2, 3, 4, 5};
 220     static_assert(
 221         std::is_same<decltype(base::data(vector)),
 222                      decltype(vector.data())>::value,
 223         "base::data(vector) should have the same type as vector.data()");
 224     EXPECT_EQ(vector.data(), base::data(vector));
 225   }
 226
 227   {
 228     const std::string cstr = "const string";
 229     static_assert(
 230         std::is_same<decltype(base::data(cstr)), decltype(cstr.data())>::value,
 231         "base::data(cstr) should have the same type as cstr.data()");
 232
 233     EXPECT_EQ(cstr.data(), base::data(cstr));
 234   }
 235
 236   {
 237     std::string str = "mutable string";
 238     static_assert(std::is_same<decltype(base::data(str)), char*>::value,
 239                   "base::data(str) should be of type char*");
 240     EXPECT_EQ(str.data(), base::data(str));
 241   }
 242
 243   {
 244     std::string empty_str;
 245     static_assert(std::is_same<decltype(base::data(empty_str)), char*>::value,
 246                   "base::data(empty_str) should be of type char*");
 247     EXPECT_EQ(empty_str.data(), base::data(empty_str));
 248   }
 249
 250   {
 251     std::array<int, 4> array = {{1, 2, 3, 4}};
 252     static_assert(
 253         std::is_same<decltype(base::data(array)),
 254                      decltype(array.data())>::value,
 255         "base::data(array) should have the same type as array.data()");
 256     // std::array::data() is not constexpr prior to C++17, hence the runtime
 257     // check.
 258     EXPECT_EQ(array.data(), base::data(array));
 259   }
 260
 261   {
 262     constexpr int array[] = {1, 2, 3};
 263     static_assert(std::is_same<const int*, decltype(base::data(array))>::value,
 264                   "base::data(array) should be of type const int*");
 265     static_assert(array == base::data(array),
 266                   "base::data(array) should be array");
 267   }
 268
 269   {
 270     constexpr std::initializer_list<int> il;
 271     static_assert(
 272         std::is_same<decltype(il.begin()), decltype(base::data(il))>::value,
 273         "base::data(il) should have the same type as il.begin()");
 274     static_assert(il.begin() == base::data(il),
 275                   "base::data(il) should be equal to il.begin()");
 276   }
 277 }
 278
 279 TEST(STLUtilTest, AsConst) {
 280   int i = 123;
 281   EXPECT_EQ(&i, &base::as_const(i));
 282   static_assert(std::is_same<const int&, decltype(base::as_const(i))>::value,
 283                 "Error: base::as_const() returns an unexpected type");
 284
 285   const int ci = 456;
 286   static_assert(&ci == &base::as_const(ci),
 287                 "Error: base::as_const() returns an unexpected reference");
 288   static_assert(std::is_same<const int&, decltype(base::as_const(ci))>::value,
 289                 "Error: base::as_const() returns an unexpected type");
 290 }
 291
 292 TEST(STLUtilTest, GetUnderlyingContainer) {
 293   {
 294     std::queue<int> queue({1, 2, 3, 4, 5});
 295     static_assert(std::is_same<decltype(GetUnderlyingContainer(queue)),
 296                                const std::deque<int>&>::value,
 297                   "GetUnderlyingContainer(queue) should be of type deque");
 298     EXPECT_THAT(GetUnderlyingContainer(queue),
 299                 testing::ElementsAre(1, 2, 3, 4, 5));
 300   }
 301
 302   {
 303     std::queue<int> queue;
 304     EXPECT_THAT(GetUnderlyingContainer(queue), testing::ElementsAre());
 305   }
 306
 307   {
 308     base::queue<int> queue({1, 2, 3, 4, 5});
 309     static_assert(
 310         std::is_same<decltype(GetUnderlyingContainer(queue)),
 311                      const base::circular_deque<int>&>::value,
 312         "GetUnderlyingContainer(queue) should be of type circular_deque");
 313     EXPECT_THAT(GetUnderlyingContainer(queue),
 314                 testing::ElementsAre(1, 2, 3, 4, 5));
 315   }
 316
 317   {
 318     std::vector<int> values = {1, 2, 3, 4, 5};
 319     std::priority_queue<int> queue(values.begin(), values.end());
 320     static_assert(std::is_same<decltype(GetUnderlyingContainer(queue)),
 321                                const std::vector<int>&>::value,
 322                   "GetUnderlyingContainer(queue) should be of type vector");
 323     EXPECT_THAT(GetUnderlyingContainer(queue),
 324                 testing::UnorderedElementsAre(1, 2, 3, 4, 5));
 325   }
 326
 327   {
 328     std::stack<int> stack({1, 2, 3, 4, 5});
 329     static_assert(std::is_same<decltype(GetUnderlyingContainer(stack)),
 330                                const std::deque<int>&>::value,
 331                   "GetUnderlyingContainer(stack) should be of type deque");
 332     EXPECT_THAT(GetUnderlyingContainer(stack),
 333                 testing::ElementsAre(1, 2, 3, 4, 5));
 334   }
 335 }
 336
 337 TEST(STLUtilTest, ConstCastIterator) {
 338   // Sequence Containers
 339   RunConstCastIteratorTest<std::forward_list<int>>();
 340   RunConstCastIteratorTest<std::list<int>>();
 341   RunConstCastIteratorTest<std::deque<int>>();
 342   RunConstCastIteratorTest<std::vector<int>>();
 343   RunConstCastIteratorTest<std::array<int, 5>>();
 344   RunConstCastIteratorTest<int[5]>();
 345
 346   // Associative Containers
 347   RunConstCastIteratorTest<std::set<int>>();
 348   RunConstCastIteratorTest<std::multiset<int>>();
 349
 350   // Unordered Associative Containers
 351   RunConstCastIteratorTest<std::unordered_set<int>>();
 352   RunConstCastIteratorTest<std::unordered_multiset<int>>();
 353 }
 354
 355 TEST(STLUtilTest, STLIsSorted) {
 356   {
 357     std::set<int> set;
 358     set.insert(24);
 359     set.insert(1);
 360     set.insert(12);
 361     EXPECT_TRUE(STLIsSorted(set));
 362   }
 363
 364   {
 365     std::set<ComparableValue> set;
 366     set.insert(ComparableValue(24));
 367     set.insert(ComparableValue(1));
 368     set.insert(ComparableValue(12));
 369     EXPECT_TRUE(STLIsSorted(set));
 370   }
 371
 372   {
 373     std::vector<int> vector;
 374     vector.push_back(1);
 375     vector.push_back(1);
 376     vector.push_back(4);
 377     vector.push_back(64);
 378     vector.push_back(12432);
 379     EXPECT_TRUE(STLIsSorted(vector));
 380     vector.back() = 1;
 381     EXPECT_FALSE(STLIsSorted(vector));
 382   }
 383
 384   {
 385     int array[] = {1, 1, 4, 64, 12432};
 386     EXPECT_TRUE(STLIsSorted(array));
 387     array[4] = 1;
 388     EXPECT_FALSE(STLIsSorted(array));
 389   }
 390 }
 391
 392 TEST(STLUtilTest, STLSetDifference) {
 393   std::set<int> a1;
 394   a1.insert(1);
 395   a1.insert(2);
 396   a1.insert(3);
 397   a1.insert(4);
 398
 399   std::set<int> a2;
 400   a2.insert(3);
 401   a2.insert(4);
 402   a2.insert(5);
 403   a2.insert(6);
 404   a2.insert(7);
 405
 406   {
 407     std::set<int> difference;
 408     difference.insert(1);
 409     difference.insert(2);
 410     EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a1, a2));
 411   }
 412
 413   {
 414     std::set<int> difference;
 415     difference.insert(5);
 416     difference.insert(6);
 417     difference.insert(7);
 418     EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a2, a1));
 419   }
 420
 421   {
 422     std::vector<int> difference;
 423     difference.push_back(1);
 424     difference.push_back(2);
 425     EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a1, a2));
 426   }
 427
 428   {
 429     std::vector<int> difference;
 430     difference.push_back(5);
 431     difference.push_back(6);
 432     difference.push_back(7);
 433     EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a2, a1));
 434   }
 435 }
 436
 437 TEST(STLUtilTest, STLSetUnion) {
 438   std::set<int> a1;
 439   a1.insert(1);
 440   a1.insert(2);
 441   a1.insert(3);
 442   a1.insert(4);
 443
 444   std::set<int> a2;
 445   a2.insert(3);
 446   a2.insert(4);
 447   a2.insert(5);
 448   a2.insert(6);
 449   a2.insert(7);
 450
 451   {
 452     std::set<int> result;
 453     result.insert(1);
 454     result.insert(2);
 455     result.insert(3);
 456     result.insert(4);
 457     result.insert(5);
 458     result.insert(6);
 459     result.insert(7);
 460     EXPECT_EQ(result, STLSetUnion<std::set<int> >(a1, a2));
 461   }
 462
 463   {
 464     std::set<int> result;
 465     result.insert(1);
 466     result.insert(2);
 467     result.insert(3);
 468     result.insert(4);
 469     result.insert(5);
 470     result.insert(6);
 471     result.insert(7);
 472     EXPECT_EQ(result, STLSetUnion<std::set<int> >(a2, a1));
 473   }
 474
 475   {
 476     std::vector<int> result;
 477     result.push_back(1);
 478     result.push_back(2);
 479     result.push_back(3);
 480     result.push_back(4);
 481     result.push_back(5);
 482     result.push_back(6);
 483     result.push_back(7);
 484     EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a1, a2));
 485   }
 486
 487   {
 488     std::vector<int> result;
 489     result.push_back(1);
 490     result.push_back(2);
 491     result.push_back(3);
 492     result.push_back(4);
 493     result.push_back(5);
 494     result.push_back(6);
 495     result.push_back(7);
 496     EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a2, a1));
 497   }
 498 }
 499
 500 TEST(STLUtilTest, STLSetIntersection) {
 501   std::set<int> a1;
 502   a1.insert(1);
 503   a1.insert(2);
 504   a1.insert(3);
 505   a1.insert(4);
 506
 507   std::set<int> a2;
 508   a2.insert(3);
 509   a2.insert(4);
 510   a2.insert(5);
 511   a2.insert(6);
 512   a2.insert(7);
 513
 514   {
 515     std::set<int> result;
 516     result.insert(3);
 517     result.insert(4);
 518     EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a1, a2));
 519   }
 520
 521   {
 522     std::set<int> result;
 523     result.insert(3);
 524     result.insert(4);
 525     EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a2, a1));
 526   }
 527
 528   {
 529     std::vector<int> result;
 530     result.push_back(3);
 531     result.push_back(4);
 532     EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a1, a2));
 533   }
 534
 535   {
 536     std::vector<int> result;
 537     result.push_back(3);
 538     result.push_back(4);
 539     EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a2, a1));
 540   }
 541 }
 542
 543 TEST(STLUtilTest, STLIncludes) {
 544   std::set<int> a1;
 545   a1.insert(1);
 546   a1.insert(2);
 547   a1.insert(3);
 548   a1.insert(4);
 549
 550   std::set<int> a2;
 551   a2.insert(3);
 552   a2.insert(4);
 553
 554   std::set<int> a3;
 555   a3.insert(3);
 556   a3.insert(4);
 557   a3.insert(5);
 558
 559   EXPECT_TRUE(STLIncludes<std::set<int> >(a1, a2));
 560   EXPECT_FALSE(STLIncludes<std::set<int> >(a1, a3));
 561   EXPECT_FALSE(STLIncludes<std::set<int> >(a2, a1));
 562   EXPECT_FALSE(STLIncludes<std::set<int> >(a2, a3));
 563   EXPECT_FALSE(STLIncludes<std::set<int> >(a3, a1));
 564   EXPECT_TRUE(STLIncludes<std::set<int> >(a3, a2));
 565 }
 566
 567 TEST(Erase, String) {
 568   const std::pair<std::string, std::string> test_data[] = {
 569       {"", ""}, {"abc", "bc"}, {"abca", "bc"},
 570   };
 571
 572   for (auto test_case : test_data) {
 573     Erase(test_case.first, 'a');
 574     EXPECT_EQ(test_case.second, test_case.first);
 575   }
 576
 577   for (auto test_case : test_data) {
 578     EraseIf(test_case.first, [](char elem) { return elem < 'b'; });
 579     EXPECT_EQ(test_case.second, test_case.first);
 580   }
 581 }
 582
 583 TEST(Erase, String16) {
 584   std::pair<base::string16, base::string16> test_data[] = {
 585       {base::string16(), base::string16()},
 586       {UTF8ToUTF16("abc"), UTF8ToUTF16("bc")},
 587       {UTF8ToUTF16("abca"), UTF8ToUTF16("bc")},
 588   };
 589
 590   const base::string16 letters = UTF8ToUTF16("ab");
 591   for (auto test_case : test_data) {
 592     Erase(test_case.first, letters[0]);
 593     EXPECT_EQ(test_case.second, test_case.first);
 594   }
 595
 596   for (auto test_case : test_data) {
 597     EraseIf(test_case.first, [&](short elem) { return elem < letters[1]; });
 598     EXPECT_EQ(test_case.second, test_case.first);
 599   }
 600 }
 601
 602 TEST(Erase, Deque) {
 603   RunEraseTest<std::deque<int>>();
 604   RunEraseIfTest<std::deque<std::pair<int, int>>>();
 605 }
 606
 607 TEST(Erase, Vector) {
 608   RunEraseTest<std::vector<int>>();
 609   RunEraseIfTest<std::vector<std::pair<int, int>>>();
 610 }
 611
 612 TEST(Erase, ForwardList) {
 613   RunEraseTest<std::forward_list<int>>();
 614   RunEraseIfTest<std::forward_list<std::pair<int, int>>>();
 615 }
 616
 617 TEST(Erase, List) {
 618   RunEraseTest<std::list<int>>();
 619   RunEraseIfTest<std::list<std::pair<int, int>>>();
 620 }
 621
 622 TEST(Erase, Map) {
 623   RunEraseIfTest<std::map<int, int>>();
 624   RunEraseIfTest<std::map<int, int, std::greater<>>>();
 625 }
 626
 627 TEST(Erase, Multimap) {
 628   RunEraseIfTest<std::multimap<int, int>>();
 629   RunEraseIfTest<std::multimap<int, int, std::greater<>>>();
 630 }
 631
 632 TEST(Erase, Set) {
 633   RunEraseIfTest<std::set<std::pair<int, int>>>();
 634   RunEraseIfTest<std::set<std::pair<int, int>, std::greater<>>>();
 635 }
 636
 637 TEST(Erase, Multiset) {
 638   RunEraseIfTest<std::multiset<std::pair<int, int>>>();
 639   RunEraseIfTest<std::multiset<std::pair<int, int>, std::greater<>>>();
 640 }
 641
 642 TEST(Erase, UnorderedMap) {
 643   RunEraseIfTest<std::unordered_map<int, int>>();
 644   RunEraseIfTest<std::unordered_map<int, int, CustomIntHash>>();
 645 }
 646
 647 TEST(Erase, UnorderedMultimap) {
 648   RunEraseIfTest<std::unordered_multimap<int, int>>();
 649   RunEraseIfTest<std::unordered_multimap<int, int, CustomIntHash>>();
 650 }
 651
 652 TEST(Erase, UnorderedSet) {
 653   RunEraseIfTest<std::unordered_set<std::pair<int, int>, HashByFirst>>();
 654 }
 655
 656 TEST(Erase, UnorderedMultiset) {
 657   RunEraseIfTest<std::unordered_multiset<std::pair<int, int>, HashByFirst>>();
 658 }
 659
 660 TEST(Erase, IsNotIn) {
 661   // Should keep both '2' but only one '4', like std::set_intersection.
 662   std::vector<int> lhs = {0, 2, 2, 4, 4, 4, 6, 8, 10};
 663   std::vector<int> rhs = {1, 2, 2, 4, 5, 6, 7};
 664   std::vector<int> expected = {2, 2, 4, 6};
 665   EXPECT_EQ(5u, EraseIf(lhs, IsNotIn<std::vector<int>>(rhs)));
 666   EXPECT_EQ(expected, lhs);
 667 }
 668
 669 TEST(STLUtilTest, GenericContains) {
 670   const char allowed_chars[] = {'a', 'b', 'c', 'd'};
 671
 672   EXPECT_TRUE(Contains(allowed_chars, 'a'));
 673   EXPECT_FALSE(Contains(allowed_chars, 'z'));
 674   EXPECT_FALSE(Contains(allowed_chars, 0));
 675
 676   const char allowed_chars_including_nul[] = "abcd";
 677   EXPECT_TRUE(Contains(allowed_chars_including_nul, 0));
 678 }
 679
 680 TEST(STLUtilTest, ContainsWithFindAndNpos) {
 681   std::string str = "abcd";
 682
 683   EXPECT_TRUE(Contains(str, 'a'));
 684   EXPECT_FALSE(Contains(str, 'z'));
 685   EXPECT_FALSE(Contains(str, 0));
 686 }
 687
 688 TEST(STLUtilTest, ContainsWithFindAndEnd) {
 689   std::set<int> set = {1, 2, 3, 4};
 690
 691   EXPECT_TRUE(Contains(set, 1));
 692   EXPECT_FALSE(Contains(set, 5));
 693   EXPECT_FALSE(Contains(set, 0));
 694 }
 695
 696 TEST(STLUtilTest, ContainsWithContains) {
 697   flat_set<int> set = {1, 2, 3, 4};
 698
 699   EXPECT_TRUE(Contains(set, 1));
 700   EXPECT_FALSE(Contains(set, 5));
 701   EXPECT_FALSE(Contains(set, 0));
 702 }
 703
 704 TEST(STLUtilTest, InsertOrAssign) {
 705   std::map<std::string, int> my_map;
 706   auto result = InsertOrAssign(my_map, "Hello", 42);
 707   EXPECT_THAT(*result.first, Pair("Hello", 42));
 708   EXPECT_TRUE(result.second);
 709
 710   result = InsertOrAssign(my_map, "Hello", 43);
 711   EXPECT_THAT(*result.first, Pair("Hello", 43));
 712   EXPECT_FALSE(result.second);
 713 }
 714
 715 TEST(STLUtilTest, InsertOrAssignHint) {
 716   std::map<std::string, int> my_map;
 717   auto result = InsertOrAssign(my_map, my_map.end(), "Hello", 42);
 718   EXPECT_THAT(*result, Pair("Hello", 42));
 719
 720   result = InsertOrAssign(my_map, my_map.begin(), "Hello", 43);
 721   EXPECT_THAT(*result, Pair("Hello", 43));
 722 }
 723
 724 TEST(STLUtilTest, InsertOrAssignWrongHints) {
 725   std::map<int, int> my_map;
 726   // Since we insert keys in sorted order, my_map.begin() will be a wrong hint
 727   // after the first iteration. Check that insertion happens anyway.
 728   for (int i = 0; i < 10; ++i) {
 729     SCOPED_TRACE(i);
 730     auto result = InsertOrAssign(my_map, my_map.begin(), i, i);
 731     EXPECT_THAT(*result, Pair(i, i));
 732   }
 733
 734   // Overwrite the keys we just inserted. Since we no longer insert into the
 735   // map, my_map.end() will be a wrong hint for all iterations but the last.
 736   for (int i = 0; i < 10; ++i) {
 737     SCOPED_TRACE(10 + i);
 738     auto result = InsertOrAssign(my_map, my_map.end(), i, 10 + i);
 739     EXPECT_THAT(*result, Pair(i, 10 + i));
 740   }
 741 }
 742
 743 TEST(STLUtilTest, TryEmplace) {
 744   std::map<std::string, std::unique_ptr<int>> my_map;
 745   auto result = TryEmplace(my_map, "Hello", nullptr);
 746   EXPECT_THAT(*result.first, Pair("Hello", IsNull()));
 747   EXPECT_TRUE(result.second);
 748
 749   auto new_value = std::make_unique<int>(42);
 750   result = TryEmplace(my_map, "Hello", std::move(new_value));
 751   EXPECT_THAT(*result.first, Pair("Hello", IsNull()));
 752   EXPECT_FALSE(result.second);
 753   // |new_value| should not be touched following a failed insertion.
 754   ASSERT_NE(nullptr, new_value);
 755   EXPECT_EQ(42, *new_value);
 756
 757   result = TryEmplace(my_map, "World", std::move(new_value));
 758   EXPECT_EQ("World", result.first->first);
 759   EXPECT_EQ(42, *result.first->second);
 760   EXPECT_TRUE(result.second);
 761   EXPECT_EQ(nullptr, new_value);
 762 }
 763
 764 TEST(STLUtilTest, TryEmplaceHint) {
 765   std::map<std::string, std::unique_ptr<int>> my_map;
 766   auto result = TryEmplace(my_map, my_map.begin(), "Hello", nullptr);
 767   EXPECT_THAT(*result, Pair("Hello", IsNull()));
 768
 769   auto new_value = std::make_unique<int>(42);
 770   result = TryEmplace(my_map, result, "Hello", std::move(new_value));
 771   EXPECT_THAT(*result, Pair("Hello", IsNull()));
 772   // |new_value| should not be touched following a failed insertion.
 773   ASSERT_NE(nullptr, new_value);
 774   EXPECT_EQ(42, *new_value);
 775
 776   result = TryEmplace(my_map, result, "World", std::move(new_value));
 777   EXPECT_EQ("World", result->first);
 778   EXPECT_EQ(42, *result->second);
 779   EXPECT_EQ(nullptr, new_value);
 780 }
 781
 782 TEST(STLUtilTest, TryEmplaceWrongHints) {
 783   std::map<int, int> my_map;
 784   // Since we emplace keys in sorted order, my_map.begin() will be a wrong hint
 785   // after the first iteration. Check that emplacement happens anyway.
 786   for (int i = 0; i < 10; ++i) {
 787     SCOPED_TRACE(i);
 788     auto result = TryEmplace(my_map, my_map.begin(), i, i);
 789     EXPECT_THAT(*result, Pair(i, i));
 790   }
 791
 792   // Fail to overwrite the keys we just inserted. Since we no longer emplace
 793   // into the map, my_map.end() will be a wrong hint for all tried emplacements
 794   // but the last.
 795   for (int i = 0; i < 10; ++i) {
 796     SCOPED_TRACE(10 + i);
 797     auto result = TryEmplace(my_map, my_map.end(), i, 10 + i);
 798     EXPECT_THAT(*result, Pair(i, i));
 799   }
 800 }
 801
 802 TEST(STLUtilTest, OptionalOrNullptr) {
 803   Optional<float> optional;
 804   EXPECT_EQ(nullptr, base::OptionalOrNullptr(optional));
 805
 806   optional = 0.1f;
 807   EXPECT_EQ(&optional.value(), base::OptionalOrNullptr(optional));
 808   EXPECT_NE(nullptr, base::OptionalOrNullptr(optional));
 809 }
 810
 811 }  // namespace
 812 }  // namespace base