Re: [GSoC] Question about std::map

[Tobias Grosser <tobias at grosser dot es>]

On 07/07/2014 13:14, Jonathan Wakely wrote:
> On 7 July 2014 12:08, Tobias Grosser wrote:
> > The number of elements in these maps is most likely between 3-10.
>
> Then std::map is the wrong solution.
>
> The overhead of dereferencing all the pointers while walking through a
> std::map will be higher than the savings you get from logarithmic
> lookup.
>
> For ten elements a linear search of a std::vector will probably be
> quicker than lookup in a std::map. A binary search of a sorted vector
> (which needs no pointer-chasing because it uses random-access
> iterators) will definitely be faster.

Very good point. On the other side, we still want to hide this behind a 
map-like interface. So starting with a std::map may be a good thing.
To tune this later we can introduce a specialized vector_map. Such a 
vector_map may not even want to use a std::vector, but a vector class 
that stores its data in stack memory.

Cheers,
Tobias