Improving flat containers interface.

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"
+#include "base/functional.h"
 #include "base/logging.h"
 
 namespace base {
 
 namespace internal {
 
 // An implementation of the flat_tree GetKeyFromValue template parameter that
 // extracts the key as the first element of a pair.
 template <class Key, class Mapped>
 struct GetKeyFromValuePairFirst {
   const Key& operator()(const std::pair<Key, Mapped>& p) const {
     return p.first;
   }
 };
 
 }  // namespace internal
 
 // flat_map is a container with a std::map-like interface that stores its
 // contents in a sorted vector.
 //
 // Please see //base/containers/README.md for an overview of which container
 // to select.
 //
 // PROS
 //
 //  - Good memory locality.
 //  - Low overhead, especially for smaller maps.
 //  - Performance is good for more workloads than you might expect (see
 //    overview link above).
+//  - Supports C++14 set interface.
+//  - Uses base::less which can compare pointers and smart pointers.
 //
 // CONS
 //
 //  - Inserts and removals are O(n).
 //
 // IMPORTANT NOTES
 //
 //  - Iterators are invalidated across mutations.
 //  - If possible, construct a flat_map in one operation by inserting into
 //    a std::vector and moving that vector into the flat_map constructor.
@@ skipping 37 matching lines @@
 //   const_iterator         end() const;
 //   const_iterator         cend() const;
 //   reverse_iterator       rbegin();
 //   const reverse_iterator rbegin() const;
 //   const_reverse_iterator crbegin() const;
 //   reverse_iterator       rend();
 //   const_reverse_iterator rend() const;
 //   const_reverse_iterator crend() const;
 //
 // Insert and accessor functions:
-//   Mapped&              operator[](const Key&);
-//   Mapped&              operator[](Key&&);
-//   pair<iterator, bool> insert(const pair<Key, Mapped>&);
-//   pair<iterator, bool> insert(pair<Key, Mapped>&&);
+//   Mapped&              operator[](const key_type&);
+//   Mapped&              operator[](key_type&&);
+//   pair<iterator, bool> insert(const value_type&);
+//   pair<iterator, bool> insert(value_type&&);
 //   void                 insert(InputIterator first, InputIterator last,
 //                               FlatContainerDupes);
+//   template <typename ...Args>

[brettw, 2017/06/20 18:13:35]

I find these ...Args template lines make it more difficult to follow which is
why I left them out of this quick-reference. It seems obvious enough what's
going on without them.

 //   pair<iterator, bool> emplace(Args&&...);
+//   template <typename ...Args>
 //   iterator             emplace_hint(const_iterator, Args&&...);
 //
 // Erase functions:
+//   iterator erase(iterator);
 //   iterator erase(const_iterator);
 //   iterator erase(const_iterator first, const_iterator& last);
-//   size_t   erase(const Key& key)
+//   template <typename K>
+//   size_t   erase(const K& key)

[brettw, 2017/06/20 18:13:35]

Here and in the ones below we really need the template definition or it makes no
sense, but I think they can all fit on one line. That will solve the weird
ambiguity of where lines begin and end and make it easy to scan down as a
reference.

(These two comments also apply to the other references.)

 //
 // Comparators (see std::map documentation).
 //   key_compare   key_comp() const;
 //   value_compare value_comp() const;
 //
 // 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;
+//   template <typename K>
+//   size_t                   count(const K&) const;
+//   template <typename K>
+//   iterator                 find(const K&);
+//   template <typename K>
+//   const_iterator           find(const K&) const;
+//   template <typename K>
+//   pair<iterator, iterator> equal_range(const K&);
+//   template <typename K>
+//   iterator                 lower_bound(const K&);
+//   template <typename K>
+//   const_iterator           lower_bound(const K&) const;
+//   template <typename K>
+//   iterator                 upper_bound(const K&);
+//   const_iterator           upper_bound(const K&) const;
 //
 // 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);
 //
-template <class Key, class Mapped, class Compare = std::less<Key>>
+template <class Key, class Mapped, class Compare = less>
 // Meets the requirements of Container, AssociativeContainer,
 // ReversibleContainer.
 // Requires: Key is Movable, Compare is a StrictWeakOrdering on Key.
 class flat_map : public ::base::internal::flat_tree<
                      Key,
                      std::pair<Key, Mapped>,
                      ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>,
                      Compare> {
  private:
   using tree = typename ::base::internal::flat_tree<
@@ skipping 152 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_