Saturday, November 27, 2010

Trick to Reducing the Copying of Large Vectors into Maps

When calling insert() on a map object. The value_type is copied once.

If you have a map from something to large vectors, to insert into that map, you would first call value_type(). This would cause
the large vector to be copied. When you call insert(), the large vector would be copied a second time.

Here is a technique to get rid of one of the large vector copies:

#include <iostream>
#include <map>
using namespace std;

namespace {
   typedef vector<unsigned> MyVectorType;
   typedef map<unsigned, MyVectorType, less<unsigned> > U2VU;
   U2U  g_myU2U (less<unsigned>());
   U2VU g_myU2VU(less<unsigned>());
} // end unnamed namespace

int main()
   MyVectorType myVector;
   U2VU::value_type vt1(1,MyVectorType());
   U2VU::value_type vt2(2,MyVectorType());
   pair<U2VU::iterator, bool> ret;
   ret = g_myU2VU.insert(vt2);
   if (ret.second == true) { // This means the key was not already there, 
                             // so the item was inserted.
      std::cout << "Inserting vector into map via iterator" << std::endl;
      ret.first->second = myVector;
   std::cout << "U2VU has " << g_myU2VU.size() << " items in it." << std::endl;
   return 0;

The trick was to insert a value_type() with an empty vector, and then use the returned iterator to set the vector part to the large vector, thus saving a copy of the large vector.

No comments:

Post a Comment