Links:
CL:
https://codereview.chromium.org/2552343003/

Document with summary:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5gw/edit?usp=sharing

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/db07be4db9751369102b24cd8fe772200982f3e7

commit db07be4db9751369102b24cd8fe772200982f3e7
Author: dyaroshev <dyaroshev@yandex-team.ru>
Date: Wed Feb 08 02:39:47 2017

This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_flat_containers.md

Differences in the api with the proposal:
 - Key types are not const.
   None of analysed flat_set implementations (boost, eastl, folly) do this. Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted Sean
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator/Sentinel} pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges TS (talk at
   CppCon: https://youtu.be/mFUXNMfaciE). Currently in chromium we do not use
   this type of ranges, and introducing it without enable_if tricks make certain
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // Tries to insert with two template parameters instead of
                             // casting iterator to const_iterator.
   We can probably fix this, but it should be done later.

- No templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them, but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for some
    cases in Chromium but it has to be investigated separately (this would lead to
    introduction of different apis, that have to be benchmarked first). However, we
    typically  do not use allocators in chromium, do we want to keep the possibility of
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids small
    buffer optimisation. This optimisation sometimes proves to be very beneficial.
    If we are willing not to give the same guarantee as std::vector, we can introduce it
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector$20based/chromium-dev/4uQMma9vj9w/HaQ-WvMOAwAJ

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5gw/edit?usp=sharing

BUG=671759

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

[modify] https://crrev.com/db07be4db9751369102b24cd8fe772200982f3e7/base/BUILD.gn
[add] https://crrev.com/db07be4db9751369102b24cd8fe772200982f3e7/base/containers/flat_set.h
[add] https://crrev.com/db07be4db9751369102b24cd8fe772200982f3e7/base/containers/flat_set_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/f7d92cff18cba731d3a33d19d3f9595bbacd6fb6

commit f7d92cff18cba731d3a33d19d3f9595bbacd6fb6
Author: jdoerrie <jdoerrie@chromium.org>
Date: Tue Apr 04 22:12:01 2017

Change flat_tree::unsafe_emplace to actually emplace

This change modifies base::flat_tree::unsafe_emplace to do an emplace instead of an insert under the hood.

BUG=671759

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

[modify] https://crrev.com/f7d92cff18cba731d3a33d19d3f9595bbacd6fb6/base/containers/flat_tree.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/154dc49655238f0fc9928763bcf47930823a8e02

commit 154dc49655238f0fc9928763bcf47930823a8e02
Author: jdoerrie <jdoerrie@chromium.org>
Date: Fri May 19 10:35:28 2017

Add range insertion for base::flat_tree

This change implements an efficient algorithm for base::flat_tree::insert(Iter, Iter).

BUG=671759, 682249

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

[modify] https://crrev.com/154dc49655238f0fc9928763bcf47930823a8e02/base/containers/flat_map.h
[modify] https://crrev.com/154dc49655238f0fc9928763bcf47930823a8e02/base/containers/flat_set.h
[modify] https://crrev.com/154dc49655238f0fc9928763bcf47930823a8e02/base/containers/flat_tree.h
[modify] https://crrev.com/154dc49655238f0fc9928763bcf47930823a8e02/base/containers/flat_tree_unittest.cc