STL: map vs vector

[zaineb]

Hi,

This is a follow-up of sort of this thread:
http://groups.google.com/group/comp....2cab752779f1fa

I've been chewing on this problem for a while. When I came across the
above thread, I figured that maybe other members have a better idea on
how to approach this.

I'm currently trying to decide between which one of maps or vectors to
use. I'm trying to come up with a design that will let me perform fast
insertions and deletions (w/o duplicates) in a sorted "list" and then
look up every 25th or so element (and then iterate sequentially for the
next 25 values , so sequential look up). The indexed lookup happens
slightly more frequently than insertions and deletions, so it makes
sense to make lookup efficient. Because the insertions and deletions
also happen often, fast/efficient lookups are helpful as well. Memory
isnt as much of an issue as speed is.

I've looked around a bit, so if this is something that has been
discussed before, please let me know.

Right now I have 2 "solutions" .

One is a sorted vector, where I use 'lower_bound' to get where I should
insert the value and insert it there, and use it to find the value to
remove. Lookups are just normal lookups (thru
my_vector.begin ()+indexSubscri pt ). Most inserts and removals are from
the center of the list, so whenever there is an insertion or removal,
I'm guessing that all the elements are copied up or down. The values
are user defined objects so thats a lot of copying calls.

The other design uses a map and a vector. The map contains the actual
sorted values. The vector is an index to every 25th key which is reset
at every insertion and removal (from the closest previous key in the
map onwards). To access the 25th*x value, you would get the
corresponding key in the index and find it in the map, and then iterate
sequentially.

After implementing both of these, the performance difference is really
minimal for me, but I'm not sure if I'm missing a better way of doing
this. I'm guessing this is something that people have come across
often. I'm a new C++/STL user, so I might be missing a good data
structure to use or a better solution to this problem. Any help would
be appreciated.

Thanks much.
-Z

[zaineb]

The whole point of doing this was not having to iterate all the way
down the list.
So the way this is used is that I have a bunch of records. Depending on
the record x used, you would get 25xth to 25(x+1)th . So if there are
multiple records called, for each record you would have to iterate all
the way down the list to get the values. For lists that are in the
thousands, this is very hard. So for imagine this for x = 1000 with x =
1500. Now imagine doing this for 100 or so records all with different x
values. There's a lot of unnecessary iteration going on.
Since insertions or removals might happen 6-7 times a second, it makes
more sense to have an index instead of using +=25 to iterate linearly.
The gains in doing that are substantial.

[Richard Herring]

In message <11************ **********@j73g 2000cwa.googleg roups.com>, Luke
Meyers <n.***********@ gmail.com> writes

Sorry, I didn't try this myself prior to posting. Whether += is
defined is (perhaps surprisingly at first) kind of irrelevant. You've
got a forward-iterator, which means you've got operator++, so you can
always implement operator+= in terms of that. If the standard library
doesn't provide this, it's probably to avoid implying that the
operation is more efficient than it really is.

