STL map vs. list & vector performance
Victor Bazarov
> Hello,
>
> I was wondering if anybody can tell me or point me to some stats on where
a
> STL vector or list is better to use over a map and vice versa?
>
> The size and number of items I'll be using will vary, so I guess one of
> these is better than others depending on the situation. I've been led to
> believe that a map is a safe bet most of the time since it's lookup is
quite
> fast and insertion and deletion is also quite fast. I'm not overly
> concerned with the amount of memory that I'll be using, but rather
focusing
> on the speed.
Those are three containers that were designed to serve completely
different purposes: vector<> has very quick random access to elements,
list<> has very quick insertion, and map<> sorts its contents by the
key values and makes sure the key is unique. If you need a fixed-sized
structure and quick access to elements (like with a C++ array) use
vector<>. If you don't really care about individual (or random) access
to elements, but you need to quickly insert and/or delete without much
overhead, use list<>. If you need your collection sorted with fair
extraction speed, use set<> or map<>. See? Different purposes. You
need to decide which one to use based on your problem, not based on
the performance of unrelated container implementations.
Victor
--
Please remove capital A's from my address when replying by mail
grzegorz
If you don't know whether you want to use vector or list use deque.
If you want to use a key - value pairs , and be able to index the
container
based on the key use map.
If you want to divide container into separate groups indexed by the key,
use multimap.
--
@@@@ grzegorz
Andrew
I was wondering if anybody can tell me or point me to some stats on where a
STL vector or list is better to use over a map and vice versa?
The size and number of items I'll be using will vary, so I guess one of
these is better than others depending on the situation. I've been led to
believe that a map is a safe bet most of the time since it's lookup is quite
fast and insertion and deletion is also quite fast. I'm not overly
concerned with the amount of memory that I'll be using, but rather focusing
on the speed.
Thanks,
Andrew
Josh Sebastian
all of the big-O's for everything in STL. Here's a general summery.
In vector, searches, comparisons, etc are linear. Access is always
constant time. Insertions CAN be constant time, but are only
garaunteed to be linear.
With deque, searches, comparisons are linear. Access is constant, but
slower than vector. Insertions AT EITHER END are constant time.
Insertions in the middle are similar to vector.
With a list, access is linear. Insertions are constant time.
With the map, searches, access, and insertions are ALL O(lg n)
On Tue, 01 Aug 2000 01:42:55 GMT, "Andrew" <akas...@sympatico.ca>
wrote:
Andrew K
I'll need a container that will need to do a lot of lookup (maps good
for this) on items and also straight iteration (vector good for this)
through the whole container.
I think the searching is a bit more important to what I'm doing than the
iteration so I'm thinking maps are the way for me to go. My container
will be storing 1000's of objects (references to them). In real life
situations would I gain more using the map, because of the searching,
than I would by using a vector for iterations?
Would it be advisable to combine the map and vector into my own class to
get the benifits of each or is there way too much processing to deal
with making sure each container contains reference to the same data, ie.
I delete an object from the map, I'll have to search the vector for the
same object and remove it from there too.
Thanks for any help,
Andrew
Victor Bazarov
> Well this is what I need.
> I'll need a container that will need to do a lot of lookup (maps good
> for this) on items and also straight iteration (vector good for this)
> through the whole container.
If you only need straight iteration, the map<> is no worse than
vector<>. vector<> is only good if you need random access to
elements using an index. However, what kind of look-ups are we
talking about? Can you extract the key from your data elements
in order to use it in map<>? If you can, good. If you can't, what
good is map<> if your key is different for every element or if
your key cannot be separated (is dynamic, for example)?
>
> I think the searching is a bit more important to what I'm doing than
the
> iteration so I'm thinking maps are the way for me to go. My container
> will be storing 1000's of objects (references to them). In real life
Don't attempt to store references in an STL container. A reference
doesn't comply with requirements that an element has to meet.
> situations would I gain more using the map, because of the searching,
> than I would by using a vector for iterations?
>
> Would it be advisable to combine the map and vector into my own class
to
> get the benifits of each or is there way too much processing to deal
> with making sure each container contains reference to the same data,
ie.
> I delete an object from the map, I'll have to search the vector for
the
> same object and remove it from there too.
Unnecessary overhead. You probably need to re-think it. Find a
good book on STL and explore the options available to you there.
If you don't feel like using any of them directly, there is probably
the need to create your own container, custom-made to fit your
problem.
>
> Thanks for any help,
> Andrew
>
>
> Josh Sebastian wrote:
> >
> > STL Tutorial and Reference Guide by David Musser and Atul Saini has
> > all of the big-O's for everything in STL. Here's a general summery.
> >
> > In vector, searches, comparisons, etc are linear. Access is always
> > constant time. Insertions CAN be constant time, but are only
> > garaunteed to be linear.
> >
> > With deque, searches, comparisons are linear. Access is constant,
but
> > slower than vector. Insertions AT EITHER END are constant time.
> > Insertions in the middle are similar to vector.
> >
> > With a list, access is linear. Insertions are constant time.
> >
> > With the map, searches, access, and insertions are ALL O(lg n)
> >
Victor
Howard Hinnant
<kas...@nortelnetworks.com> wrote:
| Well this is what I need.
| I'll need a container that will need to do a lot of lookup (maps good
| for this) on items and also straight iteration (vector good for this)
| through the whole container.
Another possibility to consider then is a sorted vector. You can
efficiently search it with lower_bound. But if you need lots of fast
insert/erase anywhere but the end of your vector, then map is still a win.
-Howard
Mark Wilden
news:39870CD4...@nortelnetworks.com...
> Well this is what I need.
> I'll need a container that will need to do a lot of lookup (maps good
> for this) on items and also straight iteration (vector good for this)
> through the whole container.
When you iterate, do you care about the order of the elements?
Andrew K
from start to finish.
Victor Bazarov
> Nope, I don't care about order at all, I just want to be able to
iterate
> from start to finish.
I belive that map<> is your template. Any thoughts why it won't suit
you?
>
> Mark Wilden wrote:
> >
> > "Andrew K" <kas...@nortelnetworks.com> wrote in message
> > news:39870CD4...@nortelnetworks.com...
> > > Well this is what I need.
> > > I'll need a container that will need to do a lot of lookup (maps
good
> > > for this) on items and also straight iteration (vector good for
this)
> > > through the whole container.
> >
> > When you iterate, do you care about the order of the elements?
Victor
Andrew K
Victor Bazarov wrote:
>
> If you only need straight iteration, the map<> is no worse than
> vector<>. vector<> is only good if you need random access to
> elements using an index. However, what kind of look-ups are we
> talking about? Can you extract the key from your data elements
> in order to use it in map<>? If you can, good. If you can't, what
> good is map<> if your key is different for every element or if
> your key cannot be separated (is dynamic, for example)?
>
I think a map is what I need from what you have said. The key can be
extracted from the data.
> >
> > I think the searching is a bit more important to what I'm doing than
> the
> > iteration so I'm thinking maps are the way for me to go. My container
> > will be storing 1000's of objects (references to them). In real life
>
> Don't attempt to store references in an STL container. A reference
> doesn't comply with requirements that an element has to meet.
>
Ohh, I didn't know that. Thanks for mentioning it. :)
Victor Bazarov
>
>
> Victor Bazarov wrote:
> >
> > If you only need straight iteration, the map<> is no worse than
> > vector<>. vector<> is only good if you need random access to
> > elements using an index. However, what kind of look-ups are we
> > talking about? Can you extract the key from your data elements
> > in order to use it in map<>? If you can, good. If you can't, what
> > good is map<> if your key is different for every element or if
> > your key cannot be separated (is dynamic, for example)?
> >
>
> I think a map is what I need from what you have said. The key can be
> extracted from the data.
Also, to clarify: when I said extracted I meant like a tooth - made
separate. It is not easy to somehow make a map<> refer to a field in
a value object. You will have to duplicate those (if the key is now
a field). See what I mean?
struct MyValue
{
string mykey;
int myactualdata;
};
map<MyValue::mykey, MyValue> mymap; // doesn't work
map<string, MyValue> mymap; // that's how you should do it
MyValue val = { string("Name"), 123 };
mymap.insert(make_pair(val.mykey, val)); // val.mykey will be
duplicated.
Good luck!
Dietmar Kuehl
In article <zWph5.93443$1h3.1...@news20.bellglobal.com>,
"Andrew" <akas...@sympatico.ca> wrote:
> I was wondering if anybody can tell me or point me to some stats on
> where a STL vector or list is better to use over a map and vice versa?
As you will have guessed from the discussion thus far, there is no
clear "use this" answer. The topic is actually fairly complex and
depends on lots more factors than those even mentioned that far. From
what I have seen so far my guess is that a 'std::vector' or a
'std::map' would be appropriate for your problem but it is hard to tell
given the information you have provided.
Basically, 'std::map' is good if you have a more or less random mix
of insert/remove, iteration, and lookup operations. If you just fill
your container once or at least insert/remove elements only fairly
infrequently, a sorted 'std::vector' is almost certainly better suited.
Probably the best approach is to use neither alternative! At least not
directly. Instead, introduce a class which supports the required
operations (and only those) and maps them to one of the possible
containers, probably using inline functions. The first approach looks
like 'std::map' is a good match for what you want to do. Then you try
your program and determine if it is running fast enough.
If it is running fast enough, you are done without bothering further.
Otherwise you have to determine where the bottleneck is. If it is
indeed at the container accesses, you just plug in another container
and profile the program again.
Also note that there are more options than 'std::vector', 'std::list',
and 'std::map'. 'std::deque' comes immediately to mind (although I have
not found anything where it is best for the stuff I'm doing...). If
the order in which elements are iterated over does not matter, a hash
may be appropriate. If the sequences of lookups normally lookup
elements which are "close" to each other, a splay tree might be in
order. ...or some combination of several approaches might yield the
desired performance.
--
<mailto:dietma...@yahoo.com>
<http://www.dietmar-kuehl.de/>
Sent via Deja.com http://www.deja.com/
Before you buy.