Re: Meyers's preference for vectors over maps

From: tom_usenet (tom_usenet_at_hotmail.com)
Date: 01/28/04 

Date: Wed, 28 Jan 2004 12:49:02 +0000

On 28 Jan 2004 08:13:37 GMT, Fred Ma <fma@doe.carleton.ca> wrote:

>Hello,
>
>I was looking at Meyers's "Effective STL", item 23
>about choosing between vectors and maps (at least
>that the choice for me). In many cases, using
>sorted vectors is faster for lookups. The two
>reasons are (1) that vector elements are smaller,
>since map elements need at least 3 pointers, and
>(2) contiguity of vector elements in memory ensure
>fewer page faults.
>
>For me, I will a container of objects that are much
>bigger than pointers, so reason (1) doesn't apply.
>
>Reason (2) is what I'm trying to understand better.
>Let me describe my application.
>
>In my case, I will have N items in the container,

Is N fixed at runtime? IOW, is the size of the container constant?

>will look up n (n<N) items, do some processing,
>then replace the n worst items in the container
>with the n new items from processing. Here, worse
>is defined by the sorting function. The problem
>is that n can vary from 1 to N, making the advantages
>of vector vs. map very unclear. For small n,
>map is better because I'm basically interspersing
>1 modification of the database with 1 lookup.
>For large n, vector is better because it's faster
>to sort a whole bunch of objects at once rather
>than building a map in a piecemeal fashion.

I would recommend a vector. Keep another empty vector handy. Start by
sorting your main vector. Calculate your new range of n to add and
sort it (in O(n)), then merge that with your old vector into your same
sized vector.

tempvec.reserve(v.size());
std::sort(newrange.begin(), newrange.end());
//merge the N-n remaining elements from v with the new range:
std::merge(v.begin() + n, v.end(), newrange.begin(), newrange.end(),
std::back_inserter(tempvec));

//swap
tempvec.swap(v);
tempvec.clear();

etc. That way the operation is only n log n, not N log N.

>
>Since I can't get a clear answer from that line of
>reasoning, I looked more carefully at Meyers's
>reason (2). I will be using binary search for
>lookup, and he claims that contiguity of elements
>is good for binary search in particular. More
>specifically, I understood him as meaning that
>closeness of elements in memory should match
>closeness of elements in the traversal of
>container elements. However, my understanding
>of binary search is that it doesn't traverse
>elements in sequential order. So why the
>contiguity of elements in a vector be of any
>advantage?

Because they are all close to each other in memory. If a 4k chunk of
the vector is pulled into cache memory, you'll get a lot of cache
hits.

>Thanks for clarifying. And if there are any
>other considerations that would make it easier
>to decide upon a proper container, I'd appreciate
>those too. Right now, I'm tempted to go for a
>vector because I haven't used a map before. But
>for that reason, I'm also thinking it's not a bad
>reason to dabble in maps, too.

Given the fixed size, vector seems a good choice. If your elements are
expensive to copy, I'd go for a vector or smart pointers, or just
pointers (with manual memory management).

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

Relevant Pages

  • Re: Good Dungeon Mapping e-Tool?
    ... Kyle Wilson wrote: ... elements to create a map is that they change sizes as you zoom, ... Lots of very cool open source projects have died because ... a reason to pick one particular interesting off-side ...
    (rec.games.frp.dnd)
  • Re: The Vinland Maps Ink
    ... > think that's one reason some folks, including Seaver, considered ... that the forger's (assuming for argument's sake that it is a forgery) ... OR he/she who was forced to make the map, ... The germans did not know writing or latin ...
    (sci.archaeology)
  • Re: Perl on the Pocket PC - Easy!
    ... thing to a size proper for the Pocket PC? ... Almost never any reason to initialize an array to. ... map() should almost never be used in a void context. ... Knowing how to use them is a good step in the right direction. ...
    (comp.lang.perl.misc)
  • Meyerss preference for vectors over maps
    ... I will a container of objects that are much ... Reason is what I'm trying to understand better. ... of vector vs. map very unclear. ... is good for binary search in particular. ...
    (comp.lang.cpp)
  • Re: XP memory detection problem at 4 GB
    ... I think this might be related to the memory map. ... some reason the full 4GB cannot fit in the first map. ...
    (microsoft.public.windowsxp.hardware)