Improving flat containers interface.

base/containers/README.md

 # base/containers library
 
 ## What goes here
 
 This directory contains some STL-like containers.
 
 Things should be moved here that are generally applicable across the code base.
 Don't add things here just because you need them in one place and think others
 may someday want something similar. You can put specialized containers in
 your component's directory and we can promote them here later if we feel there
@@ skipping 106 matching lines @@
 set sizes, std::vector's doubling-when-full strategy can waste memory.
 
 Supports efficient construction from a vector of items which avoids the O(n^2)
 insertion time of each element separately.
 
 The per-item overhead will depend on the underlying std::vector's reallocation
 strategy and the memory access pattern. Assuming items are being linearly added,
 one would expect it to be 3/4 full, so per-item overhead will be 0.25 *
 sizeof(T).
 
+
+flat\_set/flat\_map support C++14 interface and a notion of transparent

[Nico, 2017/07/20 18:26:53]

We're not on c++14 yet, and we don't know how and when we're going to switch to
it. Why do we mention c++14 in this doc (and why are we adding c++-14-related
stuff to the code base?)

[danakj, 2017/07/20 18:51:15]

Do you think mentioning c++14 is bad? It gives a really helpful tool to help
understand how this works to compare to other things IMO.

This is being added because it is useful, not because it is in c++14, but being
done in a way that will be familiar with other c++14 containers. This allows you
to key your set with a unique_ptr, instead of having to do flat_map<T*,
unqiue_ptr<T>> for example, or avoid constructing temporary std::strings on
every lookup.

+comparisons. Therefore you can, for example, lookup base::StringPiece in a set
+of std::strings without constructing a temporary std::string.
+You can find more information about transparent comparisons here:
+http://en.cppreference.com/w/cpp/utility/functional/less_void
+Example, smart pointer set:
+    // Define a custom comparator.
+    struct UniquePtrComparator {
+      // Mark your comparison as transparent.
+      using is_transparent = int;
+      template <typename T>
+      bool operator()(const std::unique_ptr<T>& lhs,
+                      const std::unique_ptr<T>& rhs) const {
+        return lhs < rhs;
+      }
+      template <typename T>
+      bool operator()(const T* lhs, const std::unique_ptr<T>& rhs) const {
+        return lhs < rhs.get();
+      }
+      template <typename T>
+      bool operator()(const std::unique_ptr<T>& lhs, const T* rhs) const {
+        return lhs.get() < rhs;
+      }
+    };
+    // Declare a typedef.
+    template <typename T>
+    using UniquePtrSet =
+        base::flat_set<std::unique_ptr<T>, UniquePtrComparator>;
+    // ...
+    // Collect data.
+    std::vector<std::unique_ptr<int>> ptr_vec;
+    ptr_vec.reserve(5);
+    std::generate_n(std::back_inserter(ptr_vec), 5, []{
+      return base::MakeUnique<int>(0);
+    });
+    // Construct a set.
+    UniquePtrSet<int> ptr_set(std::move(ptr_vec), base::KEEP_FIRST_OF_DUPES);
+    // Use raw pointers to lookup keys.
+    int* ptr = ptr_set.begin()->get();
+    EXPECT_TRUE(ptr_set.find(ptr) == ptr_set.begin());
+Example flat_map<std::string, int>:
+    base::flat_map<std::string, int> str_to_int({{"a", 1}, {"c", 2},{"b", 2}},
+                                                base::KEEP_FIRST_OF_DUPES);
+    // Does not construct temporary strings.
+    str_to_int.find("c")->second = 3;
+    str_to_int.erase("c");
+    EXPECT_EQ(str_to_int.end(), str_to_int.find("c")->second);
+    // NOTE: This does construct a temporary string. This happens since if the
+    // item is not in the container, then it needs to be constructed, which is
+    // something that transparent comparators don't have to guarantee.
+    str_to_int["c"] = 3;
+
 ### base::small\_map
 
 A small inline buffer that is brute-force searched that overflows into a full
 std::map or std::unordered\_map. This gives the memory benefit of
 base::flat\_map for small data sizes without the degenerate insertion
 performance for large container sizes.
 
 Since instantiations require both code for a std::map and a brute-force search
 of the inline container, plus a fancy iterator to cover both cases, code size
 is larger.
@@ skipping 24 matching lines @@
   printf("Found is %d\n", (int)(found == foo.end()));
   found = foo.find("bar");
   printf("Found is %d\n", (int)(found == foo.end()));
   found = foo.find("asdfhf");
   printf("Found is %d\n", (int)(found == foo.end()));
   found = foo.find("bar1");
   printf("Found is %d\n", (int)(found == foo.end()));
 }
 ```