CODEWITHSUNDEEP
c++dictionarystdset-intersection
Aditya
Aditya

Reputation: 1268

Set intersection in C++ on the keys of a map

I have two maps

map<string, int> word_count1, word_count2;

I am trying to find the set intersection between these two maps. Using the set_intersection method in std::algorithms.

map<string, int> intersection;
set_intersection(word_count1.begin(), word_count1.end(), 
                 word_count2.begin(), word_count2.end(), 
                 inserter(intersection, intersection.begin()), 
                  [](pair<string, int> p1, pair<string, int>p2){
                           return p1.first != p2.first;
                  });

I've tried this without the comparison function, with word_count1.key_comp() and the above lambda based comparison function.

I know for a fact that

  1. There is data in both the maps.
  2. The intersection is not empty.

However, when I check the values in the intersection map I find nothing.

I've also tried this without the inserter and the return value I get back from the function call indicates that there are not values! What am I doing wrong?

Upvotes: 1

Views: 1591

Answers (2)

catnip
catnip

Reputation: 25388

You need to modify the lambda slightly. The comparison operation is operator<, not operator==, so you need something like:

std::set_intersection
    (word_count1.begin(), word_count1.end(), 
     word_count2.begin(), word_count2.end(), 
     inserter (intersection, intersection.begin()),
     [](const std::pair<std::string, int> &p1, const std::pair<std::string, int> &p2)
         {return p1.first < p2.first;});

Note also that it is better to pass the parameters to the lambda as const ref as this avoids unnecessary copies, and that for C++14 and later, the lambda can be simplified to:

 [](const auto &p1, const auto &p2)
     {return p1.first < p2.first;});

Live demo

Upvotes: 4

Striezel
Striezel

Reputation: 3758

There seems to be a slight misunderstanding about the comparison operator of std::set_intersection. The comparator function (or lambda) has to return true, if the first element is less than the second element. Therefore, both != and == do not return the proper (i. e. expected) result. Change the operator and it works:

std::set_intersection(word_count1.begin(), word_count1.end(),
             word_count2.begin(), word_count2.end(),
             inserter(intersection, intersection.begin()),
              [](std::pair<std::string, int> p1, std::pair<std::string, int>p2){
                       // Compare with less than operator here.
                       return p1.first < p2.first;
              });

A full working example could be:

#include <algorithm>
#include <iostream>
#include <map>
#include <string>

int main(int argc, char** argv)
{
  std::map<std::string, int> word_count1 = {
    { "foo", 1 },
    { "bar", 3 },
    { "baz", 5 }
  };

  std::map<std::string, int> word_count2 = {
    { "foo", 4 },
    { "qux", 2 },
    { "baz", 5 },
    { "quux", 6 }
  };


  std::map<std::string, int> intersection;
  std::set_intersection(word_count1.begin(), word_count1.end(),
      word_count2.begin(), word_count2.end(),
      inserter(intersection, intersection.begin()),
      [](std::pair<std::string, int> p1, std::pair<std::string, int>p2){
          return p1.first < p2.first;
      }
  );

  for(const auto & elem: intersection)
  {
    std::cout << elem.first << " " << elem.second << "\n";
  }
}

The output in that case is:

baz 5
foo 1

(Tested with GCC 7.4.0.)

Upvotes: 3

Related Questions