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 28 matching lines @@
     cases, inserts are better or comparable to other containers even for
     several dozen items, and efficiently-moved types are unlikely to have
     performance problems for most cases until you have hundreds of items. If
     your container can be constructed in one shot, the constructor from vector
     gives O(n log n) construction times and it should be strictly better than
     a std::map.
 
   * **base::small\_map** has better runtime memory usage without the poor
     mutation performance of large containers that base::flat\_map has. But this
     advantage is partially offset by additional code size. Prefer in cases
-    where you make many objects so that the code/heap tradeoff is good.
+    where you make many objects so that the code/heap tradeoff is good.

[vmpstr, 2017/06/26 23:06:34]

I wonder if this is causing the patch failure, it seems like a no-op change? Is
that a part of your local diff?

[jdoerrie, 2017/06/27 12:56:50]

Investigating locally this seems to be replacing a non-breaking space (U+00A0)
with a regular space (U+0020). Further evidence for a non-breaking space here
can be found by investigating the corresponding sentence in
https://chromium.googlesource.com/chromium/src/+/master/base/containers/READM...
with dev tools.

It's odd that patch seems to be unable to find this space and thus the bots
break. Probably a bug should be filed to investigate this further, but maybe
simply revert to a non-breaking space in the meantime?

 
   * Use **std::map** and **std::set** if you can't decide. Even if they're not
     great, they're unlikely to be bad or surprising.
 
 ### Map and set details
 
 Sizes are on 64-bit platforms. Stable iterators aren't invalidated when the
 container is mutated.
 
 | Container                                | Empty size            | Per-item overhead | Stable iterators? |
@@ skipping 57 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
+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);
+
+    // NOTE: does construct a temporary string.
+    str_to_int["c"] = 3;

[dyaroshev, 2017/06/26 22:40:43]

standard doesn't provide a templated overload for operator[]. I don't know how
to do it well - therefor I don't think we should.

(type K has to be comparable with key_type, not necessarily convertible)

[vmpstr, 2017/06/26 23:06:34]

I agree. I think that if you have a transparent comparator it doesn't have to
imply that key_type is constructible from K. Can you expand your NOTE about to
provide this reason? Something like

"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."

I kind of tried to elaborate more, but it gets very detailed quickly, so I think
that comment is fine...

[dyaroshev, 2017/06/27 21:19:29]

Done

+
+    // Do not construct temporary strings.

[vmpstr, 2017/06/26 23:06:34]

nit: s/Do/Does/

[dyaroshev, 2017/06/27 21:19:29]

Done

+    str_to_int.find("c")->second = 3;
+    str_to_int.erase("c");
+    EXPECT_EQ(str_to_int.end(), str_to_int.find("c")->second);
+
 ### 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()));
 }
 ```