Improving flat containers interface.

base/containers/README.md

Index: base/containers/README.md
diff --git a/base/containers/README.md b/base/containers/README.md
index e64e8f3a637162d1b43b7d4df0f90e705289ecc9..878a9f4b568d34da9bd6b815c511a2cb715c455a 100644
--- a/base/containers/README.md
+++ b/base/containers/README.md
@@ -46,7 +46,7 @@ Google naming. Be sure to use the base namespace.
   * **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.
@@ -124,6 +124,70 @@ 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