CODEWITHSUNDEEP
c++booststl
Michael
Michael

Reputation: 1502

Faster alternative to STL std::map

I do have a data structure:

typedef std::pair<boost::shared_ptr<X>, boost::shared_ptr<X> > pair_ptr;
std::map< pair_ptr, int >

that I use in a iterative process. In each iteration I need to copy the the std::map and possibly destroy one copy. However, the std::map can become large, over 100k elements. This significantly slows down the program. I've defined the operator< as:

   inline bool operator<(const pair_ptr& a, const pair_ptr& b) 
   { 
   return (a.first < b.first) or 
        (a.first == b.first and a.second < b.second);
   }

I use the std::map copy constructor and destructor. Is there a faster alternative?

Upvotes: 2

Views: 2790

Answers (1)

davidbak
davidbak

Reputation: 5999

You have a lot of choices - and we can suggest design alternatives but don't have enough information to make them for you.

Here are three things you could do:

  1. Can you make the key a pointer to the pairs (and adjust the comparison appropriately) so that the pairs themselves (containing two refcnt'd ptrs) don't have to be copied?

  2. In each iteration - do you need the expected O(log n) insertion/deletion time? If you can live with O(n) insertion/deletion then can you use a sorted vector as the container instead of a map? (So that you allocate/free the container in one shot instead of allocate/free lots of little tree nodes.) (Remember: a std::map isn't the only data structure you can search in, not even the only std:: data structure. All searchable data structures will work, just choose the one that has the appropriate complexity guarantees, modulo your knowledge of the "constants" (e.g., heap allocation is expensive), for your use case.)

  3. Can you (do you) manage the lifetimes of the two things the key is pointing at independent of the map, and this iterative process? If so you can have a key of a pair of naked pointers, which will be faster than ref cnt'd pointers on creation of the new map at each iterator. You can have a separate set of ref cnt'd pointers to all your things, and manage the lifetime of these objects there.

These can be combined, too. Just some ideas to get you started.

Upvotes: 3

Related Questions