This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [GSoC] Question about std::map
- From: Jonathan Wakely <jwakely dot gcc at gmail dot com>
- To: Tobias Grosser <tobias at grosser dot es>
- Cc: Trevor Saunders <tsaunders at mozilla dot com>, Roman Gareev <gareevroman at gmail dot com>, "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>, Mircea Namolaru <mircea dot namolaru at inria dot fr>
- Date: Mon, 7 Jul 2014 12:14:53 +0100
- Subject: Re: [GSoC] Question about std::map
- Authentication-results: sourceware.org; auth=none
- References: <CABGF_gfEPTkYLxg74bykZasx6TTRMtWRTQRYWkc4B7g=Ex84fg at mail dot gmail dot com> <53B5987B dot 4060306 at grosser dot es> <20140704021609 dot GA30392 at tsaunders-iceball dot corp dot tor1 dot mozilla dot com> <53B65E57 dot 8040508 at grosser dot es> <20140704220338 dot GC3933 at tsaunders-iceball dot corp dot tor1 dot mozilla dot com> <53BA7FCA dot 4070701 at grosser dot es>
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.