Make flat containers stable, allow constructing from vector.
The stability matters more for maps that it did for sets, so I think it makes sense if all of the flat_set/map containers are stable sorted.
Since we are unlikely to switch out the storage type, I made constructors that take a moved vector. I want to use this pattern to
collect base::Values and then construct a map from it all at once.
Review-Url: https://codereview.chromium.org/2776793002
Cr-Commit-Position: refs/heads/master@{#463094}
CrOS-Libchrome-Original-Commit: 5c72fdadcbe0e5914a2a1c935992975e31ff3e67
diff --git a/base/containers/flat_map.h b/base/containers/flat_map.h
index e2cb003..bd0b126 100644
--- a/base/containers/flat_map.h
+++ b/base/containers/flat_map.h
@@ -38,6 +38,15 @@
// flat_tree.h for more details for most of these functions. As a quick
// reference, the functions available are:
//
+// Constructors (inputs need not be sorted):
+// flat_map(InputIterator first, InputIterator last,
+// FlatContainerDupes, const Compare& compare = Compare());
+// flat_map(const flat_map&);
+// flat_map(flat_map&&);
+// flat_map(std::vector<value_type>, FlatContainerDupes); // Re-use storage.
+// flat_map(std::initializer_list<value_type> ilist,
+// const Compare& comp = Compare());
+//
// Assignment functions:
// flat_map& operator=(const flat_map&);
// flat_map& operator=(flat_map&&);
@@ -95,7 +104,7 @@
// iterator upper_bound(const Key&);
// const_iterator upper_bound(const Key&) const;
//
-// General functions
+// General functions:
// void swap(flat_map&&)
//
// Non-member operators:
@@ -134,21 +143,28 @@
// duplicates an arbitrary one will be chosen.
//
// Assume that move constructors invalidate iterators and references.
+ //
+ // The constructors that take ranges, lists, and vectors do not require that
+ // the input be sorted.
flat_map();
explicit flat_map(const Compare& comp);
- // Not stable in the presence of duplicates in the initializer list.
template <class InputIterator>
flat_map(InputIterator first,
InputIterator last,
+ FlatContainerDupes dupe_handling,
const Compare& comp = Compare());
flat_map(const flat_map&);
flat_map(flat_map&&);
- // Not stable in the presence of duplicates in the initializer list.
+ flat_map(std::vector<value_type> items,
+ FlatContainerDupes dupe_handling,
+ const Compare& comp = Compare());
+
flat_map(std::initializer_list<value_type> ilist,
+ FlatContainerDupes dupe_handling,
const Compare& comp = Compare());
~flat_map();
@@ -160,7 +176,7 @@
flat_map& operator=(const flat_map&);
flat_map& operator=(flat_map&&);
- // Not stable in the presence of duplicates in the initializer list.
+ // Takes the first if there are duplicates in the initializer list.
flat_map& operator=(std::initializer_list<value_type> ilist);
// --------------------------------------------------------------------------
@@ -197,8 +213,9 @@
template <class InputIterator>
flat_map<Key, Mapped, Compare>::flat_map(InputIterator first,
InputIterator last,
+ FlatContainerDupes dupe_handling,
const Compare& comp)
- : tree(first, last, comp) {}
+ : tree(first, last, dupe_handling, comp) {}
template <class Key, class Mapped, class Compare>
flat_map<Key, Mapped, Compare>::flat_map(const flat_map&) = default;
@@ -207,10 +224,17 @@
flat_map<Key, Mapped, Compare>::flat_map(flat_map&&) = default;
template <class Key, class Mapped, class Compare>
+flat_map<Key, Mapped, Compare>::flat_map(std::vector<value_type> items,
+ FlatContainerDupes dupe_handling,
+ const Compare& comp)
+ : tree(std::move(items), dupe_handling, comp) {}
+
+template <class Key, class Mapped, class Compare>
flat_map<Key, Mapped, Compare>::flat_map(
std::initializer_list<value_type> ilist,
+ FlatContainerDupes dupe_handling,
const Compare& comp)
- : flat_map(std::begin(ilist), std::end(ilist), comp) {}
+ : flat_map(std::begin(ilist), std::end(ilist), dupe_handling, comp) {}
template <class Key, class Mapped, class Compare>
flat_map<Key, Mapped, Compare>::~flat_map() = default;
diff --git a/base/containers/flat_map_unittest.cc b/base/containers/flat_map_unittest.cc
index 18524ef..0556527 100644
--- a/base/containers/flat_map_unittest.cc
+++ b/base/containers/flat_map_unittest.cc
@@ -36,10 +36,16 @@
TEST(FlatMap, RangeConstructor) {
flat_map<int, int>::value_type input_vals[] = {
- {1, 1}, {1, 1}, {1, 1}, {2, 2}, {2, 2}, {2, 2}, {3, 3}, {3, 3}, {3, 3}};
+ {1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}};
- flat_map<int, int> cont(std::begin(input_vals), std::end(input_vals));
- EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2),
+ flat_map<int, int> first(std::begin(input_vals), std::end(input_vals),
+ KEEP_FIRST_OF_DUPES);
+ EXPECT_THAT(first, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 1),
+ std::make_pair(3, 1)));
+
+ flat_map<int, int> last(std::begin(input_vals), std::end(input_vals),
+ KEEP_LAST_OF_DUPES);
+ EXPECT_THAT(last, ElementsAre(std::make_pair(1, 3), std::make_pair(2, 3),
std::make_pair(3, 3)));
}
@@ -60,13 +66,40 @@
EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
}
+TEST(FlatMap, VectorConstructor) {
+ using IntPair = std::pair<int, int>;
+ using IntMap = flat_map<int, int>;
+ {
+ std::vector<IntPair> vect{{1, 1}, {1, 2}, {2, 1}};
+ IntMap map(std::move(vect), KEEP_FIRST_OF_DUPES);
+ EXPECT_THAT(map, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
+ }
+ {
+ std::vector<IntPair> vect{{1, 1}, {1, 2}, {2, 1}};
+ IntMap map(std::move(vect), KEEP_LAST_OF_DUPES);
+ EXPECT_THAT(map, ElementsAre(IntPair(1, 2), IntPair(2, 1)));
+ }
+}
+
TEST(FlatMap, InitializerListConstructor) {
- flat_map<int, int> cont{{1, 1}, {2, 2}, {3, 3}, {4, 4},
- {5, 5}, {6, 6}, {10, 10}, {8, 8}};
- EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2),
- std::make_pair(3, 3), std::make_pair(4, 4),
- std::make_pair(5, 5), std::make_pair(6, 6),
- std::make_pair(8, 8), std::make_pair(10, 10)));
+ {
+ flat_map<int, int> cont(
+ {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {1, 2}, {10, 10}, {8, 8}},
+ KEEP_FIRST_OF_DUPES);
+ EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2),
+ std::make_pair(3, 3), std::make_pair(4, 4),
+ std::make_pair(5, 5), std::make_pair(8, 8),
+ std::make_pair(10, 10)));
+ }
+ {
+ flat_map<int, int> cont(
+ {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {1, 2}, {10, 10}, {8, 8}},
+ KEEP_LAST_OF_DUPES);
+ EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 2), std::make_pair(2, 2),
+ std::make_pair(3, 3), std::make_pair(4, 4),
+ std::make_pair(5, 5), std::make_pair(8, 8),
+ std::make_pair(10, 10)));
+ }
}
TEST(FlatMap, InsertFindSize) {
diff --git a/base/containers/flat_set.h b/base/containers/flat_set.h
index e0a7ef7..da19034 100644
--- a/base/containers/flat_set.h
+++ b/base/containers/flat_set.h
@@ -11,8 +11,9 @@
// Overview:
// This file implements flat_set container. It is an alternative to standard
-// sorted containers that stores it's elements in contiguous memory (current
-// version uses sorted std::vector).
+// sorted containers that stores it's elements in contiguous memory using a
+// std::vector.
+//
// Discussion that preceded introduction of this container can be found here:
// https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector$20based/chromium-dev/4uQMma9vj9w/HaQ-WvMOAwAJ
//
@@ -24,11 +25,11 @@
// Usage guidance:
// Prefer base::flat_set for:
// * Very small sets, something that is an easy fit for cache. Consider
-// "very small" to be under a 100 32bit integers.
+// "very small" to be under 100 32bit integers.
// * Sets that are built once (using flat_set::flat_set(first, last)). Consider
// collecting all data in a vector and then building flat_set out of it.
-// TODO(dyaroshev): improve the interface to better support this pattern
-// (crbug.com/682254).
+// Using the constructor that takes a moved vector allows you to re-use
+// storage.
// * Sets where mutating happens in big bulks: to erase multiple elements, use
// base::EraseIf() rather than repeated single-element removal. Insertion is
// harder - consider set operations or building a new vector. Set operations
@@ -40,7 +41,9 @@
// * Set operations (union/intersect etc).
//
// Prefer to build a new flat_set from a std::vector (or similar) instead of
-// calling insert() repeatedly, which would have O(size^2) complexity.
+// calling insert() repeatedly, which would have O(size^2) complexity. The
+// constructor that can accept a moved vector (not required to be sorted) is
+// the most efficient.
//
// TODO(dyaroshev): develop standalone benchmarks to find performance boundaries
// for different types of sets crbug.com/682215.
@@ -57,12 +60,6 @@
// - we ask (for now) to assume that move operations invalidate iterators.
// TODO(dyaroshev): Research the possibility of using a small buffer
// optimization crbug.com/682240.
-// * Constructor sorts elements in a non-stable manner (unlike std::set). So
-// among equivalent (with respect to provided compare) elements passed to
-// the constructor it is unspecified with one will end up in the set.
-// However insert()/emplace() methods are stable with respect to already
-// inserted elements - an element that is already in the set will not be
-// replaced.
// * allocator support is not implemented.
// * insert(first, last) and insert(std::initializer_list) are not
// implemented (see Notes section).
@@ -82,6 +79,15 @@
// flat_tree.h for more details for most of these functions. As a quick
// reference, the functions available are:
//
+// Constructors (inputs need not be sorted):
+// flat_set(InputIterator first, InputIterator last,
+// FlatContainerDupes, const Compare& compare = Compare());
+// flat_set(const flat_set&);
+// flat_set(flat_set&&);
+// flat_set(std::vector<Key>, FlatContainerDupes); // Re-use storage.
+// flat_set(std::initializer_list<value_type> ilist,
+// const Compare& comp = Compare());
+//
// Assignment functions:
// flat_set& operator=(const flat_set&);
// flat_set& operator=(flat_set&&);
@@ -137,7 +143,7 @@
// iterator upper_bound(const Key&);
// const_iterator upper_bound(const Key&) const;
//
-// General functions
+// General functions:
// void swap(flat_set&&)
//
// Non-member operators:
diff --git a/base/containers/flat_set_unittest.cc b/base/containers/flat_set_unittest.cc
index 26bb4da..dc024fc 100644
--- a/base/containers/flat_set_unittest.cc
+++ b/base/containers/flat_set_unittest.cc
@@ -37,15 +37,16 @@
TEST(FlatSet, RangeConstructor) {
flat_set<int>::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
- flat_set<int> cont(std::begin(input_vals), std::end(input_vals));
+ flat_set<int> cont(std::begin(input_vals), std::end(input_vals),
+ base::KEEP_FIRST_OF_DUPES);
EXPECT_THAT(cont, ElementsAre(1, 2, 3));
}
TEST(FlatSet, MoveConstructor) {
int input_range[] = {1, 2, 3, 4};
- flat_set<MoveOnlyInt> original(std::begin(input_range),
- std::end(input_range));
+ flat_set<MoveOnlyInt> original(std::begin(input_range), std::end(input_range),
+ base::KEEP_FIRST_OF_DUPES);
flat_set<MoveOnlyInt> moved(std::move(original));
EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
@@ -55,7 +56,7 @@
}
TEST(FlatSet, InitializerListConstructor) {
- flat_set<int> cont{1, 2, 3, 4, 5, 6, 10, 8};
+ flat_set<int> cont({1, 2, 3, 4, 5, 6, 10, 8}, KEEP_FIRST_OF_DUPES);
EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
}
diff --git a/base/containers/flat_tree.h b/base/containers/flat_tree.h
index fc9482d..c3a234f 100644
--- a/base/containers/flat_tree.h
+++ b/base/containers/flat_tree.h
@@ -9,8 +9,39 @@
#include <vector>
namespace base {
+
+enum FlatContainerDupes {
+ KEEP_FIRST_OF_DUPES,
+ KEEP_LAST_OF_DUPES,
+};
+
namespace internal {
+// This algorithm is like unique() from the standard library except it
+// selects only the last of consecutive values instead of the first.
+template <class Iterator, class BinaryPredicate>
+Iterator LastUnique(Iterator first, Iterator last, BinaryPredicate compare) {
+ if (first == last)
+ return last;
+
+ Iterator dest = first;
+ Iterator cur = first;
+ Iterator prev = cur;
+ while (++cur != last) {
+ if (!compare(*prev, *cur)) {
+ // Non-identical one.
+ if (dest != prev)
+ *dest = std::move(*prev);
+ ++dest;
+ }
+ prev = cur;
+ }
+
+ if (dest != prev)
+ *dest = std::move(*prev);
+ return ++dest;
+}
+
// Implementation of a sorted vector for backing flat_set and flat_map. Do not
// use directly.
//
@@ -24,7 +55,6 @@
// const Key& operator()(const Value&).
template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
class flat_tree {
- public:
private:
using underlying_type = std::vector<Value>;
@@ -71,21 +101,28 @@
// length).
//
// Assume that move constructors invalidate iterators and references.
+ //
+ // The constructors that take ranges, lists, and vectors do not require that
+ // the input be sorted.
flat_tree();
explicit flat_tree(const key_compare& comp);
- // Not stable in the presence of duplicates in the initializer list.
template <class InputIterator>
flat_tree(InputIterator first,
InputIterator last,
+ FlatContainerDupes dupe_handling,
const key_compare& comp = key_compare());
flat_tree(const flat_tree&);
flat_tree(flat_tree&&);
- // Not stable in the presence of duplicates in the initializer list.
+ flat_tree(std::vector<value_type> items,
+ FlatContainerDupes dupe_handling,
+ const key_compare& comp = key_compare());
+
flat_tree(std::initializer_list<value_type> ilist,
+ FlatContainerDupes dupe_handling,
const key_compare& comp = key_compare());
~flat_tree();
@@ -97,7 +134,7 @@
flat_tree& operator=(const flat_tree&);
flat_tree& operator=(flat_tree&&);
- // Not stable in the presence of duplicates in the initializer list.
+ // Takes the first if there are duplicates in the initializer list.
flat_tree& operator=(std::initializer_list<value_type> ilist);
// --------------------------------------------------------------------------
@@ -276,17 +313,26 @@
return std::next(begin(), distance);
}
- void sort_and_unique() {
- // std::set sorts elements preserving stability because it doesn't have any
- // performance wins in not doing that. We do, so we use an unstable sort.
- std::sort(begin(), end(), impl_.get_value_comp());
- erase(std::unique(begin(), end(),
- [this](const value_type& lhs, const value_type& rhs) {
- // lhs is already <= rhs due to sort, therefore
- // !(lhs < rhs) <=> lhs == rhs.
- return !impl_.get_value_comp()(lhs, rhs);
- }),
- end());
+ void sort_and_unique(FlatContainerDupes dupes) {
+ // Preserve stability for the unique code below.
+ std::stable_sort(begin(), end(), impl_.get_value_comp());
+
+ auto comparator = [this](const value_type& lhs, const value_type& rhs) {
+ // lhs is already <= rhs due to sort, therefore
+ // !(lhs < rhs) <=> lhs == rhs.
+ return !impl_.get_value_comp()(lhs, rhs);
+ };
+
+ iterator erase_after;
+ switch (dupes) {
+ case KEEP_FIRST_OF_DUPES:
+ erase_after = std::unique(begin(), end(), comparator);
+ break;
+ case KEEP_LAST_OF_DUPES:
+ erase_after = LastUnique(begin(), end(), comparator);
+ break;
+ }
+ erase(erase_after, end());
}
// To support comparators that may not be possible to default-construct, we
@@ -325,9 +371,10 @@
flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
InputIterator first,
InputIterator last,
+ FlatContainerDupes dupe_handling,
const KeyCompare& comp)
: impl_(comp, first, last) {
- sort_and_unique();
+ sort_and_unique(dupe_handling);
}
template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
@@ -340,9 +387,19 @@
template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
- std::initializer_list<value_type> ilist,
+ std::vector<value_type> items,
+ FlatContainerDupes dupe_handling,
const KeyCompare& comp)
- : flat_tree(std::begin(ilist), std::end(ilist), comp) {}
+ : impl_(comp, std::move(items)) {
+ sort_and_unique(dupe_handling);
+}
+
+template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
+flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
+ std::initializer_list<value_type> ilist,
+ FlatContainerDupes dupe_handling,
+ const KeyCompare& comp)
+ : flat_tree(std::begin(ilist), std::end(ilist), dupe_handling, comp) {}
template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::~flat_tree() = default;
@@ -362,7 +419,7 @@
auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(
std::initializer_list<value_type> ilist) -> flat_tree& {
impl_.body_ = ilist;
- sort_and_unique();
+ sort_and_unique(KEEP_FIRST_OF_DUPES);
return *this;
}
diff --git a/base/containers/flat_tree_unittest.cc b/base/containers/flat_tree_unittest.cc
index 91a853c..e3a8f87 100644
--- a/base/containers/flat_tree_unittest.cc
+++ b/base/containers/flat_tree_unittest.cc
@@ -130,6 +130,13 @@
}
};
+template <class PairType>
+struct LessByFirst {
+ bool operator()(const PairType& lhs, const PairType& rhs) const {
+ return lhs.first < rhs.first;
+ }
+};
+
// Common test trees.
// TODO(dyaroshev): replace less<int> with less<>, once we have it
@@ -138,6 +145,11 @@
flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>;
using IntTree =
flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>;
+using IntPair = std::pair<int, int>;
+using IntPairTree = flat_tree<IntPair,
+ IntPair,
+ GetKeyFromValueIdentity<IntPair>,
+ LessByFirst<IntPair>>;
using MoveOnlyTree = flat_tree<MoveOnlyInt,
MoveOnlyInt,
GetKeyFromValueIdentity<MoveOnlyInt>,
@@ -158,6 +170,68 @@
} // namespace
+TEST(FlatTree, LastUnique) {
+ using Pair = std::pair<int, int>;
+ using Vect = std::vector<Pair>;
+
+ auto cmp = [](const Pair& lhs, const Pair& rhs) {
+ return lhs.first == rhs.first;
+ };
+
+ // Empty case.
+ Vect empty;
+ EXPECT_EQ(empty.end(), LastUnique(empty.begin(), empty.end(), cmp));
+
+ // Single element.
+ Vect one;
+ one.push_back(Pair(1, 1));
+ EXPECT_EQ(one.end(), LastUnique(one.begin(), one.end(), cmp));
+ ASSERT_EQ(1u, one.size());
+ EXPECT_THAT(one, ElementsAre(Pair(1, 1)));
+
+ // Two elements, already unique.
+ Vect two_u;
+ two_u.push_back(Pair(1, 1));
+ two_u.push_back(Pair(2, 2));
+ EXPECT_EQ(two_u.end(), LastUnique(two_u.begin(), two_u.end(), cmp));
+ EXPECT_THAT(two_u, ElementsAre(Pair(1, 1), Pair(2, 2)));
+
+ // Two elements, dupes.
+ Vect two_d;
+ two_d.push_back(Pair(1, 1));
+ two_d.push_back(Pair(1, 2));
+ auto last = LastUnique(two_d.begin(), two_d.end(), cmp);
+ EXPECT_EQ(two_d.begin() + 1, last);
+ two_d.erase(last, two_d.end());
+ EXPECT_THAT(two_d, ElementsAre(Pair(1, 2)));
+
+ // Non-dupes, dupes, non-dupes.
+ Vect ndn;
+ ndn.push_back(Pair(1, 1));
+ ndn.push_back(Pair(2, 1));
+ ndn.push_back(Pair(2, 2));
+ ndn.push_back(Pair(2, 3));
+ ndn.push_back(Pair(3, 1));
+ last = LastUnique(ndn.begin(), ndn.end(), cmp);
+ EXPECT_EQ(ndn.begin() + 3, last);
+ ndn.erase(last, ndn.end());
+ EXPECT_THAT(ndn, ElementsAre(Pair(1, 1), Pair(2, 3), Pair(3, 1)));
+
+ // Dupes, non-dupes, dupes.
+ Vect dnd;
+ dnd.push_back(Pair(1, 1));
+ dnd.push_back(Pair(1, 2));
+ dnd.push_back(Pair(1, 3));
+ dnd.push_back(Pair(2, 1));
+ dnd.push_back(Pair(3, 1));
+ dnd.push_back(Pair(3, 2));
+ dnd.push_back(Pair(3, 3));
+ last = LastUnique(dnd.begin(), dnd.end(), cmp);
+ EXPECT_EQ(dnd.begin() + 3, last);
+ dnd.erase(last, dnd.end());
+ EXPECT_THAT(dnd, ElementsAre(Pair(1, 3), Pair(2, 1), Pair(3, 3)));
+}
+
// ----------------------------------------------------------------------------
// Class.
@@ -181,36 +255,31 @@
TEST(FlatTree, Stability) {
using Pair = std::pair<int, int>;
- struct LessByFirst {
- bool operator()(const Pair& lhs, const Pair& rhs) const {
- return lhs.first < rhs.first;
- }
- };
-
using Tree =
- flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst>;
+ flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst<Pair>>;
- // Constructors are not stable.
- Tree cont{{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}};
+ // Constructors are stable.
+ Tree cont({{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}},
+ KEEP_FIRST_OF_DUPES);
- auto NoneOfSecondsAreTwo = [&cont] {
- return std::none_of(cont.begin(), cont.end(),
- [](const Pair& elem) { return elem.second == 2; });
+ auto AllOfSecondsAreZero = [&cont] {
+ return std::all_of(cont.begin(), cont.end(),
+ [](const Pair& elem) { return elem.second == 0; });
};
+ EXPECT_TRUE(AllOfSecondsAreZero()) << "constructor should be stable";
+
// Should not replace existing.
cont.insert(Pair(0, 2));
cont.insert(Pair(1, 2));
cont.insert(Pair(2, 2));
- EXPECT_TRUE(NoneOfSecondsAreTwo())
- << "insert should be stable with respect to constructor";
+ EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
cont.insert(Pair(3, 0));
cont.insert(Pair(3, 2));
- EXPECT_TRUE(NoneOfSecondsAreTwo())
- << "insert should be stable with respect to previous insert";
+ EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
}
// ----------------------------------------------------------------------------
@@ -263,16 +332,26 @@
}
// flat_tree(InputIterator first,
-// InputIterator last,
-// const Compare& comp = Compare())
+// InputIterator last,
+// FlatContainerDupes dupe_handling,
+// const Compare& comp = Compare())
TEST(FlatTree, RangeConstructor) {
{
- IntTree::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
+ IntPair input_vals[] = {{1, 1}, {1, 2}, {2, 1}, {2, 2}, {1, 3},
+ {2, 3}, {3, 1}, {3, 2}, {3, 3}};
- IntTree cont(MakeInputIterator(std::begin(input_vals)),
- MakeInputIterator(std::end(input_vals)));
- EXPECT_THAT(cont, ElementsAre(1, 2, 3));
+ IntPairTree first_of(MakeInputIterator(std::begin(input_vals)),
+ MakeInputIterator(std::end(input_vals)),
+ KEEP_FIRST_OF_DUPES);
+ EXPECT_THAT(first_of,
+ ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1)));
+
+ IntPairTree last_of(MakeInputIterator(std::begin(input_vals)),
+ MakeInputIterator(std::end(input_vals)),
+ KEEP_LAST_OF_DUPES);
+ EXPECT_THAT(last_of,
+ ElementsAre(IntPair(1, 3), IntPair(2, 3), IntPair(3, 3)));
}
{
TreeWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2,
@@ -280,6 +359,7 @@
TreeWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)),
MakeInputIterator(std::end(input_vals)),
+ KEEP_FIRST_OF_DUPES,
NonDefaultConstructibleCompare(0));
EXPECT_THAT(cont, ElementsAre(1, 2, 3));
}
@@ -288,7 +368,7 @@
// flat_tree(const flat_tree& x)
TEST(FlatTree, CopyConstructor) {
- IntTree original{1, 2, 3, 4};
+ IntTree original({1, 2, 3, 4}, KEEP_FIRST_OF_DUPES);
IntTree copied(original);
EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
@@ -303,7 +383,8 @@
TEST(FlatTree, MoveConstructor) {
int input_range[] = {1, 2, 3, 4};
- MoveOnlyTree original(std::begin(input_range), std::end(input_range));
+ MoveOnlyTree original(std::begin(input_range), std::end(input_range),
+ KEEP_FIRST_OF_DUPES);
MoveOnlyTree moved(std::move(original));
EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
@@ -312,19 +393,65 @@
EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
}
-// flat_tree(std::initializer_list<value_type> ilist,
+// flat_tree(std::vector<value_type>, FlatContainerDupes dupe_handling)
+
+TEST(FlatTree, VectorConstructor) {
+ using Pair = std::pair<int, MoveOnlyInt>;
+
+ // Construct an unsorted vector with a duplicate item in it. Sorted by the
+ // first item, the second allows us to test for stability. Using a move
+ // only type to ensure the vector is not copied.
+ std::vector<Pair> storage;
+ storage.push_back(Pair(2, MoveOnlyInt(0)));
+ storage.push_back(Pair(1, MoveOnlyInt(0)));
+ storage.push_back(Pair(2, MoveOnlyInt(1)));
+
+ using Tree =
+ flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst<Pair>>;
+ Tree tree(std::move(storage), KEEP_FIRST_OF_DUPES);
+
+ // The list should be two items long, with only the first "2" saved.
+ ASSERT_EQ(2u, tree.size());
+ const Pair& zeroth = *tree.begin();
+ ASSERT_EQ(1, zeroth.first);
+ ASSERT_EQ(0, zeroth.second.data());
+
+ const Pair& first = *(tree.begin() + 1);
+ ASSERT_EQ(2, first.first);
+ ASSERT_EQ(0, first.second.data());
+
+ // Test KEEP_LAST_OF_DUPES with a simple vector constructor.
+ std::vector<IntPair> int_storage{{1, 1}, {1, 2}, {2, 1}};
+ IntPairTree int_tree(std::move(int_storage), KEEP_LAST_OF_DUPES);
+ EXPECT_THAT(int_tree, ElementsAre(IntPair(1, 2), IntPair(2, 1)));
+}
+
+// flat_tree(std::initializer_list<value_type> ilist,
+// FlatContainerDupes dupe_handling,
// const Compare& comp = Compare())
TEST(FlatTree, InitializerListConstructor) {
{
- IntTree cont{1, 2, 3, 4, 5, 6, 10, 8};
+ IntTree cont({1, 2, 3, 4, 5, 6, 10, 8}, KEEP_FIRST_OF_DUPES);
EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
}
{
- TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8},
+ IntTree cont({1, 2, 3, 4, 5, 6, 10, 8}, KEEP_FIRST_OF_DUPES);
+ EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
+ }
+ {
+ TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8}, KEEP_FIRST_OF_DUPES,
NonDefaultConstructibleCompare(0));
EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
}
+ {
+ IntPairTree first_of({{1, 1}, {2, 1}, {1, 2}}, KEEP_FIRST_OF_DUPES);
+ EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
+ }
+ {
+ IntPairTree last_of({{1, 1}, {2, 1}, {1, 2}}, KEEP_LAST_OF_DUPES);
+ EXPECT_THAT(last_of, ElementsAre(IntPair(1, 2), IntPair(2, 1)));
+ }
}
// ----------------------------------------------------------------------------
@@ -333,7 +460,7 @@
// flat_tree& operator=(const flat_tree&)
TEST(FlatTree, CopyAssignable) {
- IntTree original{1, 2, 3, 4};
+ IntTree original({1, 2, 3, 4}, KEEP_FIRST_OF_DUPES);
IntTree copied;
copied = original;
@@ -347,7 +474,8 @@
TEST(FlatTree, MoveAssignable) {
int input_range[] = {1, 2, 3, 4};
- MoveOnlyTree original(std::begin(input_range), std::end(input_range));
+ MoveOnlyTree original(std::begin(input_range), std::end(input_range),
+ KEEP_FIRST_OF_DUPES);
MoveOnlyTree moved;
moved = std::move(original);
@@ -360,7 +488,7 @@
// flat_tree& operator=(std::initializer_list<value_type> ilist)
TEST(FlatTree, InitializerListAssignable) {
- IntTree cont{0};
+ IntTree cont({0}, KEEP_FIRST_OF_DUPES);
cont = {1, 2, 3, 4, 5, 6, 10, 8};
EXPECT_EQ(0U, cont.count(0));
@@ -373,7 +501,7 @@
// void reserve(size_type new_capacity)
TEST(FlatTree, Reserve) {
- IntTree cont{1, 2, 3};
+ IntTree cont({1, 2, 3}, KEEP_FIRST_OF_DUPES);
cont.reserve(5);
EXPECT_LE(5U, cont.capacity());
@@ -382,7 +510,7 @@
// size_type capacity() const
TEST(FlatTree, Capacity) {
- IntTree cont{1, 2, 3};
+ IntTree cont({1, 2, 3}, KEEP_FIRST_OF_DUPES);
EXPECT_LE(cont.size(), cont.capacity());
cont.reserve(5);
@@ -392,7 +520,7 @@
// void shrink_to_fit()
TEST(FlatTree, ShrinkToFit) {
- IntTree cont{1, 2, 3};
+ IntTree cont({1, 2, 3}, KEEP_FIRST_OF_DUPES);
IntTree::size_type capacity_before = cont.capacity();
cont.shrink_to_fit();
@@ -405,7 +533,7 @@
// void clear()
TEST(FlatTree, Clear) {
- IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
+ IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
cont.clear();
EXPECT_THAT(cont, ElementsAre());
}
@@ -461,7 +589,7 @@
// const_reverse_iterator crend() const
TEST(FlatTree, Iterators) {
- IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
+ IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
auto size = static_cast<IntTree::difference_type>(cont.size());
@@ -684,7 +812,7 @@
// iterator erase(const_iterator position_hint)
TEST(FlatTree, ErasePosition) {
- IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
+ IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
IntTree::iterator it = cont.erase(std::next(cont.cbegin(), 3));
EXPECT_EQ(std::next(cont.begin(), 3), it);
@@ -722,7 +850,7 @@
// iterator erase(const_iterator first, const_iterator last)
TEST(FlatTree, EraseRange) {
- IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
+ IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
IntTree::iterator it =
cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5));
@@ -749,7 +877,7 @@
// size_type erase(const key_type& key)
TEST(FlatTree, EraseKey) {
- IntTree cont{1, 2, 3, 4, 5, 6, 7, 8};
+ IntTree cont({1, 2, 3, 4, 5, 6, 7, 8}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(0U, cont.erase(9));
EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8));
@@ -785,7 +913,7 @@
// key_compare key_comp() const
TEST(FlatTree, KeyComp) {
- ReversedTree cont{1, 2, 3, 4, 5};
+ ReversedTree cont({1, 2, 3, 4, 5}, KEEP_FIRST_OF_DUPES);
EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp()));
int new_elements[] = {6, 7, 8, 9, 10};
@@ -797,7 +925,7 @@
// value_compare value_comp() const
TEST(FlatTree, ValueComp) {
- ReversedTree cont{1, 2, 3, 4, 5};
+ ReversedTree cont({1, 2, 3, 4, 5}, KEEP_FIRST_OF_DUPES);
EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp()));
int new_elements[] = {6, 7, 8, 9, 10};
@@ -813,7 +941,7 @@
TEST(FlatTree, Count) {
{
- const IntTree cont{5, 6, 7, 8, 9, 10, 11, 12};
+ const IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(1U, cont.count(5));
EXPECT_EQ(1U, cont.count(6));
@@ -826,7 +954,8 @@
EXPECT_EQ(0U, cont.count(4));
}
{
- const IntTreeWithLess cont{5, 6, 7, 8, 9, 10, 11, 12};
+ const IntTreeWithLess cont({5, 6, 7, 8, 9, 10, 11, 12},
+ KEEP_FIRST_OF_DUPES);
EXPECT_EQ(1U, cont.count(5));
EXPECT_EQ(1U, cont.count(6));
@@ -845,7 +974,7 @@
TEST(FlatTree, Find) {
{
- IntTree cont{5, 6, 7, 8, 9, 10, 11, 12};
+ IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(cont.begin(), cont.find(5));
EXPECT_EQ(std::next(cont.begin()), cont.find(6));
@@ -858,7 +987,7 @@
EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
}
{
- const IntTree cont{5, 6, 7, 8, 9, 10, 11, 12};
+ const IntTree cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(cont.begin(), cont.find(5));
EXPECT_EQ(std::next(cont.begin()), cont.find(6));
@@ -871,7 +1000,7 @@
EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
}
{
- IntTreeWithLess cont{5, 6, 7, 8, 9, 10, 11, 12};
+ IntTreeWithLess cont({5, 6, 7, 8, 9, 10, 11, 12}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(cont.begin(), cont.find(5));
EXPECT_EQ(std::next(cont.begin()), cont.find(6));
@@ -890,7 +1019,7 @@
TEST(FlatTree, EqualRange) {
{
- IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+ IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
std::pair<IntTree::iterator, IntTree::iterator> result =
cont.equal_range(5);
@@ -946,7 +1075,7 @@
EXPECT_EQ(std::next(cont.begin(), 8), result.second);
}
{
- const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+ const IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
std::pair<IntTree::const_iterator, IntTree::const_iterator> result =
cont.equal_range(5);
@@ -1002,7 +1131,7 @@
EXPECT_EQ(std::next(cont.begin(), 8), result.second);
}
{
- IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19};
+ IntTreeWithLess cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
std::pair<IntTree::iterator, IntTree::iterator> result =
cont.equal_range(5);
@@ -1064,7 +1193,7 @@
TEST(FlatTree, LowerBound) {
{
- IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+ IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(cont.begin(), cont.lower_bound(5));
EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
@@ -1085,7 +1214,7 @@
EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
}
{
- const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+ const IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(cont.begin(), cont.lower_bound(5));
EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
@@ -1106,7 +1235,7 @@
EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
}
{
- IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19};
+ IntTreeWithLess cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(cont.begin(), cont.lower_bound(5));
EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
@@ -1133,7 +1262,7 @@
TEST(FlatTree, UpperBound) {
{
- IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+ IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
@@ -1154,7 +1283,7 @@
EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
}
{
- const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19};
+ const IntTree cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
@@ -1175,7 +1304,7 @@
EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
}
{
- IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19};
+ IntTreeWithLess cont({5, 7, 9, 11, 13, 15, 17, 19}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
@@ -1204,8 +1333,8 @@
// void swap(flat_tree& lhs, flat_tree& rhs)
TEST(FlatTreeOurs, Swap) {
- IntTree x{1, 2, 3};
- IntTree y{4};
+ IntTree x({1, 2, 3}, KEEP_FIRST_OF_DUPES);
+ IntTree y({4}, KEEP_FIRST_OF_DUPES);
swap(x, y);
EXPECT_THAT(x, ElementsAre(4));
EXPECT_THAT(y, ElementsAre(1, 2, 3));
@@ -1224,9 +1353,9 @@
TEST(FlatTree, Comparison) {
// Provided comparator does not participate in comparison.
- ReversedTree biggest{3};
- ReversedTree smallest{1};
- ReversedTree middle{1, 2};
+ ReversedTree biggest({3}, KEEP_FIRST_OF_DUPES);
+ ReversedTree smallest({1}, KEEP_FIRST_OF_DUPES);
+ ReversedTree middle({1, 2}, KEEP_FIRST_OF_DUPES);
EXPECT_EQ(biggest, biggest);
EXPECT_NE(biggest, smallest);