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..5e49f4bb37a933eb567797b578cdd8c94d915105
--- /dev/null
+++ b/base/containers/flat_set_unittest.cc
@@ -0,0 +1,1764 @@
+// 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"
+
+// Following tests are modified and extended tests from libcpp for std::set.

[Peter Kasting, 2016/12/16 08:09:08]

You say "extended" here, but below you document only removals, not extensions.

I kinda feel like either we should document the extensions too, or we should
just remove all this?  I lean towards the latter, because honestly, these are
our tests, and we're going to change the syntax, style, etc., so trying to
document all the exact differences doesn't make a ton of sense to me.

[dyaroshev, 2016/12/18 22:27:23]

Changed the description a bit. I think removed tests can be useful because they
expose different subtle issues that I think are useful to support in the future.
And when we support them we should port those tests too.

+// They can be found here:
+// https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associative/set
+//
+// Removed tests:
+// * No tests with PrivateConstructor and std::less<> changed to std::less<T>
+//   These tests have to do with C++14 std::less<>
+//   http://en.cppreference.com/w/cpp/utility/functional/less_void
+//   and add support for templated versions of lookup functions.
+//   Current implementation of flat containers doesn't support it.
+// * No tests with TemplateConstructor.
+//   Library working group issue: LWG #2059
+//   http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2059
+//   There is an ambiguity between erase with an iterator and erase with a key,
+//   if key has a templated constructor. We have to fix this.
+// * No tests for max_size()
+//   Has to do with allocator support.
+// * No tests with DefaultOnly.
+//   Standard containers allocate each element in the separate node on the heap
+//   and then manipulate these nodes. Flat containers store their elements in
+//   contiguous memory and move them around, type is required to be movable.
+// * No tests for N3644.
+//   This proposal suggests that all default constructed iterators compare
+//   equal. Currently we use std::vector iterators and they don't implement
+//   this.
+// * No tests with min_allocator.
+//   Allocators are not widely used in Chromium, and how we are going to
+//   customize underlying data (if we are going to) is still up to debate.
+// * No tests, counting allocations. Flat sets have different allocation

[Peter Kasting, 2016/12/16 08:09:08]

Nit: No comma

[dyaroshev, 2016/12/18 22:27:24]

Done.

+//   patterns than std::sets and we do not consider them to be a part of the
+//   interface.
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+class MoveOnly {
+  MoveOnly(const MoveOnly&);

[Peter Kasting, 2016/12/16 08:09:07]

Nit: As much as possible, declare private section after public.  (multiple
places)

[dyaroshev, 2016/12/18 22:27:24]

Done.

+  MoveOnly& operator=(const MoveOnly&);

[Peter Kasting, 2016/12/16 08:09:07]

Nit: Use DISALLOW_COPY_AND_ASSIGN to remove these.  (2 places)

[dyaroshev, 2016/12/18 22:27:24]

Done.

+
+  int data_;
+
+ public:
+  MoveOnly(int data = 1) : data_(data) {}
+  MoveOnly(MoveOnly&& x) : data_(x.data_) { x.data_ = 0; }

[Peter Kasting, 2016/12/16 08:09:07]

Nit: |rhs| may be a more idiomatic name than |x|.  (multiple places)

[dyaroshev, 2016/12/18 22:27:23]

Replied in other comment

+  MoveOnly& operator=(MoveOnly&& x) {
+    data_ = x.data_;
+    x.data_ = 0;

[Peter Kasting, 2016/12/16 08:09:08]

Why set x.data_ at all?  So behavior failures will be more obvious?  (multiple
places)

[dyaroshev, 2016/12/18 22:27:23]

We check that we don't leave moved out elements.

+    return *this;
+  }
+
+  int get() const { return data_; }

[Peter Kasting, 2016/12/16 08:09:07]

Nit: Accessors should be named like the underlying member.  (2 places)

[dyaroshev, 2016/12/18 22:27:23]

Done.

+
+  bool operator==(const MoveOnly& x) const { return data_ == x.data_; }
+  bool operator<(const MoveOnly& x) const { return data_ < x.data_; }
+};
+
+template <class It, class ItTraits = It>
+class input_iterator {
+  typedef std::iterator_traits<ItTraits> Traits;
+  It it_;
+
+  template <class U, class T>
+  friend class input_iterator;
+
+ public:
+  typedef std::input_iterator_tag iterator_category;
+  typedef typename Traits::value_type value_type;
+  typedef typename Traits::difference_type difference_type;
+  typedef It pointer;
+  typedef typename Traits::reference reference;
+
+  It base() const { return it_; }
+
+  input_iterator() : it_() {}
+  explicit input_iterator(It it) : it_(it) {}
+  template <class U, class T>
+  input_iterator(const input_iterator<U, T>& u) : it_(u.it_) {}
+
+  reference operator*() const { return *it_; }
+  pointer operator->() const { return it_; }
+
+  input_iterator& operator++() {
+    ++it_;
+    return *this;
+  }
+  input_iterator operator++(int) {
+    input_iterator tmp(*this);
+    ++(*this);
+    return tmp;
+  }
+
+  friend bool operator==(const input_iterator& x, const input_iterator& y) {
+    return x.it_ == y.it_;
+  }
+  friend bool operator!=(const input_iterator& x, const input_iterator& y) {
+    return !(x == y);
+  }
+
+  template <class T>
+  void operator,(T const&) = delete;

[Peter Kasting, 2016/12/16 08:09:08]

Why?

[dyaroshev, 2016/12/18 22:27:23]

Copied from libc++. I think this is to avoid some scary typos. Removed.

+};
+
+template <class T, class TV, class U, class UV>
+inline bool operator==(const input_iterator<T, TV>& x,
+                       const input_iterator<U, UV>& y) {
+  return x.base() == y.base();
+}
+
+template <class T, class TV, class U, class UV>
+inline bool operator!=(const input_iterator<T, TV>& x,
+                       const input_iterator<U, UV>& y) {
+  return !(x == y);
+}
+
+class Emplaceable {
+  Emplaceable(const Emplaceable&);
+  Emplaceable& operator=(const Emplaceable&);
+
+  int int_;
+  double double_;
+
+ public:
+  Emplaceable() : int_(0), double_(0) {}
+  Emplaceable(int i, double d) : int_(i), double_(d) {}
+  Emplaceable(Emplaceable&& x) : int_(x.int_), double_(x.double_) {
+    x.int_ = 0;
+    x.double_ = 0;
+  }
+  Emplaceable& operator=(Emplaceable&& x) {
+    int_ = x.int_;
+    x.int_ = 0;
+    double_ = x.double_;
+    x.double_ = 0;
+    return *this;
+  }
+
+  bool operator==(const Emplaceable& x) const {
+    return int_ == x.int_ && double_ == x.double_;
+  }
+  bool operator<(const Emplaceable& x) const {
+    return int_ < x.int_ || (int_ == x.int_ && double_ < x.double_);
+  }
+
+  int get() const { return int_; }
+};
+
+class NonDefaultConstructibleCompare {
+ public:
+  NonDefaultConstructibleCompare(int) {}
+
+  template <typename T>
+  bool operator()(const T& lhs, const T& rhs) {
+    return std::less<T>()(lhs, rhs);
+  }
+};
+
+}  // namespace
+
+// ----------------------------------------------------------------------------
+// Class:
+
+// Check that base::flat_set and it's iterators can be instantiated with an

[Peter Kasting, 2016/12/16 08:09:07]

Nit: its

[dyaroshev, 2016/12/18 22:27:24]

Done.

+// incomplete type.
+
+TEST(FlatSet, IncompleteType) {
+  struct A {
+    typedef base::flat_set<A> Set;
+    int data;
+    Set m;
+    Set::iterator it;
+    Set::const_iterator cit;
+  };
+
+  // libcpp tests define operator< for A, but clang is complaining that it's
+  // unused

[Peter Kasting, 2016/12/16 08:09:08]

Nit: Not a complete sentence, too vague to be useful/actionable (if you really
need to describe this difference put it in the section atop the file?)

[dyaroshev, 2016/12/18 22:27:23]

It's just strange to declare a set of type without comparison. So I wanted to
point that out.

+
+  A a;
+}
+
+// ----------------------------------------------------------------------------
+// Types:
+
+// class flat_set

[Peter Kasting, 2016/12/16 08:09:08]

Nit: No need to "// class flat_set" above all these tests.

[dyaroshev, 2016/12/18 22:27:23]

Done.

