Add a flat_map container

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/logging.h"
+
+namespace base {
+
+namespace internal {
+
+// An implementation of the flat_set 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
+
+// Overview:
+// This file implements flat_map container. It is an alternative to standard
+// sorted containers that stores its elements in contiguous memory (a vector).
+//
+// Additional documentation and usage advice is in flat_set.h.
+//
+// Most of the core functionality is inherited from flat_tree.
+template <class Key, class Mapped, class Compare = std::less<Key>>
+// 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<
+      Key,
+      std::pair<Key, Mapped>,
+      ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>,
+      Compare>;
+
+ public:
+  using mapped_type = Mapped;
+  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.
+
+  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,
+           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::initializer_list<value_type> ilist,
+           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.
+  flat_map& operator=(std::initializer_list<value_type> ilist);
+
+  // --------------------------------------------------------------------------
+  // Map-specific insert operations.
+  //
+  // Normal insert() functions are inherited from flat_tree.

[danakj, 2017/03/21 20:28:55]

What do you think of making everything in flat_tree protected and putting
"using" lines here so that the whole API is available to be seen in this one
file?

[brettw, 2017/03/21 23:19:54]

I started doing this to see what it looked like. I agree with the concern that
this class is harder to understand since the API is spread across two files. But
with the usings I think you end up with:

  using tree::size;
  using tree::insert;
  using tree::begin;
  using tree::cend;

which I don't think is much improvement. You still need to look at the tree file
to see what insert looks like. It does at least tell you what functions are
available, but the complexity-to-value ratio is not great (since I would also
have to implement flat_set as a separate class again).

What I ended up doing was writing a quick reference in both flat_set and
flat_map of the available functions. A downside is that it might get
out-of-date. But I think then the reference will be there where people look for
it.

Since it's a comment, I could give a more useful function signatures than just
the name, but since it's not real code I could omit some of the ugly template
goop so I think it's easier to follow than the alternatives.

[danakj, 2017/03/21 23:25:01]

FWIW with a using tree::size; in codesearch you'd have something to click to
take you to the actual declaration. But having the full signature seems pretty
cool too.

+  //
+  // Assume that every operation invalidates iterators and references.
+  // Insertion of one element can take O(size).
+
+  mapped_type& operator[](const Key& key);
+  mapped_type& operator[](Key&& key);
+
+  // CHECK()s if the element does not exist.

[danakj, 2017/03/21 20:28:55]

I think it'd be nice to instead word this in terms like "Only valid to be called
if |key| exists in the map, will not add |key| to the map." or so. That
expresses the intent and use case rather than the implementation.

[brettw, 2017/03/21 23:19:54]

I'm thinking that we should remove at() entirely. Thinking about code bloat, the
CHECK will generate like 120 bytes of code (if I recall correctly) for something
that should never happen. This indicates that maybe we should be using a DCHECK,
but I'm reluctant to ever knowingly return invalid references.

The only use for at() is when you have a const object that you know contains the
value and you don't want to bother with find(). This is something that's easy to
add later if we change our minds.

[danakj, 2017/03/21 23:25:01]

sgtm

+  mapped_type& at(const Key& key);
+  const mapped_type& at(const Key& key) const;
+
+  // --------------------------------------------------------------------------
+  // General operations.
+  //
+  // Assume that swap invalidates iterators and references.
+
+  void swap(flat_map& other);
+
+  friend void swap(flat_map& lhs, flat_map& rhs) { lhs.swap(rhs); }
+};
+
+// ----------------------------------------------------------------------------
+// Lifetime.
+
+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,
+                                         const Compare& comp)
+    : tree(first, last, 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::initializer_list<value_type> ilist,
+    const Compare& comp)
+    : flat_map(std::begin(ilist), std::end(ilist), 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;
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::operator=(flat_map &&)
+    -> flat_map& = default;
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::operator=(
+    std::initializer_list<value_type> ilist) -> flat_map& {
+  tree::operator=(ilist);
+  return *this;
+}
+
+// ----------------------------------------------------------------------------
+// Insert operations.
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::operator[](const Key& key) -> Mapped& {
+  typename tree::iterator found = tree::lower_bound(key);
+  if (found == tree::end() || tree::key_comp()(key, found->first))
+    found = unsafe_emplace(found, key, Mapped());
+  return found->second;
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::operator[](Key&& key) -> Mapped& {
+  const Key& key_ref = key;
+  typename tree::iterator found = tree::lower_bound(key_ref);
+  if (found == tree::end() || tree::key_comp()(key, found->first))
+    found = tree::unsafe_emplace(found, std::move(key), Mapped());
+  return found->second;
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::at(const Key& key) -> mapped_type& {
+  typename tree::iterator found = tree::find(key);
+  CHECK(found != tree::end());

[danakj, 2017/03/21 20:28:56]

why did you choose CHECK instead of DCHECK? This would crash shortly after on
trying to use *end() anyway, right? And DCHECK would be similar to assert() in
the STL without adding strings to the binary.

[dyaroshev, 2017/03/21 20:34:46]

I suggested this.
This is consistent with std::map - it throws an exception.
base::Value does a check too:
https://cs.chromium.org/chromium/src/base/values.cc?q=values.cc&l=221
Essentially at() is a strange method but I think we should be consistent with
the standard.

[danakj, 2017/03/21 21:38:39]

We don't enable exceptions though, so it's not consistent for chrome.

+  return found->second;
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::at(const Key& key) const
+    -> const mapped_type& {
+  typename tree::const_iterator found = tree::find(key);
+  CHECK(found != tree::end());
+  return found->second;
+}
+
+// ----------------------------------------------------------------------------
+// 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_