Make flat containers stable, allow constructing from vector.

base/containers/flat_map.h

 // Copyright 2017 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.
 
 #ifndef BASE_CONTAINERS_FLAT_MAP_H_
 #define BASE_CONTAINERS_FLAT_MAP_H_
 
 #include <utility>
 
 #include "base/containers/flat_tree.h"
@@ skipping 20 matching lines @@
 // sorted containers that stores its elements in contiguous memory (a vector).
 //
 // Additional documentation and usage advice is in flat_set.h.
 //
 // DOCUMENTATION
 //
 // Most of the core functionality is inherited from flat_tree. Please see
 // 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&&);
 //   flat_map& operator=(initializer_list<pair<Key, Mapped>>);
 //
 // Memory management functions:
 //   void   reserve(size_t);
 //   size_t capacity() const;
 //   void   shrink_to_fit();
 //
@@ skipping 37 matching lines @@
 // Search functions:
 //   size_t                   count(const Key&) const;
 //   iterator                 find(const Key&);
 //   const_iterator           find(const Key&) const;
 //   pair<iterator, iterator> equal_range(Key&)
 //   iterator                 lower_bound(const Key&);
 //   const_iterator           lower_bound(const Key&) const;
 //   iterator                 upper_bound(const Key&);
 //   const_iterator           upper_bound(const Key&) const;
 //
-// General functions
+// General functions:
 //   void swap(flat_map&&)
 //
 // Non-member operators:
 //   bool operator==(const flat_map&, const flat_map);
 //   bool operator!=(const flat_map&, const flat_map);
 //   bool operator<(const flat_map&, const flat_map);
 //   bool operator>(const flat_map&, const flat_map);
 //   bool operator>=(const flat_map&, const flat_map);
 //   bool operator<=(const flat_map&, const flat_map);
 //
@@ skipping 18 matching lines @@
   using value_type = typename tree::value_type;
 
   // --------------------------------------------------------------------------
   // Lifetime.
   //
   // Constructors that take range guarantee O(N * log(N)) + O(N) complexity
   // (N is a range length). Thr range constructors are NOT stable. If there are
   // 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();
 
   // --------------------------------------------------------------------------
   // Assignments.
   //
   // Assume that move assignment invalidates iterators and references.
 
   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);
 
   // --------------------------------------------------------------------------
   // Map-specific insert operations.
   //
   // Normal insert() functions are inherited from flat_tree.
   //
   // Assume that every operation invalidates iterators and references.
   // Insertion of one element can take O(size).
 
@@ skipping 16 matching lines @@
 template <class Key, class Mapped, class Compare>
 flat_map<Key, Mapped, Compare>::flat_map() = default;
 
 template <class Key, class Mapped, class Compare>
 flat_map<Key, Mapped, Compare>::flat_map(const Compare& comp) : tree(comp) {}
 
 template <class Key, class Mapped, class Compare>
 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;
 
 template <class Key, class Mapped, class Compare>
 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;
 
 // ----------------------------------------------------------------------------
 // Assignments.
 
 template <class Key, class Mapped, class Compare>
 auto flat_map<Key, Mapped, Compare>::operator=(const flat_map&)
     -> flat_map& = default;
@@ skipping 33 matching lines @@
 // General operations.
 
 template <class Key, class Mapped, class Compare>
 void flat_map<Key, Mapped, Compare>::swap(flat_map& other) {
   tree::swap(other);
 }
 
 }  // namespace base
 
 #endif  // BASE_CONTAINERS_FLAT_MAP_H_