+
+//     // types:
+//     typedef Key                                      key_type;
+//     typedef key_type                                 value_type;
+//     typedef Compare                                  key_compare;
+//     typedef key_compare                              value_compare;
+//     typedef Allocator                                allocator_type;
+//     typedef typename allocator_type::reference       reference;
+//     typedef typename allocator_type::const_reference const_reference;
+//     typedef typename allocator_type::pointer         pointer;
+//     typedef typename allocator_type::const_pointer   const_pointer;
+//     typedef typename allocator_type::size_type       size_type;
+//     typedef typename allocator_type::difference_type difference_type;
+
+TEST(FlatSet, Types) {
+  {

[Peter Kasting, 2016/12/16 08:09:07]

Nit: Avoid these {} blocks in tests except where you actually have multiple such
blocks.

[dyaroshev, 2016/12/18 22:27:24]

Done.

+    typedef base::flat_set<int> C;

[Peter Kasting, 2016/12/16 08:09:08]

Nit: "using" type aliases seem slightly more readable than typedefs to me.

Avoid cryptic type names like "C".  "Set" here would be fine.  (multiple tests)

[dyaroshev, 2016/12/18 22:27:23]

Done.

+    static_assert((std::is_same<C::key_type, int>::value), "");
+    static_assert((std::is_same<C::value_type, int>::value), "");
+    static_assert((std::is_same<C::key_compare, std::less<int>>::value), "");
+    static_assert((std::is_same<C::value_compare, std::less<int>>::value), "");
+    static_assert((std::is_same<C::allocator_type, std::allocator<int>>::value),
+                  "");
+    static_assert((std::is_same<C::reference, int&>::value), "");

[dyaroshev, 2016/12/15 16:10:59]

Tests for reference/pointer etc are libc++ specific. Fix with the next patch.

[dyaroshev, 2016/12/18 22:27:24]

Done.

+    static_assert((std::is_same<C::const_reference, const int&>::value), "");
+    static_assert((std::is_same<C::pointer, int*>::value), "");
+    static_assert((std::is_same<C::const_pointer, const int*>::value), "");
+    static_assert((std::is_same<C::size_type, std::size_t>::value), "");

[Peter Kasting, 2016/12/16 08:09:07]

Nit: For better or worse, Chromium code does not qualify size_t with std::.

[dyaroshev, 2016/12/18 22:27:24]

Done.

+    static_assert((std::is_same<C::difference_type, std::ptrdiff_t>::value),
+                  "");
+  }
+}
+
+// ----------------------------------------------------------------------------
+// Lifetime.
+
+// class flat_set
+
+// flat_set()
+// flat_set(const Compare& comp, const Allocator& alloc = Allocator())
+// flat_set(const Allocator& alloc)
+
+TEST(FlatSet, DefaultConstructor) {
+  {
+    typedef base::flat_set<int> M;
+
+    M m;
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(0));

[Peter Kasting, 2016/12/16 08:09:07]

Nit: Say 0U instead of casting to size_type.  (The static_assert above ensures
this is always size_t.)  Also, for EXPECT_EQ/NE, use (expected, actual) order. 
(many places)

[dyaroshev, 2016/12/18 22:27:24]

Done.

+  }
+
+  {
+    typedef base::flat_set<int, NonDefaultConstructibleCompare> M;
+
+    M m{NonDefaultConstructibleCompare(0)};
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(0));
+  }
+}
+
+// class flat_set
+
+// flat_set(InputIterator first,
+//          InputIterator last,
+//          const Compare& comp = Compare(),
+//          const Allocator& alloc = Allocator())
+// flat_set(InputIterator first, InputIterator last, const Allocator& alloc)
+
+TEST(FlatSet, RangeConstructor) {
+  {
+    typedef base::flat_set<int> M;
+    typedef int V;
+
+    V ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
+
+    M m(input_iterator<const V*>(ar),
+        input_iterator<const V*>(ar + sizeof(ar) / sizeof(ar[0])));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*m.begin(), 1);
+    EXPECT_EQ(*next(m.begin()), 2);

[Peter Kasting, 2016/12/16 08:09:08]

Nit: Shouldn't this be std::next()?  (many places)

[dyaroshev, 2016/12/18 22:27:24]

Worked because of ADL lookup. Copied from libc++ this way. Done.

+    EXPECT_EQ(*next(m.begin(), 2), 3);
+  }
+  {
+    typedef base::flat_set<int, NonDefaultConstructibleCompare> M;
+    typedef int V;
+
+    V ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
+
+    M m(input_iterator<const V*>(ar),
+        input_iterator<const V*>(ar + sizeof(ar) / sizeof(ar[0])),
+        NonDefaultConstructibleCompare(0));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*m.begin(), 1);
+    EXPECT_EQ(*next(m.begin()), 2);
+    EXPECT_EQ(*next(m.begin(), 2), 3);
+  }
+}
+
+// class flat_set
+
+// flat_set(const flat_set& x)
+// flat_set(const flat_set& x, const Allocator& alloc)
+
+TEST(FlatSet, CopyConstructor) {
+  {
+    typedef base::flat_set<int> M;
+    typedef int V;
+
+    V ar[] = {1, 2, 3, 4};
+
+    M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    M m2(m);
+
+    EXPECT_EQ(m2.count(1), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(2), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(3), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(4), static_cast<M::size_type>(1));

[Peter Kasting, 2016/12/16 08:09:08]

Nit: Here and a lot of places below it seems like a lot of lines are spent just
checking all the elements of the set.  Worse, we use various different methods
(repeatedly calling count(), dereferencing all the iterators, etc.)

I suggest defining a helper to check equality with some array/initializer_list
or something, so you can condense these to something more readable like
EXPECT_TRUE(SetIs(m2, {1, 2, 3, 4}));

(That's assuming you can't get something like EXPECT_EQ(m2, {1, 2, 3, 4}) to
work, which would be even better.)

[dyaroshev, 2016/12/18 22:27:23]

Done.

+  }
+}
+
+// class flat_set
+
+// flat_set(flat_set&& x)
+// flat_set(flat_set&& x, const Allocator& alloc)
+
+TEST(FlatSet, MoveConstructor) {
+  {
+    typedef base::flat_set<MoveOnly> M;
+    typedef int V;
+
+    V ar[] = {1, 2, 3, 4};
+
+    M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    M m2(std::move(m));
+
+    EXPECT_EQ(m2.count(1), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(2), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(3), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(4), static_cast<M::size_type>(1));
+  }
+}
+
+// class flat_set
+
+//  flat_set(std::initializer_list<value_type> il,
+//           const Compare& comp = Compare(),
+//           const Allocator& alloc = Allocator())
+//  flat_set(std::initializer_list<value_type> il, const Allocator& a)
+
+TEST(FlatSet, InitializerListConstructor) {
+  {
+    typedef base::flat_set<int> M;
+    typedef M::value_type V;

[Peter Kasting, 2016/12/16 08:09:07]

Nit: Just use int directly, and don't bother with the explicit constructions
below.  (many places)

[dyaroshev, 2016/12/18 22:27:24]

Done.

+
+    M m{1, 2, 3, 4, 5, 6, 10, 8};
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(8));
+    EXPECT_EQ(distance(m.begin(), m.end()),

[Peter Kasting, 2016/12/16 08:09:08]

Nit: Shouldn't this be std::distance?  (3 places)

[dyaroshev, 2016/12/18 22:27:24]

Done.

+              static_cast<M::difference_type>(m.size()));

[Peter Kasting, 2016/12/16 08:09:07]

Nit: Use ptrdiff_t directly (many places)

[dyaroshev, 2016/12/18 22:27:24]

I don't think that the standard guaranties this. Anyways I think this way
clearer shows the intention.

[Peter Kasting, 2016/12/18 22:47:43]

The standard doesn't, but your static_assertions at the top of this file do.  If
this wasn't correct, the file couldn't compile.

This is related to why we explicitly direct people in the codebase to use size_t
instead of e.g. string::size_type.

It's a tradeoff, intent-wise.  You're right that this way makes clear that the
key is to match the result of calling distance().  The other route makes more
clear that in fact, you're guaranteed that that result is a ptrdiff_t.

The main reason I prefer one is just that it's shorter and has fewer symbols
than the other, and since the cast is mostly noise to get the test to compile
without complaint, and not "an important piece of functionality programmers
should read", I figure, just minimize that noise.

Again, I could be convinced to do otherwise.

+    M::const_iterator i = m.cbegin();
+    EXPECT_EQ(*i, V(1));
+    EXPECT_EQ(*++i, V(2));
+    EXPECT_EQ(*++i, V(3));
+    EXPECT_EQ(*++i, V(4));
+    EXPECT_EQ(*++i, V(5));
+    EXPECT_EQ(*++i, V(6));
+    EXPECT_EQ(*++i, V(8));
+    EXPECT_EQ(*++i, V(10));
+  }
+  {
+    typedef base::flat_set<int, NonDefaultConstructibleCompare> M;
+    typedef M::value_type V;
+
+    M m({1, 2, 3, 4, 5, 6, 10, 8}, NonDefaultConstructibleCompare(0));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(8));
+    EXPECT_EQ(distance(m.begin(), m.end()),
+              static_cast<M::difference_type>(m.size()));
+    M::const_iterator i = m.cbegin();
+    EXPECT_EQ(*i, V(1));
+    EXPECT_EQ(*++i, V(2));
+    EXPECT_EQ(*++i, V(3));
+    EXPECT_EQ(*++i, V(4));
+    EXPECT_EQ(*++i, V(5));
+    EXPECT_EQ(*++i, V(6));
+    EXPECT_EQ(*++i, V(8));
+    EXPECT_EQ(*++i, V(10));
+  }
+}
+
+// ----------------------------------------------------------------------------
+// Assignments.
+
+// class flat_set
+
+// flat_set& operator=(const flat_set& x)
+
+TEST(FlatSet, CopyAssignable) {
+  {
+    typedef base::flat_set<int> M;
+    typedef int V;
+
+    V ar[] = {1, 2, 3, 4};
+
+    M m(ar, ar + sizeof(ar) / sizeof(ar[0]));

[Peter Kasting, 2016/12/16 08:09:08]

Nit: use arraysize().  (Multiple places)

[dyaroshev, 2016/12/18 22:27:23]

Changed to using initiailizer lists and begin/end

+    M m2;
+    m2 = m;
+
+    EXPECT_EQ(m2.count(1), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(2), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(3), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(4), static_cast<M::size_type>(1));
+  }
+}
+
+// class flat_set
+
+// flat_set& operator=(flat_set&& x)
+
+TEST(FlatSet, MoveAssignable) {
+  {
+    typedef base::flat_set<MoveOnly> M;
+    typedef int V;
+
+    V ar[] = {1, 2, 3, 4};
+
+    M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    M m2;
+    m2 = std::move(m);
+
+    EXPECT_EQ(m2.count(1), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(2), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(3), static_cast<M::size_type>(1));
+    EXPECT_EQ(m2.count(4), static_cast<M::size_type>(1));
+  }
+}
+
+// class flat_set
+
+// flat_set& operator=(std::initializer_list<value_type> il)
+
+TEST(FlatSet, InitializerListAssignable) {
+  {
+    typedef base::flat_set<int> M;
+    typedef M::value_type V;
+
+    M m{0};
+    m = {1, 2, 3, 4, 5, 6, 10, 8};
+
+    EXPECT_EQ(m.count(0), static_cast<M::size_type>(0));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(8));
+    EXPECT_EQ(distance(m.begin(), m.end()),
+              static_cast<M::difference_type>(m.size()));
+    M::const_iterator i = m.cbegin();
+    EXPECT_EQ(*i, V(1));
+    EXPECT_EQ(*++i, V(2));
+    EXPECT_EQ(*++i, V(3));
+    EXPECT_EQ(*++i, V(4));
+    EXPECT_EQ(*++i, V(5));
+    EXPECT_EQ(*++i, V(6));
+    EXPECT_EQ(*++i, V(8));
+    EXPECT_EQ(*++i, V(10));
+  }
+}
+
+// --------------------------------------------------------------------------
+// Memory management.
+
+// class flat_set
+
+// void reserve(size_type size)
+
+TEST(FlatSet, Reserve) {
+  {
+    typedef base::flat_set<int> M;
+    M m{1, 2, 3};
+
+    m.reserve(5);
+    EXPECT_GE(m.capacity(), static_cast<M::size_type>(5));
+  }
+}
+
+// class flat_set
+
+// size_type capacity() const
+
+TEST(FlatSet, Capacity) {
+  {
+    typedef base::flat_set<int> M;
+    M m{1, 2, 3};
+    EXPECT_GE(m.capacity(), m.size());
+  }
+}
+
+// class flat_set
+
+// void shrink_to_fit()
+
+TEST(FlatSet, ShrinkToFit) {
+  {
+    typedef base::flat_set<int> M;
+    M m{1, 2, 3};
+
+    M::size_type capacity_before = m.capacity();
+    m.shrink_to_fit();
+    EXPECT_GE(capacity_before, m.capacity());

[Peter Kasting, 2016/12/16 08:09:08]

Maybe a stronger test would be to reserve() more space first, then EXPECT_GT
here?  Otherwise, shrink_to_fit() could do nothing and this test would pass.

[dyaroshev, 2016/12/18 22:27:23]

I've checked against the spec: shrink_to_fit can do nothing and still be a
conforming shrink_to_fit.

[Peter Kasting, 2016/12/18 22:47:43]

Wow.  That seems unfortunate.

I would add an explicit comment here noting that this test intentionally doesn't
verify that shrink_to_fit() shrinks anything, due to the reason you just gave :(

+  }
+}
+
+// ----------------------------------------------------------------------------
+// Size management.
+
+// class flat_set
+
+// void clear();
+
+TEST(FlatSet, Clear) {
+  typedef base::flat_set<int> M;
+  typedef int V;
+
+  V ar[] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+  EXPECT_EQ(m.size(), static_cast<M::size_type>(8));
+  m.clear();
+  EXPECT_EQ(m.size(), static_cast<M::size_type>(0));
+}
+
+// class flat_set
+
+// size_type size() const;
+
+TEST(FlatSet, Size) {
+  {
+    typedef base::flat_set<int> M;
+    M m;
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(0));
+    m.insert(M::value_type(2));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    m.insert(M::value_type(1));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    m.insert(M::value_type(3));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    m.erase(m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    m.erase(m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    m.erase(m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(0));
+  }
+}
+
+// class flat_set
+
+// bool empty() const;
+
+TEST(FlatSet, Empty) {
+  typedef base::flat_set<int> M;
+  M m;
+  EXPECT_TRUE(m.empty());
+  m.insert(M::value_type(1));
+  EXPECT_FALSE(m.empty());
+  m.clear();
+  EXPECT_TRUE(m.empty());
+}
+
+// ----------------------------------------------------------------------------
+// Iterators.
+
+// class flat_set
+
+//       iterator begin();
+// const_iterator begin() const;
+//       iterator end();
+// const_iterator end()   const;
+//
+//       reverse_iterator rbegin();
+// const_reverse_iterator rbegin() const;
+//       reverse_iterator rend();
+// const_reverse_iterator rend()   const;
+//
+// const_iterator         cbegin()  const;
+// const_iterator         cend()    const;
+// const_reverse_iterator crbegin() const;
+// const_reverse_iterator crend()   const;
+
+TEST(FlatSet, Iterators) {
+  {
+    typedef int V;
+
+    V ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4,
+              5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8};
+
+    base::flat_set<int> m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    EXPECT_EQ(std::distance(m.begin(), m.end()),
+              static_cast<base::flat_set<int>::difference_type>(m.size()));
+    EXPECT_EQ(std::distance(m.rbegin(), m.rend()),
+              static_cast<base::flat_set<int>::difference_type>(m.size()));
+    base::flat_set<int>::iterator i;
+    i = m.begin();
+    base::flat_set<int>::const_iterator k = i;
+    EXPECT_EQ(i, k);
+    for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)

[Peter Kasting, 2016/12/16 08:09:08]

Nit: What about:

  for (int j = 1; i != m.end(); ++i, ++j)

This avoids the need to cast.  (2 places)

[dyaroshev, 2016/12/18 22:27:23]

Done.

+      EXPECT_EQ(*i, j);
+  }
+  {
+    typedef int V;
+
+    V ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4,
+              5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8};
+
+    const base::flat_set<int> m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    EXPECT_EQ(std::distance(m.begin(), m.end()),
+              static_cast<base::flat_set<int>::difference_type>(m.size()));
+    EXPECT_EQ(std::distance(m.cbegin(), m.cend()),
+              static_cast<base::flat_set<int>::difference_type>(m.size()));
+    EXPECT_EQ(std::distance(m.rbegin(), m.rend()),
+              static_cast<base::flat_set<int>::difference_type>(m.size()));
+    EXPECT_EQ(std::distance(m.crbegin(), m.crend()),
+              static_cast<base::flat_set<int>::difference_type>(m.size()));
+    base::flat_set<int>::const_iterator i;
+    i = m.begin();
+    for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
+      EXPECT_EQ(*i, j);
+  }
+}
+
+// ----------------------------------------------------------------------------
+// Insert/Erase operations.
+
+// class flat_set
+
+// pair<iterator, bool> insert(const value_type& v);
+
+TEST(FlatSet, InsertCV) {
+  {
+    typedef base::flat_set<int> M;
+    typedef M::value_type V;
+    typedef std::pair<M::iterator, bool> R;
+
+    M m;
+    V v(2);
+    R r = m.insert(v);
+    EXPECT_TRUE(r.second);
+    EXPECT_EQ(r.first, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    EXPECT_EQ(*r.first, 2);
+
+    v = 1;
+    r = m.insert(v);
+    EXPECT_TRUE(r.second);
+    EXPECT_EQ(r.first, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(*r.first, 1);
+
+    v = 3;
+    r = m.insert(v);
+    EXPECT_TRUE(r.second);
+    EXPECT_EQ(r.first, prev(m.end()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*r.first, 3);
+
+    v = 3;
+    r = m.insert(v);
+    EXPECT_FALSE(r.second);
+    EXPECT_EQ(r.first, prev(m.end()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*r.first, 3);
+  }
+}
+
+// class flat_set
+
+// pair<iterator, bool> insert(value_type&& v);
+
+TEST(FlatSet, InsertRV) {
+  {
+    typedef base::flat_set<MoveOnly> M;
+    typedef std::pair<M::iterator, bool> R;
+    M m;
+    R r = m.insert(M::value_type(2));
+    EXPECT_TRUE(r.second);
+    EXPECT_EQ(r.first, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    EXPECT_EQ(*r.first, 2);
+
+    r = m.insert(M::value_type(1));
+    EXPECT_TRUE(r.second);
+    EXPECT_EQ(r.first, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(*r.first, 1);
+
+    r = m.insert(M::value_type(3));
+    EXPECT_TRUE(r.second);
+    EXPECT_EQ(r.first, prev(m.end()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*r.first, 3);
+
+    r = m.insert(M::value_type(3));
+    EXPECT_FALSE(r.second);
+    EXPECT_EQ(r.first, prev(m.end()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*r.first, static_cast<M::size_type>(3));
+  }
+}
+
+// class flat_set
+
+// iterator insert(const_iterator position, const value_type& v);
+
+TEST(FlatSet, InsertIterCV) {
+  {
+    typedef base::flat_set<int> M;
+    typedef M::iterator R;
+    M m;
+    R r = m.insert(m.cend(), M::value_type(2));
+    EXPECT_EQ(r, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    EXPECT_EQ(*r, 2);
+
+    r = m.insert(m.cend(), M::value_type(1));
+    EXPECT_EQ(r, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(*r, 1);
+
+    r = m.insert(m.cend(), M::value_type(3));
+    EXPECT_EQ(r, prev(m.end()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*r, 3);
+
+    r = m.insert(m.cend(), M::value_type(3));
+    EXPECT_EQ(r, prev(m.end()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*r, 3);
+  }
+}
+
+// class flat_set
+
+// iterator insert(const_iterator position, value_type&& v);
+
+TEST(FlatSet, InsertIterRV) {
+  {
+    typedef base::flat_set<MoveOnly> M;
+    typedef M::iterator R;
+    M m;
+    R r = m.insert(m.cend(), M::value_type(2));
+    EXPECT_EQ(r, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    EXPECT_EQ(*r, 2);
+
+    r = m.insert(m.cend(), M::value_type(1));
+    EXPECT_EQ(r, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(*r, 1);
+
+    r = m.insert(m.cend(), M::value_type(3));
+    EXPECT_EQ(r, prev(m.end()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*r, 3);
+
+    r = m.insert(m.cend(), M::value_type(3));
+    EXPECT_EQ(r, prev(m.end()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*r, 3);
+  }
+}
+
+// class flat_set
+
+// template <class InputIterator>
+//   void insert(InputIterator first, InputIterator last);
+
+TEST(FlatSet, InsertRange) {

[dyaroshev, 2016/12/15 16:10:59]

Add tests for stability.

[dyaroshev, 2016/12/18 22:27:23]

Done.

+  {
+    typedef base::flat_set<int> M;
+    typedef int V;
+
+    V ar[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
+
+    M m;
+    m.insert(input_iterator<const V*>(ar),
+             input_iterator<const V*>(ar + sizeof(ar) / sizeof(ar[0])));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(*m.begin(), 1);
+    EXPECT_EQ(*next(m.begin()), 2);
+    EXPECT_EQ(*next(m.begin(), 2), 3);
+  }
+}
+
+// class flat_set
+
+// void insert(initializer_list<value_type> il);
+
+TEST(FlatSet, InsertInitializerList) {
+  {
+    typedef base::flat_set<int> M;
+    typedef M::value_type V;
+    M m = {10, 8};
+    m.insert({1, 2, 3, 4, 5, 6});
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(8));
+    EXPECT_EQ(distance(m.begin(), m.end()),
+              static_cast<M::difference_type>(m.size()));
+    M::const_iterator i = m.cbegin();
+    EXPECT_EQ(*i, V(1));
+    EXPECT_EQ(*++i, V(2));
+    EXPECT_EQ(*++i, V(3));
+    EXPECT_EQ(*++i, V(4));
+    EXPECT_EQ(*++i, V(5));
+    EXPECT_EQ(*++i, V(6));
+    EXPECT_EQ(*++i, V(8));
+    EXPECT_EQ(*++i, V(10));
+  }
+}
+
+// class flat_set
+
+// template <class... Args>
+//   pair<iterator, bool> emplace(Args&&... args);
+
+TEST(FlatSet, Emplace) {
+  {
+    typedef base::flat_set<Emplaceable> M;
+    typedef std::pair<M::iterator, bool> R;
+    M m;
+    R r = m.emplace();
+    EXPECT_TRUE(r.second);
+    EXPECT_EQ(r.first, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    EXPECT_EQ(*m.begin(), Emplaceable());
+    r = m.emplace(2, 3.5);
+    EXPECT_TRUE(r.second);
+    EXPECT_EQ(r.first, next(m.begin()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(*r.first, Emplaceable(2, 3.5));
+    r = m.emplace(2, 3.5);
+    EXPECT_TRUE(!r.second);

[Peter Kasting, 2016/12/16 08:09:08]

Nit: EXPECT_FALSE(r.second)

[dyaroshev, 2016/12/18 22:27:24]

Done.

+    EXPECT_EQ(r.first, next(m.begin()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(*r.first, Emplaceable(2, 3.5));
+  }
+  {
+    typedef base::flat_set<int> M;
+    typedef std::pair<M::iterator, bool> R;
+    M m;
+    R r = m.emplace(M::value_type(2));
+    EXPECT_TRUE(r.second);
+    EXPECT_EQ(r.first, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    EXPECT_EQ(*r.first, 2);
+  }
+}
+
+// class flat_set
+
+// template <class... Args>
+//   iterator emplace_hint(const_iterator position, Args&&... args);
+
+TEST(FlatSet, EmplaceHint) {
+  {
+    typedef base::flat_set<Emplaceable> M;
+    typedef M::iterator R;
+    M m;
+    R r = m.emplace_hint(m.cend());
+    EXPECT_EQ(r, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    EXPECT_EQ(*m.begin(), Emplaceable());
+    r = m.emplace_hint(m.cend(), 2, 3.5);
+    EXPECT_EQ(r, next(m.begin()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(*r, Emplaceable(2, 3.5));
+    r = m.emplace_hint(m.cbegin(), 2, 3.5);
+    EXPECT_EQ(r, next(m.begin()));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(*r, Emplaceable(2, 3.5));
+  }
+  {
+    typedef base::flat_set<int> M;
+    typedef M::iterator R;
+    M m;
+    R r = m.emplace_hint(m.cend(), M::value_type(2));
+    EXPECT_EQ(r, m.begin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    EXPECT_EQ(*r, 2);
+  }
+}
+
+// class flat_set
+
+// iterator erase(const_iterator position);
+
+TEST(FlatSet, EraseCIter) {
+  {
+    typedef base::flat_set<int> M;
+    typedef int V;
+    typedef M::iterator I;
+
+    V ar[] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+    M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(8));
+    I i = m.erase(next(m.cbegin(), 3));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(7));
+    EXPECT_EQ(i, next(m.begin(), 3));
+    EXPECT_EQ(*next(m.begin(), 0), 1);
+    EXPECT_EQ(*next(m.begin(), 1), 2);
+    EXPECT_EQ(*next(m.begin(), 2), 3);
+    EXPECT_EQ(*next(m.begin(), 3), 5);
+    EXPECT_EQ(*next(m.begin(), 4), 6);
+    EXPECT_EQ(*next(m.begin(), 5), 7);
+    EXPECT_EQ(*next(m.begin(), 6), 8);
+
+    i = m.erase(next(m.cbegin(), 0));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(6));
+    EXPECT_EQ(i, m.begin());
+    EXPECT_EQ(*next(m.begin(), 0), 2);
+    EXPECT_EQ(*next(m.begin(), 1), 3);
+    EXPECT_EQ(*next(m.begin(), 2), 5);
+    EXPECT_EQ(*next(m.begin(), 3), 6);
+    EXPECT_EQ(*next(m.begin(), 4), 7);
+    EXPECT_EQ(*next(m.begin(), 5), 8);
+
+    i = m.erase(next(m.cbegin(), 5));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(5));
+    EXPECT_EQ(i, m.end());
+    EXPECT_EQ(*next(m.begin(), 0), 2);
+    EXPECT_EQ(*next(m.begin(), 1), 3);
+    EXPECT_EQ(*next(m.begin(), 2), 5);
+    EXPECT_EQ(*next(m.begin(), 3), 6);
+    EXPECT_EQ(*next(m.begin(), 4), 7);
+
+    i = m.erase(next(m.cbegin(), 1));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(4));
+    EXPECT_EQ(i, next(m.begin()));
+    EXPECT_EQ(*next(m.begin(), 0), 2);
+    EXPECT_EQ(*next(m.begin(), 1), 5);
+    EXPECT_EQ(*next(m.begin(), 2), 6);
+    EXPECT_EQ(*next(m.begin(), 3), 7);
+
+    i = m.erase(next(m.cbegin(), 2));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(i, next(m.begin(), 2));
+    EXPECT_EQ(*next(m.begin(), 0), 2);
+    EXPECT_EQ(*next(m.begin(), 1), 5);
+    EXPECT_EQ(*next(m.begin(), 2), 7);
+
+    i = m.erase(next(m.cbegin(), 2));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(i, next(m.begin(), 2));
+    EXPECT_EQ(*next(m.begin(), 0), 2);
+    EXPECT_EQ(*next(m.begin(), 1), 5);
+
+    i = m.erase(next(m.cbegin(), 0));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    EXPECT_EQ(i, next(m.begin(), 0));
+    EXPECT_EQ(*next(m.begin(), 0), 5);
+
+    i = m.erase(m.cbegin());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(0));
+    EXPECT_EQ(i, m.begin());
+    EXPECT_EQ(i, m.end());
+  }
+}
+
+// class flat_set
+
+// iterator erase(const_iterator first, const_iterator last);
+
+TEST(FlatSet, EraseCIterCIter) {
+  {
+    typedef base::flat_set<int> M;
+    typedef int V;
+    typedef M::iterator I;
+
+    V ar[] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+    M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(8));
+    I i = m.erase(next(m.cbegin(), 5), next(m.cbegin(), 5));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(8));
+    EXPECT_EQ(i, next(m.begin(), 5));
+    EXPECT_EQ(*next(m.begin(), 0), 1);
+    EXPECT_EQ(*next(m.begin(), 1), 2);
+    EXPECT_EQ(*next(m.begin(), 2), 3);
+    EXPECT_EQ(*next(m.begin(), 3), 4);
+    EXPECT_EQ(*next(m.begin(), 4), 5);
+    EXPECT_EQ(*next(m.begin(), 5), 6);
+    EXPECT_EQ(*next(m.begin(), 6), 7);
+    EXPECT_EQ(*next(m.begin(), 7), 8);
+
+    i = m.erase(next(m.cbegin(), 3), next(m.cbegin(), 4));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(7));
+    EXPECT_EQ(i, next(m.begin(), 3));
+    EXPECT_EQ(*next(m.begin(), 0), 1);
+    EXPECT_EQ(*next(m.begin(), 1), 2);
+    EXPECT_EQ(*next(m.begin(), 2), 3);
+    EXPECT_EQ(*next(m.begin(), 3), 5);
+    EXPECT_EQ(*next(m.begin(), 4), 6);
+    EXPECT_EQ(*next(m.begin(), 5), 7);
+    EXPECT_EQ(*next(m.begin(), 6), 8);
+
+    i = m.erase(next(m.cbegin(), 2), next(m.cbegin(), 5));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(4));
+    EXPECT_EQ(i, next(m.begin(), 2));
+    EXPECT_EQ(*next(m.begin(), 0), 1);
+    EXPECT_EQ(*next(m.begin(), 1), 2);
+    EXPECT_EQ(*next(m.begin(), 2), 7);
+    EXPECT_EQ(*next(m.begin(), 3), 8);
+
+    i = m.erase(next(m.cbegin(), 0), next(m.cbegin(), 2));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(i, next(m.begin(), 0));
+    EXPECT_EQ(*next(m.begin(), 0), 7);
+    EXPECT_EQ(*next(m.begin(), 1), 8);
+
+    i = m.erase(m.cbegin(), m.cend());
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(0));
+    EXPECT_EQ(i, m.end());
+  }
+}
+
+// class set
+
+// size_type erase(const key_type& k);
+
+TEST(FlatSet, EraseKey) {
+  {
+    typedef base::flat_set<int> M;
+    typedef int V;
+    typedef M::size_type I;
+
+    V ar[] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+    M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(8));
+    I i = m.erase(9);
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(8));
+    EXPECT_EQ(i, static_cast<M::size_type>(0));
+    EXPECT_EQ(*next(m.begin(), 0), 1);
+    EXPECT_EQ(*next(m.begin(), 1), 2);
+    EXPECT_EQ(*next(m.begin(), 2), 3);
+    EXPECT_EQ(*next(m.begin(), 3), 4);
+    EXPECT_EQ(*next(m.begin(), 4), 5);
+    EXPECT_EQ(*next(m.begin(), 5), 6);
+    EXPECT_EQ(*next(m.begin(), 6), 7);
+    EXPECT_EQ(*next(m.begin(), 7), 8);
+
+    i = m.erase(4);
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(7));
+    EXPECT_EQ(i, static_cast<M::size_type>(1));
+    EXPECT_EQ(*next(m.begin(), 0), 1);
+    EXPECT_EQ(*next(m.begin(), 1), 2);
+    EXPECT_EQ(*next(m.begin(), 2), 3);
+    EXPECT_EQ(*next(m.begin(), 3), 5);
+    EXPECT_EQ(*next(m.begin(), 4), 6);
+    EXPECT_EQ(*next(m.begin(), 5), 7);
+    EXPECT_EQ(*next(m.begin(), 6), 8);
+
+    i = m.erase(1);
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(6));
+    EXPECT_EQ(i, static_cast<M::size_type>(1));
+    EXPECT_EQ(*next(m.begin(), 0), 2);
+    EXPECT_EQ(*next(m.begin(), 1), 3);
+    EXPECT_EQ(*next(m.begin(), 2), 5);
+    EXPECT_EQ(*next(m.begin(), 3), 6);
+    EXPECT_EQ(*next(m.begin(), 4), 7);
+    EXPECT_EQ(*next(m.begin(), 5), 8);
+
+    i = m.erase(8);
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(5));
+    EXPECT_EQ(i, static_cast<M::size_type>(1));
+    EXPECT_EQ(*next(m.begin(), 0), 2);
+    EXPECT_EQ(*next(m.begin(), 1), 3);
+    EXPECT_EQ(*next(m.begin(), 2), 5);
+    EXPECT_EQ(*next(m.begin(), 3), 6);
+    EXPECT_EQ(*next(m.begin(), 4), 7);
+
+    i = m.erase(3);
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(4));
+    EXPECT_EQ(i, static_cast<M::size_type>(1));
+    EXPECT_EQ(*next(m.begin(), 0), 2);
+    EXPECT_EQ(*next(m.begin(), 1), 5);
+    EXPECT_EQ(*next(m.begin(), 2), 6);
+    EXPECT_EQ(*next(m.begin(), 3), 7);
+
+    i = m.erase(6);
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(3));
+    EXPECT_EQ(i, static_cast<M::size_type>(1));
+    EXPECT_EQ(*next(m.begin(), 0), 2);
+    EXPECT_EQ(*next(m.begin(), 1), 5);
+    EXPECT_EQ(*next(m.begin(), 2), 7);
+
+    i = m.erase(7);
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(2));
+    EXPECT_EQ(i, static_cast<M::size_type>(1));
+    EXPECT_EQ(*next(m.begin(), 0), 2);
+    EXPECT_EQ(*next(m.begin(), 1), 5);
+
+    i = m.erase(2);
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(1));
+    EXPECT_EQ(i, static_cast<M::size_type>(1));
+    EXPECT_EQ(*next(m.begin(), 0), 5);
+
+    i = m.erase(5);
+    EXPECT_EQ(m.size(), static_cast<M::size_type>(0));
+    EXPECT_EQ(i, static_cast<M::size_type>(1));
+  }
+}
+
+// ----------------------------------------------------------------------------
+// Comparators.

[dyaroshev, 2016/12/15 16:10:59]

Add test that flat_set is sorted with provided comparator.

[dyaroshev, 2016/12/18 22:27:24]

Done.

+
+// ----------------------------------------------------------------------------
+// Binary search operations.
+
+// class flat_set
+
+// size_type count(const key_type& k) const;
+
+TEST(FlatSet, Count) {
+  {
+    typedef int V;
+    typedef base::flat_set<int> M;
+    typedef M::size_type R;
+
+    V ar[] = {5, 6, 7, 8, 9, 10, 11, 12};
+
+    const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    R r = m.count(5);

[Peter Kasting, 2016/12/16 08:09:07]

Nit: Avoid unneeded temps, e.g.

  EXPECT_EQ(1U, m.count(5));
  EXPECT_EQ(1U, m.count(6));
  ...

[dyaroshev, 2016/12/18 22:27:25]

Done, where seemed appropriate.

+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(6);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(7);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(8);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(9);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(10);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(11);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(12);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(4);
+    EXPECT_EQ(r, static_cast<M::size_type>(0));
+  }
+  {
+    typedef int V;
+    typedef base::flat_set<int, std::less<V>> M;
+    typedef M::size_type R;
+
+    V ar[] = {5, 6, 7, 8, 9, 10, 11, 12};
+
+    const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    R r = m.count(5);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(6);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(7);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(8);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(9);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(10);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(11);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(12);
+    EXPECT_EQ(r, static_cast<M::size_type>(1));
+    r = m.count(4);
+    EXPECT_EQ(r, static_cast<M::size_type>(0));
+  }
+}
+
+// class set
+
+//       iterator find(const key_type& k);
+// const_iterator find(const key_type& k) const;
+
+TEST(FlatSet, Find) {
+  {
+    typedef int V;
+    typedef base::flat_set<V> M;
+    {
+      typedef M::iterator R;
+
+      V ar[] = {5, 6, 7, 8, 9, 10, 11, 12};
+
+      M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+      R r = m.find(5);
+      EXPECT_EQ(r, m.begin());
+      r = m.find(6);
+      EXPECT_EQ(r, next(m.begin()));
+      r = m.find(7);
+      EXPECT_EQ(r, next(m.begin(), 2));
+      r = m.find(8);
+      EXPECT_EQ(r, next(m.begin(), 3));
+      r = m.find(9);
+      EXPECT_EQ(r, next(m.begin(), 4));
+      r = m.find(10);
+      EXPECT_EQ(r, next(m.begin(), 5));
+      r = m.find(11);
+      EXPECT_EQ(r, next(m.begin(), 6));
+      r = m.find(12);
+      EXPECT_EQ(r, next(m.begin(), 7));
+      r = m.find(4);
+      EXPECT_EQ(r, next(m.begin(), 8));
+    }
+    {
+      typedef M::const_iterator R;
+
+      V ar[] = {5, 6, 7, 8, 9, 10, 11, 12};
+
+      const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+      R r = m.find(5);
+      EXPECT_EQ(r, m.begin());
+      r = m.find(6);
+      EXPECT_EQ(r, next(m.begin()));
+      r = m.find(7);
+      EXPECT_EQ(r, next(m.begin(), 2));
+      r = m.find(8);
+      EXPECT_EQ(r, next(m.begin(), 3));
+      r = m.find(9);
+      EXPECT_EQ(r, next(m.begin(), 4));
+      r = m.find(10);
+      EXPECT_EQ(r, next(m.begin(), 5));
+      r = m.find(11);
+      EXPECT_EQ(r, next(m.begin(), 6));
+      r = m.find(12);
+      EXPECT_EQ(r, next(m.begin(), 7));
+      r = m.find(4);
+      EXPECT_EQ(r, next(m.begin(), 8));
+    }
+  }
+  {
+    typedef int V;
+    typedef base::flat_set<V, std::less<V>> M;
+    typedef M::iterator R;
+
+    V ar[] = {5, 6, 7, 8, 9, 10, 11, 12};
+
+    M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    R r = m.find(5);
+    EXPECT_EQ(r, m.begin());
+    r = m.find(6);
+    EXPECT_EQ(r, next(m.begin()));
+    r = m.find(7);
+    EXPECT_EQ(r, next(m.begin(), 2));
+    r = m.find(8);
+    EXPECT_EQ(r, next(m.begin(), 3));
+    r = m.find(9);
+    EXPECT_EQ(r, next(m.begin(), 4));
+    r = m.find(10);
+    EXPECT_EQ(r, next(m.begin(), 5));
+    r = m.find(11);
+    EXPECT_EQ(r, next(m.begin(), 6));
+    r = m.find(12);
+    EXPECT_EQ(r, next(m.begin(), 7));
+    r = m.find(4);
+    EXPECT_EQ(r, next(m.begin(), 8));
+  }
+}
+
+// class flat_set
+
+// pair<iterator,iterator>             equal_range(const key_type& k);
+// pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
+
+TEST(FlatSet, EqualRange) {
+  {
+    typedef int V;
+    typedef base::flat_set<int> M;
+    {
+      typedef std::pair<M::iterator, M::iterator> R;
+
+      V ar[] = {5, 7, 9, 11, 13, 15, 17, 19};
+
+      M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+      R r = m.equal_range(5);
+      EXPECT_EQ(r.first, next(m.begin(), 0));
+      EXPECT_EQ(r.second, next(m.begin(), 1));
+      r = m.equal_range(7);
+      EXPECT_EQ(r.first, next(m.begin(), 1));
+      EXPECT_EQ(r.second, next(m.begin(), 2));
+      r = m.equal_range(9);
+      EXPECT_EQ(r.first, next(m.begin(), 2));
+      EXPECT_EQ(r.second, next(m.begin(), 3));
+      r = m.equal_range(11);
+      EXPECT_EQ(r.first, next(m.begin(), 3));
+      EXPECT_EQ(r.second, next(m.begin(), 4));
+      r = m.equal_range(13);
+      EXPECT_EQ(r.first, next(m.begin(), 4));
+      EXPECT_EQ(r.second, next(m.begin(), 5));
+      r = m.equal_range(15);
+      EXPECT_EQ(r.first, next(m.begin(), 5));
+      EXPECT_EQ(r.second, next(m.begin(), 6));
+      r = m.equal_range(17);
+      EXPECT_EQ(r.first, next(m.begin(), 6));
+      EXPECT_EQ(r.second, next(m.begin(), 7));
+      r = m.equal_range(19);
+      EXPECT_EQ(r.first, next(m.begin(), 7));
+      EXPECT_EQ(r.second, next(m.begin(), 8));
+      r = m.equal_range(4);
+      EXPECT_EQ(r.first, next(m.begin(), 0));
+      EXPECT_EQ(r.second, next(m.begin(), 0));
+      r = m.equal_range(6);
+      EXPECT_EQ(r.first, next(m.begin(), 1));
+      EXPECT_EQ(r.second, next(m.begin(), 1));
+      r = m.equal_range(8);
+      EXPECT_EQ(r.first, next(m.begin(), 2));
+      EXPECT_EQ(r.second, next(m.begin(), 2));
+      r = m.equal_range(10);
+      EXPECT_EQ(r.first, next(m.begin(), 3));
+      EXPECT_EQ(r.second, next(m.begin(), 3));
+      r = m.equal_range(12);
+      EXPECT_EQ(r.first, next(m.begin(), 4));
+      EXPECT_EQ(r.second, next(m.begin(), 4));
+      r = m.equal_range(14);
+      EXPECT_EQ(r.first, next(m.begin(), 5));
+      EXPECT_EQ(r.second, next(m.begin(), 5));
+      r = m.equal_range(16);
+      EXPECT_EQ(r.first, next(m.begin(), 6));
+      EXPECT_EQ(r.second, next(m.begin(), 6));
+      r = m.equal_range(18);
+      EXPECT_EQ(r.first, next(m.begin(), 7));
+      EXPECT_EQ(r.second, next(m.begin(), 7));
+      r = m.equal_range(20);
+      EXPECT_EQ(r.first, next(m.begin(), 8));
+      EXPECT_EQ(r.second, next(m.begin(), 8));
+    }
+    {
+      typedef std::pair<M::const_iterator, M::const_iterator> R;
+
+      V ar[] = {5, 7, 9, 11, 13, 15, 17, 19};
+
+      const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+      R r = m.equal_range(5);
+      EXPECT_EQ(r.first, next(m.begin(), 0));
+      EXPECT_EQ(r.second, next(m.begin(), 1));
+      r = m.equal_range(7);
+      EXPECT_EQ(r.first, next(m.begin(), 1));
+      EXPECT_EQ(r.second, next(m.begin(), 2));
+      r = m.equal_range(9);
+      EXPECT_EQ(r.first, next(m.begin(), 2));
+      EXPECT_EQ(r.second, next(m.begin(), 3));
+      r = m.equal_range(11);
+      EXPECT_EQ(r.first, next(m.begin(), 3));
+      EXPECT_EQ(r.second, next(m.begin(), 4));
+      r = m.equal_range(13);
+      EXPECT_EQ(r.first, next(m.begin(), 4));
+      EXPECT_EQ(r.second, next(m.begin(), 5));
+      r = m.equal_range(15);
+      EXPECT_EQ(r.first, next(m.begin(), 5));
+      EXPECT_EQ(r.second, next(m.begin(), 6));
+      r = m.equal_range(17);
+      EXPECT_EQ(r.first, next(m.begin(), 6));
+      EXPECT_EQ(r.second, next(m.begin(), 7));
+      r = m.equal_range(19);
+      EXPECT_EQ(r.first, next(m.begin(), 7));
+      EXPECT_EQ(r.second, next(m.begin(), 8));
+      r = m.equal_range(4);
+      EXPECT_EQ(r.first, next(m.begin(), 0));
+      EXPECT_EQ(r.second, next(m.begin(), 0));
+      r = m.equal_range(6);
+      EXPECT_EQ(r.first, next(m.begin(), 1));
+      EXPECT_EQ(r.second, next(m.begin(), 1));
+      r = m.equal_range(8);
+      EXPECT_EQ(r.first, next(m.begin(), 2));
+      EXPECT_EQ(r.second, next(m.begin(), 2));
+      r = m.equal_range(10);
+      EXPECT_EQ(r.first, next(m.begin(), 3));
+      EXPECT_EQ(r.second, next(m.begin(), 3));
+      r = m.equal_range(12);
+      EXPECT_EQ(r.first, next(m.begin(), 4));
+      EXPECT_EQ(r.second, next(m.begin(), 4));
+      r = m.equal_range(14);
+      EXPECT_EQ(r.first, next(m.begin(), 5));
+      EXPECT_EQ(r.second, next(m.begin(), 5));
+      r = m.equal_range(16);
+      EXPECT_EQ(r.first, next(m.begin(), 6));
+      EXPECT_EQ(r.second, next(m.begin(), 6));
+      r = m.equal_range(18);
+      EXPECT_EQ(r.first, next(m.begin(), 7));
+      EXPECT_EQ(r.second, next(m.begin(), 7));
+      r = m.equal_range(20);
+      EXPECT_EQ(r.first, next(m.begin(), 8));
+      EXPECT_EQ(r.second, next(m.begin(), 8));
+    }
+  }
+
+  {
+    typedef int V;
+    typedef base::flat_set<V, std::less<V>> M;
+    {
+      typedef std::pair<M::iterator, M::iterator> R;
+
+      V ar[] = {5, 7, 9, 11, 13, 15, 17, 19};
+
+      M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+      R r = m.equal_range(5);
+      EXPECT_EQ(r.first, next(m.begin(), 0));
+      EXPECT_EQ(r.second, next(m.begin(), 1));
+      r = m.equal_range(7);
+      EXPECT_EQ(r.first, next(m.begin(), 1));
+      EXPECT_EQ(r.second, next(m.begin(), 2));
+      r = m.equal_range(9);
+      EXPECT_EQ(r.first, next(m.begin(), 2));
+      EXPECT_EQ(r.second, next(m.begin(), 3));
+      r = m.equal_range(11);
+      EXPECT_EQ(r.first, next(m.begin(), 3));
+      EXPECT_EQ(r.second, next(m.begin(), 4));
+      r = m.equal_range(13);
+      EXPECT_EQ(r.first, next(m.begin(), 4));
+      EXPECT_EQ(r.second, next(m.begin(), 5));
+      r = m.equal_range(15);
+      EXPECT_EQ(r.first, next(m.begin(), 5));
+      EXPECT_EQ(r.second, next(m.begin(), 6));
+      r = m.equal_range(17);
+      EXPECT_EQ(r.first, next(m.begin(), 6));
+      EXPECT_EQ(r.second, next(m.begin(), 7));
+      r = m.equal_range(19);
+      EXPECT_EQ(r.first, next(m.begin(), 7));
+      EXPECT_EQ(r.second, next(m.begin(), 8));
+      r = m.equal_range(4);
+      EXPECT_EQ(r.first, next(m.begin(), 0));
+      EXPECT_EQ(r.second, next(m.begin(), 0));
+      r = m.equal_range(6);
+      EXPECT_EQ(r.first, next(m.begin(), 1));
+      EXPECT_EQ(r.second, next(m.begin(), 1));
+      r = m.equal_range(8);
+      EXPECT_EQ(r.first, next(m.begin(), 2));
+      EXPECT_EQ(r.second, next(m.begin(), 2));
+      r = m.equal_range(10);
+      EXPECT_EQ(r.first, next(m.begin(), 3));
+      EXPECT_EQ(r.second, next(m.begin(), 3));
+      r = m.equal_range(12);
+      EXPECT_EQ(r.first, next(m.begin(), 4));
+      EXPECT_EQ(r.second, next(m.begin(), 4));
+      r = m.equal_range(14);
+      EXPECT_EQ(r.first, next(m.begin(), 5));
+      EXPECT_EQ(r.second, next(m.begin(), 5));
+      r = m.equal_range(16);
+      EXPECT_EQ(r.first, next(m.begin(), 6));
+      EXPECT_EQ(r.second, next(m.begin(), 6));
+      r = m.equal_range(18);
+      EXPECT_EQ(r.first, next(m.begin(), 7));
+      EXPECT_EQ(r.second, next(m.begin(), 7));
+      r = m.equal_range(20);
+      EXPECT_EQ(r.first, next(m.begin(), 8));
+      EXPECT_EQ(r.second, next(m.begin(), 8));
+    }
+  }
+}
+
+// class flat_set
+
+//       iterator lower_bound(const key_type& k);
+// const_iterator lower_bound(const key_type& k) const;
+
+TEST(FlatSet, LowerBound) {
+  {
+    typedef int V;
+    typedef base::flat_set<int> M;
+    {
+      typedef M::iterator R;
+
+      V ar[] = {5, 7, 9, 11, 13, 15, 17, 19};
+
+      M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+      R r = m.lower_bound(5);
+      EXPECT_EQ(r, m.begin());
+      r = m.lower_bound(7);
+      EXPECT_EQ(r, next(m.begin()));
+      r = m.lower_bound(9);
+      EXPECT_EQ(r, next(m.begin(), 2));
+      r = m.lower_bound(11);
+      EXPECT_EQ(r, next(m.begin(), 3));
+      r = m.lower_bound(13);
+      EXPECT_EQ(r, next(m.begin(), 4));
+      r = m.lower_bound(15);
+      EXPECT_EQ(r, next(m.begin(), 5));
+      r = m.lower_bound(17);
+      EXPECT_EQ(r, next(m.begin(), 6));
+      r = m.lower_bound(19);
+      EXPECT_EQ(r, next(m.begin(), 7));
+      r = m.lower_bound(4);
+      EXPECT_EQ(r, next(m.begin(), 0));
+      r = m.lower_bound(6);
+      EXPECT_EQ(r, next(m.begin(), 1));
+      r = m.lower_bound(8);
+      EXPECT_EQ(r, next(m.begin(), 2));
+      r = m.lower_bound(10);
+      EXPECT_EQ(r, next(m.begin(), 3));
+      r = m.lower_bound(12);
+      EXPECT_EQ(r, next(m.begin(), 4));
+      r = m.lower_bound(14);
+      EXPECT_EQ(r, next(m.begin(), 5));
+      r = m.lower_bound(16);
+      EXPECT_EQ(r, next(m.begin(), 6));
+      r = m.lower_bound(18);
+      EXPECT_EQ(r, next(m.begin(), 7));
+      r = m.lower_bound(20);
+      EXPECT_EQ(r, next(m.begin(), 8));
+    }
+    {
+      typedef M::const_iterator R;
+
+      V ar[] = {5, 7, 9, 11, 13, 15, 17, 19};
+
+      const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+      R r = m.lower_bound(5);
+      EXPECT_EQ(r, m.begin());
+      r = m.lower_bound(7);
+      EXPECT_EQ(r, next(m.begin()));
+      r = m.lower_bound(9);
+      EXPECT_EQ(r, next(m.begin(), 2));
+      r = m.lower_bound(11);
+      EXPECT_EQ(r, next(m.begin(), 3));
+      r = m.lower_bound(13);
+      EXPECT_EQ(r, next(m.begin(), 4));
+      r = m.lower_bound(15);
+      EXPECT_EQ(r, next(m.begin(), 5));
+      r = m.lower_bound(17);
+      EXPECT_EQ(r, next(m.begin(), 6));
+      r = m.lower_bound(19);
+      EXPECT_EQ(r, next(m.begin(), 7));
+      r = m.lower_bound(4);
+      EXPECT_EQ(r, next(m.begin(), 0));
+      r = m.lower_bound(6);
+      EXPECT_EQ(r, next(m.begin(), 1));
+      r = m.lower_bound(8);
+      EXPECT_EQ(r, next(m.begin(), 2));
+      r = m.lower_bound(10);
+      EXPECT_EQ(r, next(m.begin(), 3));
+      r = m.lower_bound(12);
+      EXPECT_EQ(r, next(m.begin(), 4));
+      r = m.lower_bound(14);
+      EXPECT_EQ(r, next(m.begin(), 5));
+      r = m.lower_bound(16);
+      EXPECT_EQ(r, next(m.begin(), 6));
+      r = m.lower_bound(18);
+      EXPECT_EQ(r, next(m.begin(), 7));
+      r = m.lower_bound(20);
+      EXPECT_EQ(r, next(m.begin(), 8));
+    }
+  }
+  {
+    typedef int V;
+    typedef base::flat_set<V, std::less<V>> M;
+    typedef M::iterator R;
+
+    V ar[] = {5, 7, 9, 11, 13, 15, 17, 19};
+
+    M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    R r = m.lower_bound(5);
+    EXPECT_EQ(r, m.begin());
+    r = m.lower_bound(7);
+    EXPECT_EQ(r, next(m.begin()));
+    r = m.lower_bound(9);
+    EXPECT_EQ(r, next(m.begin(), 2));
+    r = m.lower_bound(11);
+    EXPECT_EQ(r, next(m.begin(), 3));
+    r = m.lower_bound(13);
+    EXPECT_EQ(r, next(m.begin(), 4));
+    r = m.lower_bound(15);
+    EXPECT_EQ(r, next(m.begin(), 5));
+    r = m.lower_bound(17);
+    EXPECT_EQ(r, next(m.begin(), 6));
+    r = m.lower_bound(19);
+    EXPECT_EQ(r, next(m.begin(), 7));
+    r = m.lower_bound(4);
+    EXPECT_EQ(r, next(m.begin(), 0));
+    r = m.lower_bound(6);
+    EXPECT_EQ(r, next(m.begin(), 1));
+    r = m.lower_bound(8);
+    EXPECT_EQ(r, next(m.begin(), 2));
+    r = m.lower_bound(10);
+    EXPECT_EQ(r, next(m.begin(), 3));
+    r = m.lower_bound(12);
+    EXPECT_EQ(r, next(m.begin(), 4));
+    r = m.lower_bound(14);
+    EXPECT_EQ(r, next(m.begin(), 5));
+    r = m.lower_bound(16);
+    EXPECT_EQ(r, next(m.begin(), 6));
+    r = m.lower_bound(18);
+    EXPECT_EQ(r, next(m.begin(), 7));
+    r = m.lower_bound(20);
+    EXPECT_EQ(r, next(m.begin(), 8));
+  }
+}
+
+// class flat_set
+
+//       iterator upper_bound(const key_type& k);
+// const_iterator upper_bound(const key_type& k) const;
+
+TEST(FlatSet, UpperBound) {
+  {
+    typedef int V;
+    typedef base::flat_set<int> M;
+    {
+      typedef M::iterator R;
+
+      V ar[] = {5, 7, 9, 11, 13, 15, 17, 19};
+
+      M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+      R r = m.upper_bound(5);
+      EXPECT_EQ(r, next(m.begin(), 1));
+      r = m.upper_bound(7);
+      EXPECT_EQ(r, next(m.begin(), 2));
+      r = m.upper_bound(9);
+      EXPECT_EQ(r, next(m.begin(), 3));
+      r = m.upper_bound(11);
+      EXPECT_EQ(r, next(m.begin(), 4));
+      r = m.upper_bound(13);
+      EXPECT_EQ(r, next(m.begin(), 5));
+      r = m.upper_bound(15);
+      EXPECT_EQ(r, next(m.begin(), 6));
+      r = m.upper_bound(17);
+      EXPECT_EQ(r, next(m.begin(), 7));
+      r = m.upper_bound(19);
+      EXPECT_EQ(r, next(m.begin(), 8));
+      r = m.upper_bound(4);
+      EXPECT_EQ(r, next(m.begin(), 0));
+      r = m.upper_bound(6);
+      EXPECT_EQ(r, next(m.begin(), 1));
+      r = m.upper_bound(8);
+      EXPECT_EQ(r, next(m.begin(), 2));
+      r = m.upper_bound(10);
+      EXPECT_EQ(r, next(m.begin(), 3));
+      r = m.upper_bound(12);
+      EXPECT_EQ(r, next(m.begin(), 4));
+      r = m.upper_bound(14);
+      EXPECT_EQ(r, next(m.begin(), 5));
+      r = m.upper_bound(16);
+      EXPECT_EQ(r, next(m.begin(), 6));
+      r = m.upper_bound(18);
+      EXPECT_EQ(r, next(m.begin(), 7));
+      r = m.upper_bound(20);
+      EXPECT_EQ(r, next(m.begin(), 8));
+    }
+    {
+      typedef M::const_iterator R;
+
+      V ar[] = {5, 7, 9, 11, 13, 15, 17, 19};
+
+      const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+      R r = m.upper_bound(5);
+      EXPECT_EQ(r, next(m.begin(), 1));
+      r = m.upper_bound(7);
+      EXPECT_EQ(r, next(m.begin(), 2));
+      r = m.upper_bound(9);
+      EXPECT_EQ(r, next(m.begin(), 3));
+      r = m.upper_bound(11);
+      EXPECT_EQ(r, next(m.begin(), 4));
+      r = m.upper_bound(13);
+      EXPECT_EQ(r, next(m.begin(), 5));
+      r = m.upper_bound(15);
+      EXPECT_EQ(r, next(m.begin(), 6));
+      r = m.upper_bound(17);
+      EXPECT_EQ(r, next(m.begin(), 7));
+      r = m.upper_bound(19);
+      EXPECT_EQ(r, next(m.begin(), 8));
+      r = m.upper_bound(4);
+      EXPECT_EQ(r, next(m.begin(), 0));
+      r = m.upper_bound(6);
+      EXPECT_EQ(r, next(m.begin(), 1));
+      r = m.upper_bound(8);
+      EXPECT_EQ(r, next(m.begin(), 2));
+      r = m.upper_bound(10);
+      EXPECT_EQ(r, next(m.begin(), 3));
+      r = m.upper_bound(12);
+      EXPECT_EQ(r, next(m.begin(), 4));
+      r = m.upper_bound(14);
+      EXPECT_EQ(r, next(m.begin(), 5));
+      r = m.upper_bound(16);
+      EXPECT_EQ(r, next(m.begin(), 6));
+      r = m.upper_bound(18);
+      EXPECT_EQ(r, next(m.begin(), 7));
+      r = m.upper_bound(20);
+      EXPECT_EQ(r, next(m.begin(), 8));
+    }
+  }
+  {
+    typedef int V;
+    typedef base::flat_set<V, std::less<V>> M;
+    typedef M::iterator R;
+
+    V ar[] = {5, 7, 9, 11, 13, 15, 17, 19};
+
+    M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+    R r = m.upper_bound(5);
+    EXPECT_EQ(r, next(m.begin(), 1));
+    r = m.upper_bound(7);
+    EXPECT_EQ(r, next(m.begin(), 2));
+    r = m.upper_bound(9);
+    EXPECT_EQ(r, next(m.begin(), 3));
+    r = m.upper_bound(11);
+    EXPECT_EQ(r, next(m.begin(), 4));
+    r = m.upper_bound(13);
+    EXPECT_EQ(r, next(m.begin(), 5));
+    r = m.upper_bound(15);
+    EXPECT_EQ(r, next(m.begin(), 6));
+    r = m.upper_bound(17);
+    EXPECT_EQ(r, next(m.begin(), 7));
+    r = m.upper_bound(19);
+    EXPECT_EQ(r, next(m.begin(), 8));
+    r = m.upper_bound(4);
+    EXPECT_EQ(r, next(m.begin(), 0));
+    r = m.upper_bound(6);
+    EXPECT_EQ(r, next(m.begin(), 1));
+    r = m.upper_bound(8);
+    EXPECT_EQ(r, next(m.begin(), 2));
+    r = m.upper_bound(10);
+    EXPECT_EQ(r, next(m.begin(), 3));
+    r = m.upper_bound(12);
+    EXPECT_EQ(r, next(m.begin(), 4));
+    r = m.upper_bound(14);
+    EXPECT_EQ(r, next(m.begin(), 5));
+    r = m.upper_bound(16);
+    EXPECT_EQ(r, next(m.begin(), 6));
+    r = m.upper_bound(18);
+    EXPECT_EQ(r, next(m.begin(), 7));
+    r = m.upper_bound(20);
+    EXPECT_EQ(r, next(m.begin(), 8));
+  }
+}
+
+// ----------------------------------------------------------------------------
+// Regular type operations
+
+// class flat_set
+
+// void swap(flat_set& x)
+// void swap(flat_set& x, flat_set& y)
+
+TEST(FlatSetOurs, Swap) {
+  using M = base::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 works too;
+}
+
+// class flat_set
+
+// bool operator==(const flat_set& x, const flat_set& y)
+// bool operator!=(const flat_set& x, const flat_set& y)
+// bool operator<(const flat_set& x, const flat_set& y)
+// bool operator>(const flat_set& x, const flat_set& y)
+// bool operator<=(const flat_set& x, const flat_set& y)
+// bool operator>=(const flat_set& x, const flat_set& y)
+
+TEST(FlatSet, Comparison) {
+  using M = base::flat_set<int>;
+  M biggest{3};
+  M smallest{1};
+  M middle{1, 2};
+
+  EXPECT_EQ(biggest, biggest);
+  EXPECT_NE(biggest, smallest);
+  EXPECT_LT(smallest, middle);
+  EXPECT_LE(smallest, middle);
+  EXPECT_LE(middle, middle);
+  EXPECT_GT(biggest, middle);
+  EXPECT_GE(biggest, middle);
+  EXPECT_GE(biggest, biggest);
+}