std::map vs unordered_map memory footprint for small N

Question

For embedded system applications where memory usage is more of a concern than speed, what would be the best map container to use? std::map, std::unordered_map? This would be for situations where N is less than, say, a hundred.

If implementation matters, then I'm concerned with the libstdc++ implementation (GCC).

While I understand that it's impossible to beat a simple array for memory usage, I want to avoid a data structure that has O(N) performance. So while I want to reduce memory footprint, I also want the lookup speed to be reasonable (better than O(N)). I don't care about other operations (insertions, removals), as they will occur infrequently.

If I wanted to make my own memory usage measurements, how would I go about doing this on a Linux platform?

Would boost::flat_map be suitable as an associative container with small footprint and lookup times better than O(n)?

Answer 1

For small N, a sorted vector is often the fastest container, and has minimal memory footprint. boost::flat_map is an implementation, others call it AssociativeVector. You can use std::lower_bound to implement it easily. Since the data has to be sorted, insert and delete operations are O(n) since the data has to be shifted in the vector.

With a sorted vector, you can do a binary search which is O(log N) for retrieval. The complexity of std::lower_bound is:

The number of comparisons performed is logarithmic in the distance between first and last (At most log2(last - first) + O(1) comparisons)