Add a flat_map container

Desktop / Chromium - brettw [chromium.org] - 22 March 2017 13:56 EDT

This works the same as flat_set but corresponding to a std::map.

The existing flat_set implementation was factored into a base class called flat_tree with a provision to have a potentially different lookup key type than value type, and a way to convert from a value to a key. flat_set and flat_map can be trivially implemented on top of this API.

The existing flat_set tests are moved to flat-tree and some simple type-specific tests were created for the set and map derivations.

flat_tree no longer copies the comparison object except when required (when returned by value_comp()). But this requires that the comparison functor be const which was not the case before.

Review-Url: https://codereview.chromium.org/2715433007 Cr-Commit-Position: refs/heads/master@{#458796}

9816813 Add a flat_map container.
base/BUILD.gn | 5 +
base/containers/container_test_utils.h | 39 +
base/containers/flat_map.h | 266 +++++++
base/containers/flat_map_unittest.cc | 140 ++++
base/containers/flat_set.h | 668 ++---------------
base/containers/flat_set_unittest.cc | 1246 +------------------------------
base/containers/flat_tree.h | 717 ++++++++++++++++++
base/containers/flat_tree_unittest.cc | 1256 ++++++++++++++++++++++++++++++++
8 files changed, 2541 insertions(+), 1796 deletions(-)

Upstream: git.chromium.org


  • Share