CODEWITHSUNDEEP
c++data-structures
yesraaj
yesraaj

Reputation: 47900

How to convert a vector<pair<int,int> > to multimap<int,int> efficiently?

How to convert a multimap<int,int> to vector<pair<int,int> > efficiently

EDIT: Sorry for the trouble I was actually looking for converting vector to map

Upvotes: 1

Views: 1825

Answers (2)

Bojan Resnik
Bojan Resnik

Reputation: 7378

The value type of a multimap<int,int> is pair<int,int> - exactly what you would like your vector to hold. So, you can use the constructor to initialize the vector from the multimap:

std::vector< std::pair<int,int> > v( mmap.begin(), mmap.end() );

Or, if you have an existing vector where you want to copy the elements:

v.resize( mmap.size() );
std::copy( mmap.begin(), mmap.end(), v.begin() );

You can also use the std::back_inserter, but that would be slower in general due to vector reallocations:

std::copy( mmap.begin(), mmap.end(), std::back_inserter(v) );

EDIT To answer your other question - you can convert a vector to a multimap in a similar way. The multimap also has a constructor which accepts an iterator range:

std::multimap<int,int> mmap(v.begin(), v.end());

This, of course, assumes that v is std::vector< std::pair<int,int> >.

Upvotes: 4

Martin v. L&#246;wis
Martin v. L&#246;wis

Reputation: 127447

I believe that the naive approach is also the most efficient one: iterate over the multimap, and add each element to the vector. As an optimization, you should v.reserve(m.size) before you start.

The elements are typically stored in a tree in the multimap, in objects spread over the heap. For the vector, they must be in contiguous memory: this requires that you really have to copy them together.

Upvotes: 1

Related Questions