Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(945)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: base/containers/flat_set_libcpp_unittest.cc

Issue 2552343003: First implementation of flat sets (Closed)
Patch Set: Initial commit Created 4 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« base/containers/flat_set.h ('K') | « base/containers/flat_set.h ('k') | base/containers/flat_set_unittest.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: base/containers/flat_set_libcpp_unittest.cc
diff --git a/base/containers/flat_set_libcpp_unittest.cc b/base/containers/flat_set_libcpp_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..766dd9d06f2824382830d4993c80694ae434e1b9
--- /dev/null
+++ b/base/containers/flat_set_libcpp_unittest.cc
@@ -0,0 +1,1686 @@
+// 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 tests from libc++ for std::set.
+// 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 implentation 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 manipualte these nodes. Flat containers store their elements in
+// contigious memory and move them around, type is required to be movable.
+// * No tests for N3644.
+// This proposal suggests that all defaul 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
+// castomise underlying data (if we are going to) is still up to debate.
+// * No tests, counting allocations. Flat sets have different allocation
+// 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 base {
+
+namespace {
+
+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 MoveOnly {
+ MoveOnly(const MoveOnly&);
+ MoveOnly& operator=(const MoveOnly&);
+
+ int data_;
+
+ public:
+ MoveOnly(int data = 1) : data_(data) {}
+ MoveOnly(MoveOnly&& x) : data_(x.data_) { x.data_ = 0; }
+ MoveOnly& operator=(MoveOnly&& x) {
+ data_ = x.data_;
+ x.data_ = 0;
+ return *this;
+ }
+
+ int get() const { return data_; }
+
+ 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;
+};
+
+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);
+}
+
+} // namespace
+
+// class flat_set
+
+// void clear();
+
+TEST(FlatSet, Clear) {
+ typedef base::flat_set<int> M;
+ typedef int V;
+
+ // clang-format off
+ V ar[] =
+ {
+ 1,
+ 2,
+ 3,
+ 4,
+ 5,
+ 6,
+ 7,
+ 8
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ ASSERT_TRUE(m.size() == 8);
+ m.clear();
+ ASSERT_TRUE(m.size() == 0);
+}
+
+// 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;
+
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 6,
+ 7,
+ 8,
+ 9,
+ 10,
+ 11,
+ 12
+ };
+ // clang-format on
+
+ const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.count(5);
+ ASSERT_TRUE(r == 1);
+ r = m.count(6);
+ ASSERT_TRUE(r == 1);
+ r = m.count(7);
+ ASSERT_TRUE(r == 1);
+ r = m.count(8);
+ ASSERT_TRUE(r == 1);
+ r = m.count(9);
+ ASSERT_TRUE(r == 1);
+ r = m.count(10);
+ ASSERT_TRUE(r == 1);
+ r = m.count(11);
+ ASSERT_TRUE(r == 1);
+ r = m.count(12);
+ ASSERT_TRUE(r == 1);
+ r = m.count(4);
+ ASSERT_TRUE(r == 0);
+ }
+ {
+ typedef int V;
+ typedef base::flat_set<int, std::less<V>> M;
+ typedef M::size_type R;
+
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 6,
+ 7,
+ 8,
+ 9,
+ 10,
+ 11,
+ 12
+ };
+ // clang-format on
+
+ const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.count(5);
+ ASSERT_TRUE(r == 1);
+ r = m.count(6);
+ ASSERT_TRUE(r == 1);
+ r = m.count(7);
+ ASSERT_TRUE(r == 1);
+ r = m.count(8);
+ ASSERT_TRUE(r == 1);
+ r = m.count(9);
+ ASSERT_TRUE(r == 1);
+ r = m.count(10);
+ ASSERT_TRUE(r == 1);
+ r = m.count(11);
+ ASSERT_TRUE(r == 1);
+ r = m.count(12);
+ ASSERT_TRUE(r == 1);
+ r = m.count(4);
+ ASSERT_TRUE(r == 0);
+ }
+}
+
+// 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();
+ ASSERT_TRUE(r.second);
+ ASSERT_TRUE(r.first == m.begin());
+ ASSERT_TRUE(m.size() == 1);
+ ASSERT_TRUE(*m.begin() == Emplaceable());
+ r = m.emplace(2, 3.5);
+ ASSERT_TRUE(r.second);
+ ASSERT_TRUE(r.first == next(m.begin()));
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(*r.first == Emplaceable(2, 3.5));
+ r = m.emplace(2, 3.5);
+ ASSERT_TRUE(!r.second);
+ ASSERT_TRUE(r.first == next(m.begin()));
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(*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));
+ ASSERT_TRUE(r.second);
+ ASSERT_TRUE(r.first == m.begin());
+ ASSERT_TRUE(m.size() == 1);
+ ASSERT_TRUE(*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());
+ ASSERT_TRUE(r == m.begin());
+ ASSERT_TRUE(m.size() == 1);
+ ASSERT_TRUE(*m.begin() == Emplaceable());
+ r = m.emplace_hint(m.cend(), 2, 3.5);
+ ASSERT_TRUE(r == next(m.begin()));
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(*r == Emplaceable(2, 3.5));
+ r = m.emplace_hint(m.cbegin(), 2, 3.5);
+ ASSERT_TRUE(r == next(m.begin()));
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(*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));
+ ASSERT_TRUE(r == m.begin());
+ ASSERT_TRUE(m.size() == 1);
+ ASSERT_TRUE(*r == 2);
+ }
+}
+
+// class flat_set
+
+// bool empty() const;
+
+TEST(FlatSet, Empty) {
+ typedef base::flat_set<int> M;
+ M m;
+ ASSERT_TRUE(m.empty());
+ m.insert(M::value_type(1));
+ ASSERT_TRUE(!m.empty());
+ m.clear();
+ ASSERT_TRUE(m.empty());
+}
+
+// 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;
+
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 7,
+ 9,
+ 11,
+ 13,
+ 15,
+ 17,
+ 19
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.equal_range(5);
+ ASSERT_TRUE(r.first == next(m.begin(), 0));
+ ASSERT_TRUE(r.second == next(m.begin(), 1));
+ r = m.equal_range(7);
+ ASSERT_TRUE(r.first == next(m.begin(), 1));
+ ASSERT_TRUE(r.second == next(m.begin(), 2));
+ r = m.equal_range(9);
+ ASSERT_TRUE(r.first == next(m.begin(), 2));
+ ASSERT_TRUE(r.second == next(m.begin(), 3));
+ r = m.equal_range(11);
+ ASSERT_TRUE(r.first == next(m.begin(), 3));
+ ASSERT_TRUE(r.second == next(m.begin(), 4));
+ r = m.equal_range(13);
+ ASSERT_TRUE(r.first == next(m.begin(), 4));
+ ASSERT_TRUE(r.second == next(m.begin(), 5));
+ r = m.equal_range(15);
+ ASSERT_TRUE(r.first == next(m.begin(), 5));
+ ASSERT_TRUE(r.second == next(m.begin(), 6));
+ r = m.equal_range(17);
+ ASSERT_TRUE(r.first == next(m.begin(), 6));
+ ASSERT_TRUE(r.second == next(m.begin(), 7));
+ r = m.equal_range(19);
+ ASSERT_TRUE(r.first == next(m.begin(), 7));
+ ASSERT_TRUE(r.second == next(m.begin(), 8));
+ r = m.equal_range(4);
+ ASSERT_TRUE(r.first == next(m.begin(), 0));
+ ASSERT_TRUE(r.second == next(m.begin(), 0));
+ r = m.equal_range(6);
+ ASSERT_TRUE(r.first == next(m.begin(), 1));
+ ASSERT_TRUE(r.second == next(m.begin(), 1));
+ r = m.equal_range(8);
+ ASSERT_TRUE(r.first == next(m.begin(), 2));
+ ASSERT_TRUE(r.second == next(m.begin(), 2));
+ r = m.equal_range(10);
+ ASSERT_TRUE(r.first == next(m.begin(), 3));
+ ASSERT_TRUE(r.second == next(m.begin(), 3));
+ r = m.equal_range(12);
+ ASSERT_TRUE(r.first == next(m.begin(), 4));
+ ASSERT_TRUE(r.second == next(m.begin(), 4));
+ r = m.equal_range(14);
+ ASSERT_TRUE(r.first == next(m.begin(), 5));
+ ASSERT_TRUE(r.second == next(m.begin(), 5));
+ r = m.equal_range(16);
+ ASSERT_TRUE(r.first == next(m.begin(), 6));
+ ASSERT_TRUE(r.second == next(m.begin(), 6));
+ r = m.equal_range(18);
+ ASSERT_TRUE(r.first == next(m.begin(), 7));
+ ASSERT_TRUE(r.second == next(m.begin(), 7));
+ r = m.equal_range(20);
+ ASSERT_TRUE(r.first == next(m.begin(), 8));
+ ASSERT_TRUE(r.second == next(m.begin(), 8));
+ }
+ {
+ typedef std::pair<M::const_iterator, M::const_iterator> R;
+
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 7,
+ 9,
+ 11,
+ 13,
+ 15,
+ 17,
+ 19
+ };
+ // clang-format on
+
+ const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.equal_range(5);
+ ASSERT_TRUE(r.first == next(m.begin(), 0));
+ ASSERT_TRUE(r.second == next(m.begin(), 1));
+ r = m.equal_range(7);
+ ASSERT_TRUE(r.first == next(m.begin(), 1));
+ ASSERT_TRUE(r.second == next(m.begin(), 2));
+ r = m.equal_range(9);
+ ASSERT_TRUE(r.first == next(m.begin(), 2));
+ ASSERT_TRUE(r.second == next(m.begin(), 3));
+ r = m.equal_range(11);
+ ASSERT_TRUE(r.first == next(m.begin(), 3));
+ ASSERT_TRUE(r.second == next(m.begin(), 4));
+ r = m.equal_range(13);
+ ASSERT_TRUE(r.first == next(m.begin(), 4));
+ ASSERT_TRUE(r.second == next(m.begin(), 5));
+ r = m.equal_range(15);
+ ASSERT_TRUE(r.first == next(m.begin(), 5));
+ ASSERT_TRUE(r.second == next(m.begin(), 6));
+ r = m.equal_range(17);
+ ASSERT_TRUE(r.first == next(m.begin(), 6));
+ ASSERT_TRUE(r.second == next(m.begin(), 7));
+ r = m.equal_range(19);
+ ASSERT_TRUE(r.first == next(m.begin(), 7));
+ ASSERT_TRUE(r.second == next(m.begin(), 8));
+ r = m.equal_range(4);
+ ASSERT_TRUE(r.first == next(m.begin(), 0));
+ ASSERT_TRUE(r.second == next(m.begin(), 0));
+ r = m.equal_range(6);
+ ASSERT_TRUE(r.first == next(m.begin(), 1));
+ ASSERT_TRUE(r.second == next(m.begin(), 1));
+ r = m.equal_range(8);
+ ASSERT_TRUE(r.first == next(m.begin(), 2));
+ ASSERT_TRUE(r.second == next(m.begin(), 2));
+ r = m.equal_range(10);
+ ASSERT_TRUE(r.first == next(m.begin(), 3));
+ ASSERT_TRUE(r.second == next(m.begin(), 3));
+ r = m.equal_range(12);
+ ASSERT_TRUE(r.first == next(m.begin(), 4));
+ ASSERT_TRUE(r.second == next(m.begin(), 4));
+ r = m.equal_range(14);
+ ASSERT_TRUE(r.first == next(m.begin(), 5));
+ ASSERT_TRUE(r.second == next(m.begin(), 5));
+ r = m.equal_range(16);
+ ASSERT_TRUE(r.first == next(m.begin(), 6));
+ ASSERT_TRUE(r.second == next(m.begin(), 6));
+ r = m.equal_range(18);
+ ASSERT_TRUE(r.first == next(m.begin(), 7));
+ ASSERT_TRUE(r.second == next(m.begin(), 7));
+ r = m.equal_range(20);
+ ASSERT_TRUE(r.first == next(m.begin(), 8));
+ ASSERT_TRUE(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;
+
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 7,
+ 9,
+ 11,
+ 13,
+ 15,
+ 17,
+ 19
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.equal_range(5);
+ ASSERT_TRUE(r.first == next(m.begin(), 0));
+ ASSERT_TRUE(r.second == next(m.begin(), 1));
+ r = m.equal_range(7);
+ ASSERT_TRUE(r.first == next(m.begin(), 1));
+ ASSERT_TRUE(r.second == next(m.begin(), 2));
+ r = m.equal_range(9);
+ ASSERT_TRUE(r.first == next(m.begin(), 2));
+ ASSERT_TRUE(r.second == next(m.begin(), 3));
+ r = m.equal_range(11);
+ ASSERT_TRUE(r.first == next(m.begin(), 3));
+ ASSERT_TRUE(r.second == next(m.begin(), 4));
+ r = m.equal_range(13);
+ ASSERT_TRUE(r.first == next(m.begin(), 4));
+ ASSERT_TRUE(r.second == next(m.begin(), 5));
+ r = m.equal_range(15);
+ ASSERT_TRUE(r.first == next(m.begin(), 5));
+ ASSERT_TRUE(r.second == next(m.begin(), 6));
+ r = m.equal_range(17);
+ ASSERT_TRUE(r.first == next(m.begin(), 6));
+ ASSERT_TRUE(r.second == next(m.begin(), 7));
+ r = m.equal_range(19);
+ ASSERT_TRUE(r.first == next(m.begin(), 7));
+ ASSERT_TRUE(r.second == next(m.begin(), 8));
+ r = m.equal_range(4);
+ ASSERT_TRUE(r.first == next(m.begin(), 0));
+ ASSERT_TRUE(r.second == next(m.begin(), 0));
+ r = m.equal_range(6);
+ ASSERT_TRUE(r.first == next(m.begin(), 1));
+ ASSERT_TRUE(r.second == next(m.begin(), 1));
+ r = m.equal_range(8);
+ ASSERT_TRUE(r.first == next(m.begin(), 2));
+ ASSERT_TRUE(r.second == next(m.begin(), 2));
+ r = m.equal_range(10);
+ ASSERT_TRUE(r.first == next(m.begin(), 3));
+ ASSERT_TRUE(r.second == next(m.begin(), 3));
+ r = m.equal_range(12);
+ ASSERT_TRUE(r.first == next(m.begin(), 4));
+ ASSERT_TRUE(r.second == next(m.begin(), 4));
+ r = m.equal_range(14);
+ ASSERT_TRUE(r.first == next(m.begin(), 5));
+ ASSERT_TRUE(r.second == next(m.begin(), 5));
+ r = m.equal_range(16);
+ ASSERT_TRUE(r.first == next(m.begin(), 6));
+ ASSERT_TRUE(r.second == next(m.begin(), 6));
+ r = m.equal_range(18);
+ ASSERT_TRUE(r.first == next(m.begin(), 7));
+ ASSERT_TRUE(r.second == next(m.begin(), 7));
+ r = m.equal_range(20);
+ ASSERT_TRUE(r.first == next(m.begin(), 8));
+ ASSERT_TRUE(r.second == next(m.begin(), 8));
+ }
+ }
+}
+
+// class flat_set
+
+// iterator erase(const_iterator position);
+
+TEST(FlatSet, EraseCIter) {
+ {
+ typedef base::flat_set<int> M;
+ typedef int V;
+ typedef M::iterator I;
+
+ // clang-format off
+ V ar[] =
+ {
+ 1,
+ 2,
+ 3,
+ 4,
+ 5,
+ 6,
+ 7,
+ 8
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ ASSERT_TRUE(m.size() == 8);
+ I i = m.erase(next(m.cbegin(), 3));
+ ASSERT_TRUE(m.size() == 7);
+ ASSERT_TRUE(i == next(m.begin(), 3));
+ ASSERT_TRUE(*next(m.begin(), 0) == 1);
+ ASSERT_TRUE(*next(m.begin(), 1) == 2);
+ ASSERT_TRUE(*next(m.begin(), 2) == 3);
+ ASSERT_TRUE(*next(m.begin(), 3) == 5);
+ ASSERT_TRUE(*next(m.begin(), 4) == 6);
+ ASSERT_TRUE(*next(m.begin(), 5) == 7);
+ ASSERT_TRUE(*next(m.begin(), 6) == 8);
+
+ i = m.erase(next(m.cbegin(), 0));
+ ASSERT_TRUE(m.size() == 6);
+ ASSERT_TRUE(i == m.begin());
+ ASSERT_TRUE(*next(m.begin(), 0) == 2);
+ ASSERT_TRUE(*next(m.begin(), 1) == 3);
+ ASSERT_TRUE(*next(m.begin(), 2) == 5);
+ ASSERT_TRUE(*next(m.begin(), 3) == 6);
+ ASSERT_TRUE(*next(m.begin(), 4) == 7);
+ ASSERT_TRUE(*next(m.begin(), 5) == 8);
+
+ i = m.erase(next(m.cbegin(), 5));
+ ASSERT_TRUE(m.size() == 5);
+ ASSERT_TRUE(i == m.end());
+ ASSERT_TRUE(*next(m.begin(), 0) == 2);
+ ASSERT_TRUE(*next(m.begin(), 1) == 3);
+ ASSERT_TRUE(*next(m.begin(), 2) == 5);
+ ASSERT_TRUE(*next(m.begin(), 3) == 6);
+ ASSERT_TRUE(*next(m.begin(), 4) == 7);
+
+ i = m.erase(next(m.cbegin(), 1));
+ ASSERT_TRUE(m.size() == 4);
+ ASSERT_TRUE(i == next(m.begin()));
+ ASSERT_TRUE(*next(m.begin(), 0) == 2);
+ ASSERT_TRUE(*next(m.begin(), 1) == 5);
+ ASSERT_TRUE(*next(m.begin(), 2) == 6);
+ ASSERT_TRUE(*next(m.begin(), 3) == 7);
+
+ i = m.erase(next(m.cbegin(), 2));
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(i == next(m.begin(), 2));
+ ASSERT_TRUE(*next(m.begin(), 0) == 2);
+ ASSERT_TRUE(*next(m.begin(), 1) == 5);
+ ASSERT_TRUE(*next(m.begin(), 2) == 7);
+
+ i = m.erase(next(m.cbegin(), 2));
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(i == next(m.begin(), 2));
+ ASSERT_TRUE(*next(m.begin(), 0) == 2);
+ ASSERT_TRUE(*next(m.begin(), 1) == 5);
+
+ i = m.erase(next(m.cbegin(), 0));
+ ASSERT_TRUE(m.size() == 1);
+ ASSERT_TRUE(i == next(m.begin(), 0));
+ ASSERT_TRUE(*next(m.begin(), 0) == 5);
+
+ i = m.erase(m.cbegin());
+ ASSERT_TRUE(m.size() == 0);
+ ASSERT_TRUE(i == m.begin());
+ ASSERT_TRUE(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;
+
+ // clang-format off
+ V ar[] =
+ {
+ 1,
+ 2,
+ 3,
+ 4,
+ 5,
+ 6,
+ 7,
+ 8
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ ASSERT_TRUE(m.size() == 8);
+ I i = m.erase(next(m.cbegin(), 5), next(m.cbegin(), 5));
+ ASSERT_TRUE(m.size() == 8);
+ ASSERT_TRUE(i == next(m.begin(), 5));
+ ASSERT_TRUE(*next(m.begin(), 0) == 1);
+ ASSERT_TRUE(*next(m.begin(), 1) == 2);
+ ASSERT_TRUE(*next(m.begin(), 2) == 3);
+ ASSERT_TRUE(*next(m.begin(), 3) == 4);
+ ASSERT_TRUE(*next(m.begin(), 4) == 5);
+ ASSERT_TRUE(*next(m.begin(), 5) == 6);
+ ASSERT_TRUE(*next(m.begin(), 6) == 7);
+ ASSERT_TRUE(*next(m.begin(), 7) == 8);
+
+ i = m.erase(next(m.cbegin(), 3), next(m.cbegin(), 4));
+ ASSERT_TRUE(m.size() == 7);
+ ASSERT_TRUE(i == next(m.begin(), 3));
+ ASSERT_TRUE(*next(m.begin(), 0) == 1);
+ ASSERT_TRUE(*next(m.begin(), 1) == 2);
+ ASSERT_TRUE(*next(m.begin(), 2) == 3);
+ ASSERT_TRUE(*next(m.begin(), 3) == 5);
+ ASSERT_TRUE(*next(m.begin(), 4) == 6);
+ ASSERT_TRUE(*next(m.begin(), 5) == 7);
+ ASSERT_TRUE(*next(m.begin(), 6) == 8);
+
+ i = m.erase(next(m.cbegin(), 2), next(m.cbegin(), 5));
+ ASSERT_TRUE(m.size() == 4);
+ ASSERT_TRUE(i == next(m.begin(), 2));
+ ASSERT_TRUE(*next(m.begin(), 0) == 1);
+ ASSERT_TRUE(*next(m.begin(), 1) == 2);
+ ASSERT_TRUE(*next(m.begin(), 2) == 7);
+ ASSERT_TRUE(*next(m.begin(), 3) == 8);
+
+ i = m.erase(next(m.cbegin(), 0), next(m.cbegin(), 2));
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(i == next(m.begin(), 0));
+ ASSERT_TRUE(*next(m.begin(), 0) == 7);
+ ASSERT_TRUE(*next(m.begin(), 1) == 8);
+
+ i = m.erase(m.cbegin(), m.cend());
+ ASSERT_TRUE(m.size() == 0);
+ ASSERT_TRUE(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;
+
+ // clang-format off
+ V ar[] =
+ {
+ 1,
+ 2,
+ 3,
+ 4,
+ 5,
+ 6,
+ 7,
+ 8
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ ASSERT_TRUE(m.size() == 8);
+ I i = m.erase(9);
+ ASSERT_TRUE(m.size() == 8);
+ ASSERT_TRUE(i == 0);
+ ASSERT_TRUE(*next(m.begin(), 0) == 1);
+ ASSERT_TRUE(*next(m.begin(), 1) == 2);
+ ASSERT_TRUE(*next(m.begin(), 2) == 3);
+ ASSERT_TRUE(*next(m.begin(), 3) == 4);
+ ASSERT_TRUE(*next(m.begin(), 4) == 5);
+ ASSERT_TRUE(*next(m.begin(), 5) == 6);
+ ASSERT_TRUE(*next(m.begin(), 6) == 7);
+ ASSERT_TRUE(*next(m.begin(), 7) == 8);
+
+ i = m.erase(4);
+ ASSERT_TRUE(m.size() == 7);
+ ASSERT_TRUE(i == 1);
+ ASSERT_TRUE(*next(m.begin(), 0) == 1);
+ ASSERT_TRUE(*next(m.begin(), 1) == 2);
+ ASSERT_TRUE(*next(m.begin(), 2) == 3);
+ ASSERT_TRUE(*next(m.begin(), 3) == 5);
+ ASSERT_TRUE(*next(m.begin(), 4) == 6);
+ ASSERT_TRUE(*next(m.begin(), 5) == 7);
+ ASSERT_TRUE(*next(m.begin(), 6) == 8);
+
+ i = m.erase(1);
+ ASSERT_TRUE(m.size() == 6);
+ ASSERT_TRUE(i == 1);
+ ASSERT_TRUE(*next(m.begin(), 0) == 2);
+ ASSERT_TRUE(*next(m.begin(), 1) == 3);
+ ASSERT_TRUE(*next(m.begin(), 2) == 5);
+ ASSERT_TRUE(*next(m.begin(), 3) == 6);
+ ASSERT_TRUE(*next(m.begin(), 4) == 7);
+ ASSERT_TRUE(*next(m.begin(), 5) == 8);
+
+ i = m.erase(8);
+ ASSERT_TRUE(m.size() == 5);
+ ASSERT_TRUE(i == 1);
+ ASSERT_TRUE(*next(m.begin(), 0) == 2);
+ ASSERT_TRUE(*next(m.begin(), 1) == 3);
+ ASSERT_TRUE(*next(m.begin(), 2) == 5);
+ ASSERT_TRUE(*next(m.begin(), 3) == 6);
+ ASSERT_TRUE(*next(m.begin(), 4) == 7);
+
+ i = m.erase(3);
+ ASSERT_TRUE(m.size() == 4);
+ ASSERT_TRUE(i == 1);
+ ASSERT_TRUE(*next(m.begin(), 0) == 2);
+ ASSERT_TRUE(*next(m.begin(), 1) == 5);
+ ASSERT_TRUE(*next(m.begin(), 2) == 6);
+ ASSERT_TRUE(*next(m.begin(), 3) == 7);
+
+ i = m.erase(6);
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(i == 1);
+ ASSERT_TRUE(*next(m.begin(), 0) == 2);
+ ASSERT_TRUE(*next(m.begin(), 1) == 5);
+ ASSERT_TRUE(*next(m.begin(), 2) == 7);
+
+ i = m.erase(7);
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(i == 1);
+ ASSERT_TRUE(*next(m.begin(), 0) == 2);
+ ASSERT_TRUE(*next(m.begin(), 1) == 5);
+
+ i = m.erase(2);
+ ASSERT_TRUE(m.size() == 1);
+ ASSERT_TRUE(i == 1);
+ ASSERT_TRUE(*next(m.begin(), 0) == 5);
+
+ i = m.erase(5);
+ ASSERT_TRUE(m.size() == 0);
+ ASSERT_TRUE(i == 1);
+ }
+}
+
+// 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;
+
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 6,
+ 7,
+ 8,
+ 9,
+ 10,
+ 11,
+ 12
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.find(5);
+ ASSERT_TRUE(r == m.begin());
+ r = m.find(6);
+ ASSERT_TRUE(r == next(m.begin()));
+ r = m.find(7);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.find(8);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.find(9);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.find(10);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.find(11);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.find(12);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.find(4);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ }
+ {
+ typedef M::const_iterator R;
+
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 6,
+ 7,
+ 8,
+ 9,
+ 10,
+ 11,
+ 12
+ };
+ // clang-format on
+
+ const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.find(5);
+ ASSERT_TRUE(r == m.begin());
+ r = m.find(6);
+ ASSERT_TRUE(r == next(m.begin()));
+ r = m.find(7);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.find(8);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.find(9);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.find(10);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.find(11);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.find(12);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.find(4);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ }
+ }
+ {
+ typedef int V;
+ typedef base::flat_set<V, std::less<V>> M;
+ typedef M::iterator R;
+
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 6,
+ 7,
+ 8,
+ 9,
+ 10,
+ 11,
+ 12
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.find(5);
+ ASSERT_TRUE(r == m.begin());
+ r = m.find(6);
+ ASSERT_TRUE(r == next(m.begin()));
+ r = m.find(7);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.find(8);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.find(9);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.find(10);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.find(11);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.find(12);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.find(4);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ }
+}
+
+// Check that base::flat_set and it's iterators can be instantiated with an
+// incomplete type.
+
+TEST(FlatSet, IncompleteType) {
+ struct A {
+ typedef base::flat_set<A> Set;
+ int data;
+ Set m;
+ Set::iterator it;
+ Set::const_iterator cit;
+ };
+
+ // libc++ tests define operator< for A, but clang is complaining that it's
+ // unsued
+
+ A a;
+}
+
+// class flat_set
+
+// pair<iterator, bool> insert(const value_type& v);
+
+TEST(FlatSet, InsertCV) {
+ {
+ typedef base::flat_set<int> M;
+ typedef std::pair<M::iterator, bool> R;
+ M m;
+ R r = m.insert(M::value_type(2));
+ ASSERT_TRUE(r.second);
+ ASSERT_TRUE(r.first == m.begin());
+ ASSERT_TRUE(m.size() == 1);
+ ASSERT_TRUE(*r.first == 2);
+
+ r = m.insert(M::value_type(1));
+ ASSERT_TRUE(r.second);
+ ASSERT_TRUE(r.first == m.begin());
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(*r.first == 1);
+
+ r = m.insert(M::value_type(3));
+ ASSERT_TRUE(r.second);
+ ASSERT_TRUE(r.first == prev(m.end()));
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(*r.first == 3);
+
+ r = m.insert(M::value_type(3));
+ ASSERT_TRUE(!r.second);
+ ASSERT_TRUE(r.first == prev(m.end()));
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(*r.first == 3);
+ }
+}
+
+// class flat_set
+
+// void insert(initializer_list<value_type> il);
+
+TEST(FlatSet, InitializerList) {
+ {
+ typedef base::flat_set<int> C;
+ typedef C::value_type V;
+ C m = {10, 8};
+ m.insert({1, 2, 3, 4, 5, 6});
+ ASSERT_TRUE(m.size() == 8);
+ ASSERT_TRUE(distance(m.begin(), m.end()) ==
+ static_cast<C::difference_type>(m.size()));
+ C::const_iterator i = m.cbegin();
+ ASSERT_TRUE(*i == V(1));
+ ASSERT_TRUE(*++i == V(2));
+ ASSERT_TRUE(*++i == V(3));
+ ASSERT_TRUE(*++i == V(4));
+ ASSERT_TRUE(*++i == V(5));
+ ASSERT_TRUE(*++i == V(6));
+ ASSERT_TRUE(*++i == V(8));
+ ASSERT_TRUE(*++i == V(10));
+ }
+}
+
+// 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));
+ ASSERT_TRUE(r == m.begin());
+ ASSERT_TRUE(m.size() == 1);
+ ASSERT_TRUE(*r == 2);
+
+ r = m.insert(m.cend(), M::value_type(1));
+ ASSERT_TRUE(r == m.begin());
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(*r == 1);
+
+ r = m.insert(m.cend(), M::value_type(3));
+ ASSERT_TRUE(r == prev(m.end()));
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(*r == 3);
+
+ r = m.insert(m.cend(), M::value_type(3));
+ ASSERT_TRUE(r == prev(m.end()));
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(*r == 3);
+ }
+}
+
+// class flat_set
+
+// template <class InputIterator>
+// void insert(InputIterator first, InputIterator last);
+
+TEST(FlatSet, InsertIterIter) {
+ {
+ typedef std::set<int> M;
+ typedef int V;
+
+ // clang-format off
+ V ar[] =
+ {
+ 1,
+ 1,
+ 1,
+ 2,
+ 2,
+ 2,
+ 3,
+ 3,
+ 3
+ };
+ // clang-format on
+
+ M m;
+ m.insert(input_iterator<const V*>(ar),
+ input_iterator<const V*>(ar + sizeof(ar) / sizeof(ar[0])));
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(*m.begin() == 1);
+ ASSERT_TRUE(*next(m.begin()) == 2);
+ ASSERT_TRUE(*next(m.begin(), 2) == 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));
+ ASSERT_TRUE(r == m.begin());
+ ASSERT_TRUE(m.size() == 1);
+ ASSERT_TRUE(*r == 2);
+
+ r = m.insert(m.cend(), M::value_type(1));
+ ASSERT_TRUE(r == m.begin());
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(*r == 1);
+
+ r = m.insert(m.cend(), M::value_type(3));
+ ASSERT_TRUE(r == prev(m.end()));
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(*r == 3);
+
+ r = m.insert(m.cend(), M::value_type(3));
+ ASSERT_TRUE(r == prev(m.end()));
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(*r == 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));
+ ASSERT_TRUE(r.second);
+ ASSERT_TRUE(r.first == m.begin());
+ ASSERT_TRUE(m.size() == 1);
+ ASSERT_TRUE(*r.first == 2);
+
+ r = m.insert(M::value_type(1));
+ ASSERT_TRUE(r.second);
+ ASSERT_TRUE(r.first == m.begin());
+ ASSERT_TRUE(m.size() == 2);
+ ASSERT_TRUE(*r.first == 1);
+
+ r = m.insert(M::value_type(3));
+ ASSERT_TRUE(r.second);
+ ASSERT_TRUE(r.first == prev(m.end()));
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(*r.first == 3);
+
+ r = m.insert(M::value_type(3));
+ ASSERT_TRUE(!r.second);
+ ASSERT_TRUE(r.first == prev(m.end()));
+ ASSERT_TRUE(m.size() == 3);
+ ASSERT_TRUE(*r.first == 3);
+ }
+}
+
+// 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;
+ // clang-format off
+ 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
+ };
+ // clang-format on
+
+ base::flat_set<int> m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ ASSERT_TRUE(std::distance(m.begin(), m.end()) ==
+ static_cast<base::flat_set<int>::difference_type>(m.size()));
+ ASSERT_TRUE(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;
+ ASSERT_TRUE(i == k);
+ for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
+ ASSERT_TRUE(*i == j);
+ }
+ {
+ typedef int V;
+ // clang-format off
+ 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
+ };
+ // clang-format on
+
+ const base::flat_set<int> m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ ASSERT_TRUE(std::distance(m.begin(), m.end()) ==
+ static_cast<base::flat_set<int>::difference_type>(m.size()));
+ ASSERT_TRUE(std::distance(m.cbegin(), m.cend()) ==
+ static_cast<base::flat_set<int>::difference_type>(m.size()));
+ ASSERT_TRUE(std::distance(m.rbegin(), m.rend()) ==
+ static_cast<base::flat_set<int>::difference_type>(m.size()));
+ ASSERT_TRUE(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)
+ ASSERT_TRUE(*i == j);
+ }
+}
+
+// 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;
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 7,
+ 9,
+ 11,
+ 13,
+ 15,
+ 17,
+ 19
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.lower_bound(5);
+ ASSERT_TRUE(r == m.begin());
+ r = m.lower_bound(7);
+ ASSERT_TRUE(r == next(m.begin()));
+ r = m.lower_bound(9);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.lower_bound(11);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.lower_bound(13);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.lower_bound(15);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.lower_bound(17);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.lower_bound(19);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.lower_bound(4);
+ ASSERT_TRUE(r == next(m.begin(), 0));
+ r = m.lower_bound(6);
+ ASSERT_TRUE(r == next(m.begin(), 1));
+ r = m.lower_bound(8);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.lower_bound(10);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.lower_bound(12);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.lower_bound(14);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.lower_bound(16);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.lower_bound(18);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.lower_bound(20);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ }
+ {
+ typedef M::const_iterator R;
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 7,
+ 9,
+ 11,
+ 13,
+ 15,
+ 17,
+ 19
+ };
+ // clang-format on
+
+ const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.lower_bound(5);
+ ASSERT_TRUE(r == m.begin());
+ r = m.lower_bound(7);
+ ASSERT_TRUE(r == next(m.begin()));
+ r = m.lower_bound(9);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.lower_bound(11);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.lower_bound(13);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.lower_bound(15);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.lower_bound(17);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.lower_bound(19);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.lower_bound(4);
+ ASSERT_TRUE(r == next(m.begin(), 0));
+ r = m.lower_bound(6);
+ ASSERT_TRUE(r == next(m.begin(), 1));
+ r = m.lower_bound(8);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.lower_bound(10);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.lower_bound(12);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.lower_bound(14);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.lower_bound(16);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.lower_bound(18);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.lower_bound(20);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ }
+ }
+ {
+ typedef int V;
+ typedef base::flat_set<V, std::less<V>> M;
+ typedef M::iterator R;
+
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 7,
+ 9,
+ 11,
+ 13,
+ 15,
+ 17,
+ 19
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.lower_bound(5);
+ ASSERT_TRUE(r == m.begin());
+ r = m.lower_bound(7);
+ ASSERT_TRUE(r == next(m.begin()));
+ r = m.lower_bound(9);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.lower_bound(11);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.lower_bound(13);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.lower_bound(15);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.lower_bound(17);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.lower_bound(19);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.lower_bound(4);
+ ASSERT_TRUE(r == next(m.begin(), 0));
+ r = m.lower_bound(6);
+ ASSERT_TRUE(r == next(m.begin(), 1));
+ r = m.lower_bound(8);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.lower_bound(10);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.lower_bound(12);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.lower_bound(14);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.lower_bound(16);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.lower_bound(18);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.lower_bound(20);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ }
+}
+
+// class flat_set
+
+// size_type size() const;
+
+TEST(FlatSet, Size) {
+ {
+ typedef base::flat_set<int> M;
+ M m;
+ ASSERT_TRUE(m.size() == 0);
+ m.insert(M::value_type(2));
+ ASSERT_TRUE(m.size() == 1);
+ m.insert(M::value_type(1));
+ ASSERT_TRUE(m.size() == 2);
+ m.insert(M::value_type(3));
+ ASSERT_TRUE(m.size() == 3);
+ m.erase(m.begin());
+ ASSERT_TRUE(m.size() == 2);
+ m.erase(m.begin());
+ ASSERT_TRUE(m.size() == 1);
+ m.erase(m.begin());
+ ASSERT_TRUE(m.size() == 0);
+ }
+}
+
+// class flat_set
+
+// // 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) {
+ {
+ typedef base::flat_set<int> C;
+ 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), "");
+ 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), "");
+ static_assert((std::is_same<C::difference_type, std::ptrdiff_t>::value),
+ "");
+ }
+}
+
+// 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;
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 7,
+ 9,
+ 11,
+ 13,
+ 15,
+ 17,
+ 19
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.upper_bound(5);
+ ASSERT_TRUE(r == next(m.begin(), 1));
+ r = m.upper_bound(7);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.upper_bound(9);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.upper_bound(11);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.upper_bound(13);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.upper_bound(15);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.upper_bound(17);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.upper_bound(19);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ r = m.upper_bound(4);
+ ASSERT_TRUE(r == next(m.begin(), 0));
+ r = m.upper_bound(6);
+ ASSERT_TRUE(r == next(m.begin(), 1));
+ r = m.upper_bound(8);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.upper_bound(10);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.upper_bound(12);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.upper_bound(14);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.upper_bound(16);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.upper_bound(18);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.upper_bound(20);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ }
+ {
+ typedef M::const_iterator R;
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 7,
+ 9,
+ 11,
+ 13,
+ 15,
+ 17,
+ 19
+ };
+ // clang-format on
+
+ const M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.upper_bound(5);
+ ASSERT_TRUE(r == next(m.begin(), 1));
+ r = m.upper_bound(7);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.upper_bound(9);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.upper_bound(11);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.upper_bound(13);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.upper_bound(15);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.upper_bound(17);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.upper_bound(19);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ r = m.upper_bound(4);
+ ASSERT_TRUE(r == next(m.begin(), 0));
+ r = m.upper_bound(6);
+ ASSERT_TRUE(r == next(m.begin(), 1));
+ r = m.upper_bound(8);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.upper_bound(10);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.upper_bound(12);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.upper_bound(14);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.upper_bound(16);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.upper_bound(18);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.upper_bound(20);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ }
+ }
+ {
+ typedef int V;
+ typedef base::flat_set<V, std::less<V>> M;
+ typedef M::iterator R;
+
+ // clang-format off
+ V ar[] =
+ {
+ 5,
+ 7,
+ 9,
+ 11,
+ 13,
+ 15,
+ 17,
+ 19
+ };
+ // clang-format on
+
+ M m(ar, ar + sizeof(ar) / sizeof(ar[0]));
+ R r = m.upper_bound(5);
+ ASSERT_TRUE(r == next(m.begin(), 1));
+ r = m.upper_bound(7);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.upper_bound(9);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.upper_bound(11);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.upper_bound(13);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.upper_bound(15);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.upper_bound(17);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.upper_bound(19);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ r = m.upper_bound(4);
+ ASSERT_TRUE(r == next(m.begin(), 0));
+ r = m.upper_bound(6);
+ ASSERT_TRUE(r == next(m.begin(), 1));
+ r = m.upper_bound(8);
+ ASSERT_TRUE(r == next(m.begin(), 2));
+ r = m.upper_bound(10);
+ ASSERT_TRUE(r == next(m.begin(), 3));
+ r = m.upper_bound(12);
+ ASSERT_TRUE(r == next(m.begin(), 4));
+ r = m.upper_bound(14);
+ ASSERT_TRUE(r == next(m.begin(), 5));
+ r = m.upper_bound(16);
+ ASSERT_TRUE(r == next(m.begin(), 6));
+ r = m.upper_bound(18);
+ ASSERT_TRUE(r == next(m.begin(), 7));
+ r = m.upper_bound(20);
+ ASSERT_TRUE(r == next(m.begin(), 8));
+ }
+}
+
+} // namespace base
« base/containers/flat_set.h ('K') | « base/containers/flat_set.h ('k') | base/containers/flat_set_unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698