Ok, I've got a vector I've filled with a LOT of data, and after massaging it
just right, I need to copy it all over to a map where I'll have the
advantage of assigning a custom key as the key attribute to do fast lookups.
Is there an STL treasure that will help me do this copy without choking my
computer with the heavy memory demand? It looks like both vectors and maps
have their own 'swap' member functions, but I need something that crosses
the container barrier. Any advice would be greatly appreciated.
d 7 1678
deancoo wrote: Ok, I've got a vector I've filled with a LOT of data, and after
massaging it just right, I need to copy it all over to a map where I'll have the advantage of assigning a custom key as the key attribute to do fast
lookups. Is there an STL treasure that will help me do this copy without
choking my computer with the heavy memory demand? It looks like both vectors
and maps have their own 'swap' member functions, but I need something that
crosses the container barrier. Any advice would be greatly appreciated.
If your vector already has 'std::pair's in it, you can use
'map::insert'. Otherwise you have to assign key values to your vector
elements some other way, e.g., by looping over the vector elements,
creating pairs, and inserting them into the map. /david
"deancoo" <s2*******@yahoo.ca> wrote in message
news:9iDVd.35396$hN1.7722@clgrps13... Ok, I've got a vector I've filled with a LOT of data, and after massaging it just right, I need to copy it all over to a map where I'll have the advantage of assigning a custom key as the key attribute to do fast lookups. Is there an STL treasure that will help me do this copy without choking my computer with the heavy memory demand? It looks like both vectors and maps have their own 'swap' member functions, but I need something that crosses the container barrier. Any advice would be greatly appreciated.
Fast look-up is not a good reason to use an std::map -- don't use it
if you have the data you need already stored in a (sorted) vector.
An std::map is only efficient when you need to dynamically insert/remove
items while keeping the collection sorted.
using std::lower_bound (does a binary search) on a sorted vector is most
likely faster than looking-up an item in a map. Or eventually you could
use a separate index, storing pointers into the vector.
hth -Ivan
-- http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
"Ivan Vecerina" <NO**********************************@vecerina.com > wrote in
message news:d0**********@news.hispeed.ch... "deancoo" <s2*******@yahoo.ca> wrote in message news:9iDVd.35396$hN1.7722@clgrps13... Ok, I've got a vector I've filled with a LOT of data, and after massaging it just right, I need to copy it all over to a map where I'll have the advantage of assigning a custom key as the key attribute to do fast lookups. Is there an STL treasure that will help me do this copy without choking my computer with the heavy memory demand? It looks like both vectors and maps have their own 'swap' member functions, but I need something that crosses the container barrier. Any advice would be greatly appreciated.
Fast look-up is not a good reason to use an std::map -- don't use it if you have the data you need already stored in a (sorted) vector. An std::map is only efficient when you need to dynamically insert/remove items while keeping the collection sorted.
using std::lower_bound (does a binary search) on a sorted vector is most likely faster than looking-up an item in a map. Or eventually you could use a separate index, storing pointers into the vector.
hth -Ivan
Good point. What might be good container to hold such an index? Let me go
into a little bit more detail. The key I would like to use to identify my
objects is almost like a hash or even a check sum. It is very fast and easy
to produce, and completely unique, however quite disjointed. So off the top
of my head, it (the index) might be a vector, storing pairs (key, *ptr_obj)?
Then do something like overload the < operator to allow lower_bound to be
able to search on the 'key' attribute of the pair? Does this sound about
right?
d
"deancoo" <s2*******@yahoo.ca> wrote in message
news:9MLVd.25930$TB.14639@edtnps84... "Ivan Vecerina" <NO**********************************@vecerina.com > wrote in message news:d0**********@news.hispeed.ch... using std::lower_bound (does a binary search) on a sorted vector is most likely faster than looking-up an item in a map. Or eventually you could use a separate index, storing pointers into the vector.
hth -Ivan
Good point. What might be good container to hold such an index? Let me go into a little bit more detail. The key I would like to use to identify my objects is almost like a hash or even a check sum. It is very fast and easy to produce, and completely unique, however quite disjointed. So off the top of my head, it (the index) might be a vector, storing pairs (key, *ptr_obj)? Then do something like overload the < operator to allow lower_bound to be able to search on the 'key' attribute of the pair? Does this sound about right?
Yes, you could do that.
An alternative would be to have one vector with the objects, and one vector
with the keys, sorted in sync (best way to obtain this depends on details).
Searching a linearly sorted vector of (only)keys is nearly optimum in terms
of cache usage (only eventually beaten by a heap-based structure).
Cheers,
Ivan
-- http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
"Ivan Vecerina" <IN*************************@vecerina.com> wrote in message
news:d0**********@news.hispeed.ch... "deancoo" <s2*******@yahoo.ca> wrote in message news:9MLVd.25930$TB.14639@edtnps84... "Ivan Vecerina" <NO**********************************@vecerina.com > wrote in message news:d0**********@news.hispeed.ch... using std::lower_bound (does a binary search) on a sorted vector is most likely faster than looking-up an item in a map. Or eventually you could use a separate index, storing pointers into the vector.
hth -Ivan
Good point. What might be good container to hold such an index? Let me go into a little bit more detail. The key I would like to use to identify my objects is almost like a hash or even a check sum. It is very fast and easy to produce, and completely unique, however quite disjointed. So off the top of my head, it (the index) might be a vector, storing pairs (key, *ptr_obj)? Then do something like overload the < operator to allow lower_bound to be able to search on the 'key' attribute of the pair? Does this sound about right? Yes, you could do that. An alternative would be to have one vector with the objects, and one vector with the keys, sorted in sync (best way to obtain this depends on details). Searching a linearly sorted vector of (only)keys is nearly optimum in terms of cache usage (only eventually beaten by a heap-based structure).
Cool. That's going to work awesome. Thanks.
deancoo wrote: [...] So off the top of my head, it (the index) might be a vector,
storing pairs (key, *ptr_obj)? Then do something like overload the
< operator to allow lower_bound to be able to search on the 'key'
attribute of the pair? Does this sound about right? Yes, you could do that. An alternative would be to have one vector with the objects, and
one vector with the keys, sorted in sync (best way to obtain this depends on details). Searching a linearly sorted vector of (only)keys is nearly optimum
in terms of cache usage (only eventually beaten by a heap-based structure).
Cool. That's going to work awesome. Thanks.
If you've already got 'std::pair's, you may as well use a map. It's
much easier. Once you have it working, you can profile to find
performance bottlenecks. I'm quite sure that the constant factor
differentiating std::map::find and std::lower_bound is not going to be
in the top 10.
/david
<da********@warpmail.net> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com... deancoo wrote:
>> [...] So off the top of my head, it (the index) might be a vector, >> storing pairs (key, *ptr_obj)? Then do something like overload the < >> operator to allow lower_bound to be able to search on the 'key' attribute >> of the pair? Does this sound about right? > Yes, you could do that. > An alternative would be to have one vector with the objects, and one > vector > with the keys, sorted in sync (best way to obtain this depends on > details). > Searching a linearly sorted vector of (only)keys is nearly optimum in > terms > of cache usage (only eventually beaten by a heap-based structure).
Cool. That's going to work awesome. Thanks.
If you've already got 'std::pair's, you may as well use a map. It's much easier. Once you have it working, you can profile to find performance bottlenecks. I'm quite sure that the constant factor differentiating std::map::find and std::lower_bound is not going to be in the top 10.
/david
Ya, using map is really tempting because of the ease. Since one of the
reasons I'm building this app is to get myself back into C++, I think I'll
try implementing both. Thanks again guys.
d This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Christopher Jeris |
last post by:
Please help me understand the differences, in semantics, browser
support and moral preferredness, between the following three methods
of swapping content in and out of a page via JavaScript. I...
|
by: alanrn |
last post by:
I am using a TreeView to display the hierarchy of a strongly-typed collection
(inherited from CollectionBase). The order of the nodes in the TreeView is
strictly tied to the order in which they...
|
by: Jatinder |
last post by:
I found these questions on a web site and wish to share with all of u
out there,Can SomeOne Solve these Porgramming puzzles.
Programming Puzzles
Some companies certainly ask for these...
|
by: Ann |
last post by:
I am opening a file which looks like 0xABCDEF01 on another machine but
0x01EFCDAB on my machine.
Is this a byte swapping?
Could anyone give a good way to check if bytes are being swapped?...
|
by: bcomeara |
last post by:
I am writing a program which needs to include a large amount of data.
Basically, the data are p values for different possible outcomes from
trials with different number of observations (the p...
|
by: Howard |
last post by:
Hi all,
is there an easy way to swap one pointer item in a vector with a pointer
that's not yet in the vector?
Currently, I'm using begin()+index to get an iterator to the item I want
to swap...
|
by: Rob |
last post by:
How would I do this?
I want to be able to handle vectors of many different types of data
and vectors that can contain any number of other vectors of data.
Currently, I have a templated...
|
by: oktayarslan |
last post by:
Hi all;
I have a problem when inserting an element to a vector. All I want is
reading some data from a file and putting them into a vector. But the
program is crashing after pushing a data which...
|
by: Juha Nieminen |
last post by:
Assume we have this:
std::list<Typelist1(10, 1), list2(20, 2);
std::list<Type>::iterator iter = list1.end();
list1.swap(list2);
What happens here, according to the standard?
1) 'iter'...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |