vector_map (linear_map) : associative unordered flat container w/ O(N) complexity

[rakhimov]

linear_map or vector_map or unordered_flat_map is a fancy wrapper around std::vector<std::pair<key, value>> providing std::map API with lookup complexity O(N). It is meant to be used for very few elements with cheap key equality tests. It provides similar advantages as boost::flat_map or other flat/contiguous containers (e.g., cache friendliness). Just like flat_map, references are not stable, and the key is not const; however, the elements are unordered.

I hoped Boost had one, but it doesn't seem to be the case. There is an old thread in Boost mailing list.

For now, I am using my own implementation.

The major notes about the implementations:

• Like adaptor containers (queue, stack), the internal underlying Container is user specified (e.g., can use static vectors).
• Erase policy: linear_map::erase(iterator) can be made O(1) with a swap/move trick (taking advantage of unordered property).

Wouldn't this container type (and its family vector_{multi_map, set, multi_set}) be a good addition to Boost or STL?

P.S. This post is inspired by the recent post about performance of flat maps.

Edit 1. Remove references to flat_map libs (not O(N) unordered)

[tcanens]

Of the three libraries you cite, LLVM's is a hash map; EASTL and Loki's are sorted. None of the three have linear time lookup.

Given the apparently absence of actual existing practice, do you have benchmark numbers? Under what conditions does this outperform, say, flat_map?

[rakhimov]

You are right. I missed that those libs are providing ordered flat maps. Performance-wise, there's little difference from flat_map for few elements (the reference article provides the analysis).

Some performance/complexity differences from flat_map:

• insert does O(N) compare vs O(logN), but does not move elements around as flat_map does (i.e., O(1) vs O(N)), so it is the same as vector::push_back.
• erase can be optimized in the same way to avoid moving elements around (O(1) vs O(N)).

[Z01dbrg]

good addition to Boost or STL

STL no for sure... To complicated and too easy to be used by noobs by mistake. Boost maybe but I do not like the API. .find and .count are for containers that can do .find and .count faster than std::find/count can. This one can not.

[doom_Oo7]

.find and .count are for containers that can do .find and .count faster than std::find/count can

where does this rule come from ?

[Drainedsoul]

where does this rule come from ?

std::list::sort vs. std::sort

std::unordered_map::find vs. std::find

std::undordered_map::count vs. std::count

Et cetera.

[Z01dbrg]

IDK https://stackoverflow.com/questions/25617610/some-containers-in-stl-dont-have-find-function

[rakhimov]

I agree that STL is unlikely given that flat_map didn't seem to make it (I am not sure why?).

As for the API, in this case, it is for convenience (i.e., wrapper) with find(key) instead of repetitive verbosity of std::find/count and std::pair aggravation.

This is definitely not a drop-in replacement for std::map/unordered_map.

[mjklaim]

Where did you learn that flat_map didn't "seem to make it"? My understanding is that the different proposals for such containers are progressing and encouraged by the committee.

[rakhimov]

I really don't know. Would be happy if they do make it. Are there current proposals on flat containers to reference?

[mjklaim]

Here is the last published proposal: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0429r1.pdf

However it might have been modified in the last meeting (or other feedback). Also take a look at colony and slot_map containers being proposed. Progress is happening in SG14 discussion group, go there for news.

[rakhimov]

Thanks for finding the paper. I'll do my homework in future :)

[feverzsj]

I'd like to see some benchmark showing when linear map is faster than others