map to vector

[John]

How do I copy all the elements of a map to a vector
efficiently? The vector is empty initially and needs
to be populated with the map elements in sorted order.

Thanks,
--j

 

[Victor Bazarov]

How do I copy all the elements of a map to a vector
efficiently? The vector is empty initially and needs
to be populated with the map elements in sorted order.

(a) Reserve the space in the vector based on the size of the map.
See 'std::vector::reserve' member.

(b) Use std::copy and std::back_inserter.

Would you like to figure the code out yourself?

V

 

[John]

Damn Victor,

Sorry for being lazy, k will write it

Thanks,
--j

 

[John]

v.reserve(tmap.size());
copy(tmap.begin(), tmap.begin() + tmap.size(), v.begin());

but my tmap is map<K,I> and my vector v is vector<K>

Is this copy right?

 

[John]

This wont work , I need a tranform and a functor, anyone can help?
I want to copy all the elements of map<A,B> to vector<A>

 

[Alan Johnson]

v.reserve(tmap.size());
copy(tmap.begin(), tmap.begin() + tmap.size(), v.begin());

but my tmap is map<K,I> and my vector v is vector<K>

Is this copy right?

I don't think that std::copy is appropriate here. The value_type of
your map is std:air<K, I>, while the value_type of your vector is just
K. The former cannot be assigned to the latter. What you are looking
for is std::transform, which let's you provide a function that will
transform the pair into the appropriate value. Here is an example,
using types K and I as you did. Note that select1st and select2nd are
based on the descriptions given here:
http://www.sgi.com/tech/stl/table_of_contents.html

-Alan

#include <iostream>
#include <map>
#include <vector>
#include <iterator>
#include <algorithm>

template <typename Pair>
struct select1st
{
typedef Pair argument_type ;
typedef typename Pair::first_type result_type ;

const result_type &
operator()(const argument_type &p) const
{
return p.first ;
}
} ;

template <typename Pair>
struct select2nd
{
typedef Pair argument_type ;
typedef typename Pair::second_type result_type ;

const result_type &
operator()(const argument_type &p) const
{
return p.second ;
}
} ;

int main()
{
typedef const char * K ;
typedef int I ;

std::map<K, I> m ;
std::vector<K> vk ;
std::vector<I> vi ;

// Put some values into the map.
m["key1"] = 1 ;
m["key2"] = 2 ;
m["key3"] = 3 ;
m["key4"] = 4 ;

// Copy the keys to the vector.
vk.reserve(m.size()) ;
std::transform(m.begin(), m.end(), std::back_inserter(vk),
select1st<std::map<K, I>::value_type>()) ;

// Print the vector.
std::copy(vk.begin(), vk.end(),
std:stream_iterator<K>(std::cout, "\n")) ;

// Copy the values to the vector.
vi.reserve(m.size()) ;
std::transform(m.begin(), m.end(), std::back_inserter(vi),
select2nd<std::map<K, I>::value_type>()) ;

// Print the vector.
std::copy(vi.begin(), vi.end(),
std:stream_iterator<I>(std::cout, "\n")) ;

return 0 ;
}

 

[Prawit Chaivong]

(a) Reserve the space in the vector based on the size of the map.
See 'std::vector::reserve' member.

(b) Use std::copy and std::back_inserter.

Would you like to figure the code out yourself?

V

Hi,
- Is 'reserve' better than 'resize' (in performance perspective)?

 

[Alan Johnson]

Hi,
- Is 'reserve' better than 'resize' (in performance perspective)?

reserve (potentially) changes the _capacity_ of the vector, while resize
changes the _size_ of the vector. Think of capacity as the number of
elements the vector space to hold before it needs to allocate more
space, whereas size would be the number of things it is actually holding.

Consider the following code fragment:

std::vector<SomeType> v ;
v.resize(3) ;

This actually creates 3 new objects of type SomeType (and calls their
constructors when they are created). At this point, v[0], v[1], and
v[2] are all valid expressions.

Now consider doing the same thing with reserve:

std::vector<SomeType> v ;
v.reserve(3) ;

This doesn't create any new objects, it just causes the vector to
allocate (at least) enough space to hold 3 objects of type SomeType
before it has to do any reallocating. v[0], v[1], and v[2] are NOT
valid expressions, as we still need to actually put some objects in it,
via some method such as push_back, or as Victor suggested, with a
back_insertion_iterator.

-Alan

 

[Mike Smith]

This wont work , I need a tranform and a functor, anyone can help?
I want to copy all the elements of map<A,B> to vector<A>

You need a vector<pair<A,B> > instead of a vector<A>. The elements of a
map<A,B> are of type pair<A,B>.

 

[Victor Bazarov]

Hi,
- Is 'reserve' better than 'resize' (in performance perspective)?

I am not sure what you mean by "better". They do different things.
'resize' resizes. 'reserve' doesn't change anything except if the
current storage is smaller, reallocates the storage. 'resize' adds
to the vector. 'reserve' only affects the future 'push_back' or
'insert'.

V