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

Question

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

Answer 1

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.

Answer 2

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> >.

Answer 3

I am trying to find duplicates in a multimap consisting of vectors of structs.

multimap::iterator,vector::iterator> mymm;

multimap::iterator,vector::iterator>::iterator it; pair::iterator,vector::iterator>::iterator,multimap::iterator,vector::iterator>::iterator> ret;

Can anyone please help me solve this problem. I can do it with simple vectors of int or string but I dont know how to compare a vector of structs in multimap.

for (vector::iterator itr = v.begin(); itr != v.end(); itr++) { cout << itr->x << " =>";

ret = mymm.equal_range(itr);

for (it = ret.first; it != ret.second; ++it)
{
    //c++;
    cout << " " << ((*it).second)->x << endl;
    }
 }

}

where MyPred is the struct containing int variables x, y, z.