Flat containers (flat_set & flat_map)

[samchon]

Flat containers are based on array.

• flat_set: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1222r1.pdf
• flat_map: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0429r6.pdf

Ordinary tree (associative) containers like TreeMap or TreeMultiSet, they store elements in a doubly-linked-list and nodes (iterators) of the doubly-linked-list are stored in a binary tree. It makes binary search & bidirectional iteration possible at the same time (B+Tree).

New flat containers, they store elements in array. They do not implement binary search through binary tree, but by using sorting and binary search functions in <algorithm> module.

• sort
• lower_bound
• upper_bound
• equal_range

Type	TreeMap	FlatMap
Search	O (log n)	O (log n)
Insert	O (log n)	O (n*log n)
Erase	O (1)	O (n)
Iteration	Bidirectional	Random Accessible

[samchon]

Flat containers in v2.2 update as experimental features:

• src/experimental/container/FlatSet.ts
• src/experimental/container/FlatMultiSet.ts
• src/experimental/container/FlatMap.ts
• src/experimental/container/FlatMultiMap.ts

[samchon]

Have implemented until v2.2 update.

Flat containers are candidate features in C++20, however, it's not determined yet. It even can be rejected in final C++20 committee and don't know whether those flat containers would be adapted in standard or experimental.

If someone recognizes final determination of C++20 committee about flat containers faster than me, please inform me.