Z
zaineb
Hi,
This is a follow-up of sort of this thread:
http://groups.google.com/group/comp...++vector+vs+map&rnum=1&hl=en#662cab752779f1fa
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()+indexSubscript ). 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
This is a follow-up of sort of this thread:
http://groups.google.com/group/comp...++vector+vs+map&rnum=1&hl=en#662cab752779f1fa
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()+indexSubscript ). 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