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

[vmpstr, 2017/06/23 21:45:14]

Can you link to documentation about transparent comparators in the comment?

[dyaroshev, 2017/06/26 11:47:29]

Sorry - missed this. Will do with next patch. Do docks for std::less work for
you? http://en.cppreference.com/w/cpp/utility/functional/less_void

[vmpstr, 2017/06/26 15:35:53]

Yeah that works; just something for people to read up on if interested in
transparent comparisons

+comparisons. Therefore you can, for example, lookup base::StringPiece in a set
+of std::strings without constructing a temporary std::string.
+
 ### 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()));
 }
 ```