First implementation of flat sets

base/containers/flat_set_unittest.cc

Index: base/containers/flat_set_unittest.cc
diff --git a/base/containers/flat_set_unittest.cc b/base/containers/flat_set_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..dbfb73bd7b5fddd70d4710337824d24340cce03c
--- /dev/null
+++ b/base/containers/flat_set_unittest.cc
@@ -0,0 +1,761 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/containers/flat_set.h"
+
+#include <algorithm>
+#include <functional>
+#include <set>
+#include <string>
+#include <utility>
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+class MoveOnlyInt {
+ public:
+  MoveOnlyInt() = default;
+  explicit MoveOnlyInt(int rhs) : body_(rhs) {}
+
+  operator int() const { return body_; }
+
+  MoveOnlyInt(const MoveOnlyInt&) = delete;
+  MoveOnlyInt(MoveOnlyInt&& rhs) : body_(rhs.body_) { rhs.body_ = 0; }
+  MoveOnlyInt& operator=(const MoveOnlyInt&) = delete;
+  MoveOnlyInt& operator=(MoveOnlyInt&& rhs) {
+    body_ = rhs.body_;
+    rhs.body_ = 0;
+    return *this;
+  }
+  ~MoveOnlyInt() = default;
+
+  friend bool operator<(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) {
+    return lhs.body_ < rhs.body_;
+  }
+
+ private:
+  int body_ = 0;
+};
+
+struct LessByFirst {
+  template <typename FirstPair, typename SecondPair>
+  bool operator()(const FirstPair& lhs, const SecondPair& rhs) {
+    return std::less<typename FirstPair::first_type>()(lhs.first, rhs.first);
+  }
+};
+
+class NonDefaultConstructableCompare {
+ public:
+  NonDefaultConstructableCompare(int) {}
+
+  template <typename T>
+  bool operator()(const T& lhs, const T& rhs) {
+    return std::less<T>()(lhs, rhs);
+  }
+};
+
+NonDefaultConstructableCompare MakeWeiredCmp() {
+  return NonDefaultConstructableCompare(0);
+}
+
+template <typename LhsSet, typename RhsSet>
+bool EqualRanges(const LhsSet& lhs, const RhsSet& rhs) {
+  if (lhs.size() != rhs.size())
+    return false;
+  return std::equal(lhs.begin(), lhs.end(), rhs.begin());
+}
+
+template <typename T, typename Cmp>
+void ExpectSetsAreEqual(const base::flat_set<T, Cmp>& fl_set,
+                        const std::set<T, Cmp>& std_set) {
+  if (EqualRanges(fl_set, std_set))
+    return;
+  std::string error_msg("\nExpected values are: [");
+  for (const auto& v : std_set)
+    error_msg += std::to_string(v) + ' ';
+  error_msg += "]\nActual values are:   [";
+  for (const auto& v : fl_set)
+    error_msg += std::to_string(v) + ' ';
+  error_msg += "]";
+
+  ASSERT_TRUE(false) << error_msg;
+}
+
+#define TEST_INTEGERS_LIST 5, 3, 5, 1, 1, 9, 0,
+
+constexpr int kIntRange[] = {TEST_INTEGERS_LIST};
+
+const std::initializer_list<int> kInitList = {TEST_INTEGERS_LIST};
+
+#undef TEST_INTEGERS_LIST
+
+}  // namespace
+
+namespace base {
+
+using CopySet = flat_set<int>;
+using CopyStdSet = std::set<int>;
+using CopyVec = std::vector<int>;
+using MoveSet = flat_set<MoveOnlyInt>;
+using MoveStdSet = std::set<MoveOnlyInt>;
+using MoveVec = std::vector<MoveOnlyInt>;
+using PairSet = flat_set<std::pair<int, int>, LessByFirst>;
+using PairVec = std::vector<std::pair<int, int>>;
+using WeiredCmpSet = flat_set<int, NonDefaultConstructableCompare>;
+using WeiredCmpStdSet = std::set<int, NonDefaultConstructableCompare>;
+
+TEST(FlatSetOurs, Swap) {
+  using M = flat_set<int>;
+  M lhs{1, 2, 3};
+  M rhs{4};
+  swap(lhs, rhs);
+  EXPECT_EQ(lhs.size(), static_cast<M::size_type>(1));
+  EXPECT_EQ(rhs.size(), static_cast<M::size_type>(3));
+  EXPECT_EQ(rhs.count(1), static_cast<M::size_type>(1));
+  EXPECT_EQ(rhs.count(2), static_cast<M::size_type>(1));
+  EXPECT_EQ(rhs.count(3), static_cast<M::size_type>(1));
+  EXPECT_EQ(lhs.count(1), static_cast<M::size_type>(0));
+  EXPECT_EQ(lhs.count(4), static_cast<M::size_type>(1));
+
+  rhs.swap(lhs);  // member function wokrs too;
+}
+
+TEST(FlatSetOurs, Comparison) {
+  using M = flat_set<int>;
+  M biggest{3};
+  M smallest{1};
+  M middle{1, 2};
+
+  EXPECT_TRUE(biggest == biggest);
+  EXPECT_TRUE(biggest != smallest);
+  EXPECT_TRUE(smallest < middle);
+  EXPECT_TRUE(smallest <= middle);
+  EXPECT_TRUE(biggest >= middle);
+  EXPECT_TRUE(biggest > middle);
+}
+
+TEST(FlatSetOurs, Constructors) {
+  // default constructable
+  { CopySet s1; }
+  // constructable with Compare()
+  {
+    CopySet s1{std::less<int>()};
+    WeiredCmpSet s3{MakeWeiredCmp()};
+  }
+  // constructable with Compare() and Allocator()
+  { CopySet s1{std::less<int>(), std::allocator<int>()}; }
+  // constructable with range
+  {
+    CopySet s1(std::begin(kIntRange), std::end(kIntRange));
+    CopyStdSet std_s1(std::begin(kIntRange), std::end(kIntRange));
+    ExpectSetsAreEqual(s1, std_s1);
+  }
+  // constructable with range and compare
+  {
+    WeiredCmpSet s1(std::begin(kIntRange), std::end(kIntRange),
+                    MakeWeiredCmp());
+    WeiredCmpStdSet std_s1(std::begin(kIntRange), std::end(kIntRange),
+                           MakeWeiredCmp());
+    ExpectSetsAreEqual(s1, std_s1);
+  }
+  // constructable with range, compare and allocator
+  {
+    WeiredCmpSet s1(std::begin(kIntRange), std::end(kIntRange),
+                    NonDefaultConstructableCompare(0), std::allocator<int>());
+    WeiredCmpStdSet std_s1(std::begin(kIntRange), std::end(kIntRange),
+                           MakeWeiredCmp());
+    ExpectSetsAreEqual(s1, std_s1);
+  }
+  // copy constructable
+  {
+    WeiredCmpStdSet test_set(std::begin(kIntRange), std::end(kIntRange),
+                             MakeWeiredCmp());
+
+    WeiredCmpSet s1(std::begin(kIntRange), std::end(kIntRange),
+                    MakeWeiredCmp());
+    WeiredCmpSet s2(s1);
+
+    ExpectSetsAreEqual(s1, test_set);
+    ExpectSetsAreEqual(s2, test_set);
+  }
+  // move constructable
+  {
+    MoveStdSet test_set(std::begin(kIntRange), std::end(kIntRange));
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+
+    MoveSet s2(std::move(s1));
+    ExpectSetsAreEqual(s2, test_set);
+  }
+  // constructable with an allocator
+  { CopySet s1{std::allocator<int>()}; }
+  // copy constructable with an allocator
+  {
+    WeiredCmpStdSet test_set(std::begin(kIntRange), std::end(kIntRange),
+                             MakeWeiredCmp());
+
+    WeiredCmpSet s1(std::begin(kIntRange), std::end(kIntRange),
+                    MakeWeiredCmp());
+
+    WeiredCmpSet s2(s1, std::allocator<int>());
+
+    ExpectSetsAreEqual(s1, test_set);
+    ExpectSetsAreEqual(s2, test_set);
+  }
+  // move constructable with an allocator
+  {
+    MoveStdSet test_set(std::begin(kIntRange), std::end(kIntRange));
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+
+    MoveSet s2(std::move(s1), std::allocator<MoveOnlyInt>());
+    ExpectSetsAreEqual(s2, test_set);
+  }
+  // constructable with an initializer list
+  {
+    CopyStdSet test_set(kInitList);
+    CopySet s1(kInitList);
+
+    ExpectSetsAreEqual(s1, test_set);
+  }
+  // constructable with an initializer list and compare
+  {
+    WeiredCmpStdSet test_set(kInitList, MakeWeiredCmp());
+    WeiredCmpSet s1(kInitList, MakeWeiredCmp());
+
+    ExpectSetsAreEqual(s1, test_set);
+  }
+  // constructable with an initializer list, compare and an allocator
+  {
+    WeiredCmpStdSet test_set(kInitList, MakeWeiredCmp());
+    WeiredCmpSet s1(kInitList, MakeWeiredCmp(), std::allocator<int>());
+
+    ExpectSetsAreEqual(s1, test_set);
+  }
+  // constructable with a range and an allocator
+  {
+    CopyStdSet test_set(std::begin(kIntRange), std::end(kIntRange));
+    CopySet s1(std::begin(kIntRange), std::end(kIntRange),
+               std::allocator<int>());
+
+    ExpectSetsAreEqual(s1, test_set);
+  }
+  // constructable with an initializer list and an allocator
+  {
+    CopyStdSet test_set(kInitList);
+    CopySet s1(kInitList, std::allocator<int>());
+
+    ExpectSetsAreEqual(s1, test_set);
+  }
+}
+
+TEST(FlatSetOurs, Assigments) {
+  using MoveVec = std::vector<MoveOnlyInt>;
+
+  // copy assimgnable
+  {
+    CopyStdSet test_set(kInitList);
+
+    CopySet s1(kInitList);
+    CopySet s2;
+    s2 = s1;
+
+    ExpectSetsAreEqual(s1, test_set);
+    ExpectSetsAreEqual(s2, test_set);
+  }
+  // move assignable
+  {
+    MoveStdSet test_set(std::begin(kIntRange), std::end(kIntRange));
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+    MoveSet s2;
+
+    s2 = std::move(s1);
+    ExpectSetsAreEqual(s2, test_set);
+  }
+  // assignable to an initializer list
+  {
+    CopyStdSet test_set;
+    test_set = kInitList;
+
+    CopySet s1;
+    s1 = kInitList;
+    ExpectSetsAreEqual(s1, test_set);
+  }
+}
+
+TEST(FlatSetOurs, MemoryManagment) {
+  constexpr CopySet::size_type kReserveSize = 5;
+
+  // get allocator
+  {
+    CopyVec test;
+    CopySet s1;
+
+    EXPECT_TRUE(test.get_allocator() == s1.get_allocator());
+  }
+  // capacity
+  {
+    CopyVec test;
+    CopySet s1;
+
+    EXPECT_EQ(s1.capacity(), test.capacity());
+  }
+  // reserve
+  {
+    CopySet s1;
+
+    s1.reserve(kReserveSize);
+    EXPECT_GE(s1.capacity(), kReserveSize);
+  }
+  // shrink to fit
+  {
+    CopySet s1;
+
+    s1.reserve(kReserveSize);
+    s1.insert(kInitList);
+    auto capacity_before = s1.capacity();
+    s1.shrink_to_fit();
+    EXPECT_GE(capacity_before, s1.capacity());  // Shrink to fit is not binding.
+  }
+}
+
+TEST(FlatSetOurs, Iterators) {
+  // begin, end
+  {
+    CopyStdSet test_set(kInitList);
+    CopySet s1(kInitList);
+
+    EXPECT_EQ(CopyVec(test_set.begin(), test_set.end()),
+              CopyVec(s1.begin(), s1.end()));
+  }
+  // const begin, end
+  {
+    CopyStdSet test_set(kInitList);
+    const CopySet s1(kInitList);
+
+    EXPECT_EQ(CopyVec(test_set.begin(), test_set.end()),
+              CopyVec(s1.begin(), s1.end()));
+  }
+  // rbegin, rend
+  {
+    CopyStdSet test_set(kInitList);
+    CopySet s1(kInitList);
+
+    EXPECT_EQ(CopyVec(test_set.rbegin(), test_set.rend()),
+              CopyVec(s1.rbegin(), s1.rend()));
+  }
+  // const rbegin, rend
+  {
+    CopyStdSet test_set(kInitList);
+    const CopySet s1(kInitList);
+
+    EXPECT_EQ(CopyVec(test_set.rbegin(), test_set.rend()),
+              CopyVec(s1.rbegin(), s1.rend()));
+  }
+  // cbegin, cend
+  {
+    CopyStdSet test_set(kInitList);
+    const CopySet s1(kInitList);
+
+    EXPECT_EQ(CopyVec(test_set.cbegin(), test_set.cend()),
+              CopyVec(s1.cbegin(), s1.cend()));
+  }
+  // crbegin, crend
+  {
+    CopyStdSet test_set(kInitList);
+    CopySet s1(kInitList);
+
+    EXPECT_EQ(CopyVec(test_set.crbegin(), test_set.crend()),
+              CopyVec(s1.crbegin(), s1.crend()));
+  }
+}
+
+TEST(FlatSetOurs, CapasityAccessors) {
+  // empty
+  {
+    CopySet s1;
+    EXPECT_TRUE(s1.empty());
+  }
+  // size
+  {
+    CopySet s1;
+    EXPECT_EQ(s1.size(), static_cast<CopySet::size_type>(0));
+  }
+  // max size
+  {
+    CopySet s1;
+    EXPECT_EQ(s1.max_size(), CopyVec().max_size());
+  }
+}
+
+TEST(FlatSetOurs, OneValueInsertionsWithoutHints) {
+  // insert (const value_type&) in the beginning successful
+  {
+    CopySet s1{2, 3, 4};
+
+    const int val1 = 1;
+    auto pos_suc = s1.insert(val1);
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 0);
+    EXPECT_TRUE(pos_suc.second);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+
+  // insert (const value_type&) in the middle successful
+  {
+    CopySet s1{1, 2, 4};
+
+    const int val1 = 3;
+    auto pos_suc = s1.insert(val1);
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 2);
+    EXPECT_TRUE(pos_suc.second);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+
+  // insert (const value_type&) in the end successful
+  {
+    CopySet s1{1, 2, 3};
+
+    const int val1 = 4;
+    auto pos_suc = s1.insert(val1);
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 3);
+    EXPECT_TRUE(pos_suc.second);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+
+  // insert (const value_type&) not successful
+  {
+    CopySet s1{1, 2, 3};
+
+    const int val1 = 1;
+    auto pos_suc = s1.insert(val1);
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 0);
+    EXPECT_FALSE(pos_suc.second);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3}));
+  }
+
+  // insert (value_type&&) in the beginning successful
+  {
+    constexpr int kIntRange[] = {2, 3, 4};
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+
+    auto pos_suc = s1.insert(MoveOnlyInt(1));
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 0);
+    EXPECT_TRUE(pos_suc.second);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+
+  // insert (value_type&&) in the middle successful
+  {
+    constexpr int kIntRange[] = {1, 2, 4};
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+
+    auto pos_suc = s1.insert(MoveOnlyInt(3));
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 2);
+    EXPECT_TRUE(pos_suc.second);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+
+  // insert (value_type&&) in the end successful
+  {
+    constexpr int kIntRange[] = {1, 2, 3};
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+
+    auto pos_suc = s1.insert(MoveOnlyInt(4));
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 3);
+    EXPECT_TRUE(pos_suc.second);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+  // insert (value_type&&) not successful
+  {
+    constexpr int kIntRange[] = {1, 2, 3};
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+
+    auto pos_suc = s1.insert(MoveOnlyInt(1));
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 0);
+    EXPECT_FALSE(pos_suc.second);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3}));
+  }
+
+  // emplace (Args&&...) in the beginning successful
+  {
+    PairSet s1{{2, 0}, {3, 0}, {4, 0}};
+
+    auto pos_suc = s1.emplace(1, 0);
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 0);
+    EXPECT_TRUE(pos_suc.second);
+    EXPECT_EQ(PairVec(s1.begin(), s1.end()),
+              PairVec({{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+  }
+  // emplace (Args&&...) in the middle successful
+  {
+    PairSet s1{{1, 0}, {2, 0}, {4, 0}};
+
+    auto pos_suc = s1.emplace(3, 0);
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 2);
+    EXPECT_TRUE(pos_suc.second);
+    EXPECT_EQ(PairVec(s1.begin(), s1.end()),
+              PairVec({{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+  }
+  // emplace (Args&&...) in the end successful
+  {
+    PairSet s1{{1, 0}, {2, 0}, {3, 0}};
+
+    auto pos_suc = s1.emplace(4, 0);
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 3);
+    EXPECT_TRUE(pos_suc.second);
+    EXPECT_EQ(PairVec(s1.begin(), s1.end()),
+              PairVec({{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+  }
+  // emplace (Args&&...) is not successful
+  {
+    PairSet s1{{1, 0}, {2, 0}, {3, 0}};
+
+    auto pos_suc = s1.emplace(3, 1);  // checking that we keep the old one
+
+    EXPECT_EQ(pos_suc.first - s1.begin(), 2);
+    EXPECT_FALSE(pos_suc.second);
+    EXPECT_EQ(PairVec(s1.begin(), s1.end()), PairVec({{1, 0}, {2, 0}, {3, 0}}));
+  }
+}
+
+TEST(FlatSetOurs, InsertingWithAHint) {
+  // inserting (position, const &) with correct hint in the beginning is
+  // succesfull
+  {
+    CopySet s1{2, 3, 4};
+
+    const int val1 = 1;
+    auto pos = s1.insert(s1.begin(), val1);
+
+    EXPECT_EQ(pos - s1.begin(), 0);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+  // inserting (position, const &) with correct hint in the middle is succesfull
+  {
+    CopySet s1{1, 2, 4};
+
+    const int val1 = 3;
+    auto pos = s1.insert(s1.begin() + 2, val1);
+
+    EXPECT_EQ(pos - s1.begin(), 2);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+  // inserting (position, const &) with correct hint in the end is succesfull
+  {
+    CopySet s1{1, 2, 3};
+
+    const int val1 = 4;
+    auto pos = s1.insert(s1.end(), val1);
+
+    EXPECT_EQ(pos - s1.begin(), 3);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+  // inserting (position, const &) with hint is not succefful
+  {
+    CopySet s1{1, 2, 3};
+
+    const int val1 = 2;
+    auto pos = s1.insert(s1.begin(), val1);
+
+    EXPECT_EQ(pos - s1.begin(), 1);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3}));
+  }
+
+  // inserting (position, &&) with correct hint in the beginning is succefful
+  {
+    constexpr int kIntRange[] = {2, 3, 4};
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+
+    auto pos = s1.insert(s1.begin(), MoveOnlyInt(1));
+
+    EXPECT_EQ(pos - s1.begin(), 0);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+  // inserting (position, &&) with correct hint in the middle is succefful
+  {
+    constexpr int kIntRange[] = {1, 2, 4};
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+
+    auto pos = s1.insert(s1.begin() + 2, MoveOnlyInt(3));
+
+    EXPECT_EQ(pos - s1.begin(), 2);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+  // inserting (position, &&) with correct hint in the end is succesfull
+  {
+    constexpr int kIntRange[] = {1, 2, 3};
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+
+    auto pos = s1.insert(s1.end(), MoveOnlyInt(4));
+
+    EXPECT_EQ(pos - s1.begin(), 3);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+  // inserting (position, &&) with hint is not succefful
+  {
+    constexpr int kIntRange[] = {1, 2, 3};
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1(std::make_move_iterator(vec.begin()),
+               std::make_move_iterator(vec.end()));
+
+    auto pos = s1.insert(s1.begin(), MoveOnlyInt(2));
+
+    EXPECT_EQ(pos - s1.begin(), 1);
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3}));
+  }
+
+  // emplace_hint (position Args&&...) with correct hint in the beginning
+  // successful
+  {
+    PairSet s1{{2, 0}, {3, 0}, {4, 0}};
+
+    auto pos = s1.emplace_hint(s1.begin(), 1, 0);
+
+    EXPECT_EQ(pos - s1.begin(), 0);
+    EXPECT_EQ(PairVec(s1.begin(), s1.end()),
+              PairVec({{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+  }
+  // emplace_hint (position Args&&...) with correct hint in the middle
+  // successful
+  {
+    PairSet s1{{1, 0}, {2, 0}, {4, 0}};
+
+    auto pos = s1.emplace_hint(s1.begin() + 2, 3, 0);
+
+    EXPECT_EQ(pos - s1.begin(), 2);
+    EXPECT_EQ(PairVec(s1.begin(), s1.end()),
+              PairVec({{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+  }
+  // emplace_hint (position Args&&...) with correct hint in the end successful
+  {
+    PairSet s1{{1, 0}, {2, 0}, {3, 0}};
+
+    auto pos = s1.emplace_hint(s1.end(), 4, 0);
+
+    EXPECT_EQ(pos - s1.begin(), 3);
+    EXPECT_EQ(PairVec(s1.begin(), s1.end()),
+              PairVec({{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+  }
+  // emplace_hint (position Args&&...) is not successful
+  {
+    PairSet s1{{1, 0}, {2, 0}, {3, 0}};
+
+    auto pos = s1.emplace_hint(s1.begin(), 2, 0);
+
+    EXPECT_EQ(pos - s1.begin(), 1);
+    EXPECT_EQ(PairVec(s1.begin(), s1.end()), PairVec({{1, 0}, {2, 0}, {3, 0}}));
+  }
+}
+
+TEST(FlatSetOurs, InsertRange) {
+  // insert (first, last) simple
+  {
+    CopyStdSet test_set(std::begin(kIntRange), std::end(kIntRange));
+    CopySet s1;
+
+    s1.insert(std::begin(kIntRange), std::end(kIntRange));
+
+    ExpectSetsAreEqual(s1, test_set);
+  }
+  // insert ({}) simple
+  {
+    CopyStdSet test_set(kInitList);
+    CopySet s1;
+
+    s1.insert(kInitList);
+
+    ExpectSetsAreEqual(s1, test_set);
+  }
+
+  // insert (first, last) move only
+  {
+    MoveStdSet test_set(std::begin(kIntRange), std::end(kIntRange));
+    MoveSet s1;
+
+    MoveVec vec(std::begin(kIntRange), std::end(kIntRange));
+
+    s1.insert(std::make_move_iterator(vec.begin()),
+              std::make_move_iterator(vec.end()));
+
+    ExpectSetsAreEqual(s1, test_set);
+  }
+
+  // insert (first, last) simple merge
+  {
+    CopySet s1{1, 2, 3};
+    constexpr int kMergingRange[] = {1, 4};
+    s1.insert(std::begin(kMergingRange), std::end(kMergingRange));
+
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+  // insert ({}) simple merge
+  {
+    CopySet s1{1, 2, 3};
+    s1.insert({1, 4});
+
+    EXPECT_EQ(CopyVec(s1.begin(), s1.end()), CopyVec({1, 2, 3, 4}));
+  }
+
+  // insert (first, last) stable regarding already inserted
+  {
+    PairSet s1{{1, 0}, {2, 0}, {3, 0}, {4, 0}};
+    const std::pair<int, int> kMergingRange[] = {
+        {1, 1}, {2, 1}, {1, 2}, {3, 1}};
+    s1.insert(std::begin(kMergingRange), std::end(kMergingRange));
+
+    EXPECT_EQ(PairVec(s1.begin(), s1.end()),
+              PairVec({{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+  }
+  // insert ({}) stable regarding already inserted
+  {
+    PairSet s1{{1, 0}, {2, 0}, {3, 0}, {4, 0}};
+    s1.insert({{1, 1}, {2, 1}, {1, 2}, {3, 1}});
+
+    EXPECT_EQ(PairVec(s1.begin(), s1.end()),
+              PairVec({{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+  }
+}
+
+}  // namespace base