Here's a working implementation:
(apart from being UB :-( )
namespace std {
17.4.3.1 It is undefined for a C + + program to add declarations or
definitions to namespace std or namespaces within namespace std unless
otherwise specified. A program may add template specializations for any
standard library template to namespace std. Such a specialization
(complete or partial) of a standard library template results in
undefined behavior unless the declaration depends on a user-defined name
of external linkage and unless the specialization meets the standard
library requirements for the original template.
template <class FwIter>
FwIter &
operator+=(FwI ter & iter, size_t n)
which will attempt to match just about any type for its left operand,
not just set iterators.
{
for (int i = 0; i < n; ++i, ++iter); // no body
return iter;
}
}

The C++ way of doing this is called std::advance().

--
Richard Herring

[Luke Meyers]

za****@gmail.co m wrote:

The whole point of doing this was not having to iterate all the way
down the list.
So the way this is used is that I have a bunch of records. Depending on
the record x used, you would get 25xth to 25(x+1)th . So if there are
multiple records called, for each record you would have to iterate all
the way down the list to get the values. For lists that are in the
thousands, this is very hard. So for imagine this for x = 1000 with x =
1500. Now imagine doing this for 100 or so records all with different x
values. There's a lot of unnecessary iteration going on.
Since insertions or removals might happen 6-7 times a second, it makes
more sense to have an index instead of using +=25 to iterate linearly.
The gains in doing that are substantial.

Unless the creation of the indices introduces overhead equivalent to
the linear-search work you're trying to avoid by creating them. Which
is what I stated. I'm well aware, and said explicitly, that the +=
operation doesn't magically introduce constant-time random access to
std::map. Neither does your scheme. If you've got 6-7
insertions/removals per second, and calculate the set of indices (or a
significant fraction thereof -- half, on average, if they're evenly
distributed) each time, you're doing 6-7 operations with time
complexity that's linear in the size of the map per second. If you're
willing to recalculate the set of indices less often, at the expense of
not spanning exactly 25 elements each time, you can incrementally
reduce this. You didn't respond to my suggestion along these lines,
though.

The asymptotic time-complexities of your current scheme, from my best
understanding of your descriptions, are:

Insert/remove element:
O(n*log(n)) // log(n) for std::map insertion, plus O(n) insertions of
recalculated indices

Access element number x*25, given cached index set:
O(log(n)) // can be improved to O(1) if you use vector<map::ite rator>

Iterate across all elements, 25 at a time, assuming no insert/delete
interruptions:
O(n*log(n)) // O(n) elements accessed, log(n) look up each time. Can
be improved to O(n) if you use vector<map::ite rator>

There's no way you'll get better than O(n) for accessing every 25th
element, since the number of elements you want to actually look at has
cardinality of O(n). The problem is the O(n*log(n)) step on
insert/remove. That's as bad as doing push_back on a vector and
calling std::sort each time you insert. Do you still like this scheme?

Finally, getting back to the original point, it's not accurate to
characterize the += step as "iterating all the way down the list." 25
is a constant. You've got an iterator to one point in the list, and
+=25 involves a constant amount of work to get to the next point you're
interested in. If you want to do this n times (or n/25 times, as it
happens), you're going to have linear-time complexity regardless of
whether your constant-time operation is an efficient random access
(which is not available) or the one I described involving looping over
operator++.

I hope this is more clear. I feel like your response was a little
impolite, incidentally -- I feel I've demonstrated adequate
understanding of asymptotic complexity in this thread not to merit a
remedial explanation of why linear search is inefficient.

Unless you've got some better-than-O(n) way of caching those indices
each time you insert/remove, perform fewer insertions/removals, or
recache your indices far less frequently, you're not going to improve
on O(n*log(n)) here. Given that fact, you might as well give up on
this scheme for a more straightforward O(n*log(n)) scheme (one with a
better constant factor, no doubt), or try approaching the problem from
a different perspective entirely.

According to what you've said, it sounds like perhaps you're
over-valuing random access. You said that, after doing one of these
random accesses, you proceed to iterate over the entire collection
starting at that point (on average, half of the elements), 25 at a
time. That's inherently an O(n) operation, so you wouldn't increase
your big-O even by doing linear search for the starting point. Of
course, the constant factor in that lookup is greater by a factor of
25. But, well, food for thought.

Luke

[Luke Meyers]

Richard Herring wrote:

In message <11************ **********@j73g 2000cwa.googleg roups.com>, Luke
Meyers <n.***********@ gmail.com> writes

Here's a working implementation:

(apart from being UB :-( )

Okay, maybe "working implementation" was too strong a phrase. ;)

What I meant is, I coded it up and compiled it, and it worked in my
case -- to be fair, that's more than you get a lot of the time with ng
code!

namespace std {

17.4.3.1 It is undefined for a C + + program to add declarations or
definitions to namespace std or namespaces within namespace std unless
otherwise specified. A program may add template specializations for any
standard library template to namespace std. Such a specialization
(complete or partial) of a standard library template results in
undefined behavior unless the declaration depends on a user-defined name
of external linkage and unless the specialization meets the standard
library requirements for the original template.

Yeah yeah, ya got me. Thanks for pointing this out. I was aware of
this section of the standard, but had chosen following the example of
an old C++ mentor of mine over adhering to the letter of the standard
in this particular case -- not my usual practice, and I'm now glad to
have considered this and found sufficient reason not to make the
exception. His reasoning for adding things to namespace std had to do
with ADL, and putting operations in the same namespace as the entities
to whose interface they belong. Valid in general, but as I considered
your point I realized that, by introducing a template such as this, I
could interfere with lookups happening internal to my standard library
implementation, which may be part of why this section of the standard
exists.

template <class FwIter>
FwIter &
operator+=(FwI ter & iter, size_t n)

which will attempt to match just about any type for its left operand,
not just set iterators.

Right, and I knew this. Just as you know that writing correct generic
code is full of unique challenges -- my point was not to say, here's
some perfect code you should copy and paste and use everywhere, but
just to point out that based on the ability to increment, incrementing
by 25 is an obvious and trivial extension. How it's accomplished
syntactically, while perhaps interesting in another context, is not
important to the question at hand.

for (int i = 0; i < n; ++i, ++iter); // no body

The C++ way of doing this is called std::advance().

Yes, that's exactly what I wish I had thought of.

Thanks,
Luke