Make flat containers stable, allow constructing from vector.

base/containers/flat_set.h

Index: base/containers/flat_set.h
diff --git a/base/containers/flat_set.h b/base/containers/flat_set.h
index e0a7ef714db05ef32ef9b4f38ad56ee3d9a98e42..0a780f445344a86cca94ea429581706a0605325e 100644
--- a/base/containers/flat_set.h
+++ b/base/containers/flat_set.h
@@ -11,8 +11,9 @@ namespace base {
 
 // 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 @@ namespace base {
 // Usage guidance:

[danakj, 2017/04/05 21:33:43]

Noticing that guidance of some sort like this is conspicuously missing from
flat_map.h

 // 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 cosntructor that takes a vector rvalue allows you to re-use

[danakj, 2017/04/05 21:33:43]

no rvalue

[brettw, 2017/04/07 21:59:03]

Done.

+//    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 @@ namespace base {
 //  * 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 moves a vector (not required to be sorted) is the most

[danakj, 2017/04/05 21:33:43]

receives a vector?

[brettw, 2017/04/07 21:59:04]

Done.

+// efficient.
 //
 // TODO(dyaroshev): develop standalone benchmarks to find performance boundaries
 // for different types of sets crbug.com/682215.
@@ -57,12 +60,6 @@ namespace base {
 //     - 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 @@ namespace base {
 // 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, first of duplicates will be kept):

[danakj, 2017/04/05 21:33:42]

Like in the map, the comments saying first is kept seems wrong

[brettw, 2017/04/07 21:59:04]

Done.

+//   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 @@ namespace base {
 //   iterator                 upper_bound(const Key&);
 //   const_iterator           upper_bound(const Key&) const;
 //
-// General functions
+// General functions:
 //   void swap(flat_set&&)
 //
 // Non-member operators: