CODEWITHSUNDEEP
c++listiteratoruniquemultimap
Alessandro Jacopson
Alessandro Jacopson

Reputation: 18603

In C++ `multimap`, how can I get efficiently a collection of the `mapped_type` elements without the duplicates?

I have a std::multimap< int, std::string > like that:

1 A
1 B
1 C
1 B
1 C
1 C

and I would like to get a collection of mapped_type elements with no duplicates, like that:

1 A
1 B
1 C

My solution is like this:

#include <map>
#include <list>
#include <string>
#include <algorithm>

int main(int argc, char* argv[])
{
   std::multimap< int, std::string > mm;
   mm.insert( std::make_pair(1,"A") );
   mm.insert( std::make_pair(1,"B") );
   mm.insert( std::make_pair(1,"C") );
   mm.insert( std::make_pair(1,"B") );
   mm.insert( std::make_pair(1,"C") );
   mm.insert( std::make_pair(1,"C") );

   auto range( mm.equal_range(1) );

   std::list< std::string > ss;
   std::transform(range.first, range.second, 
                  std::back_inserter(ss), 
                  [](const std::pair<int,std::string>& p) {
                      return p.second;
                  });
   ss.sort();
   ss.unique();
   return 0;
}

Is there any more efficient way to get the collection?

Upvotes: 2

Views: 156

Answers (2)

ltjax
ltjax

Reputation: 15997

Algorithmically, this is already the most efficient way. Bulk operations like sort and unique almost always trump online operations like set-inserts by constant factors.

That said, it is usually recommended to stay away from node-based containers like list, map and set when performance is key. You could switch to std::vector, std::sort and std::unique, but in your example, that might not be faster, since moving around strings might actually be slower than rearranging list-nodes. If you have move-support and no small-string optimizations active, if might be worth a try.

Upvotes: 2

Joseph Mansfield
Joseph Mansfield

Reputation: 110658

You can use a std::set, which only allows unique values, instead of a std::list:

std::set<std::string> ss;
std::transform(range.first, range.second, 
               std::inserter(ss, ss.begin()), 
               [](const std::pair<int,std::string>& p) {
                   return p.second;
               });

Now you don't have to use sort or unique.

Upvotes: 2

Related Questions