How could I obtain the common keys of two std::map?

Question

Suppose there are two c++ std::maps:

std::map<string, int> m1{{"n1", 1}, {"n2", 2}, {"n3", 3}};
std::map<string, int> m2{{"n2", 3}, {"n4", 2}, {"n1", 9}};

I would like to obtain a std::set that contains the common keys of the two maps.

std::set<string> common = ...;

I hope I can do it elegantly, so I better avoid using loops and it would be better if I can find some method in the std namespace or from <algorithm>, how could I do this?

Answer 1

Possible solution with a std::set_intersection:

template<class It>
class Key_iterator {
public:
    Key_iterator(It it) : it_(it) {}

    Key_iterator& operator++() {
        ++it_;
        return *this;
    }

    bool operator==(const Key_iterator& other) const {
        return it_ == other.it_;
    }

    bool operator!=(const Key_iterator& other) const {
        return it_ != other.it_;
    }

    auto operator*() const {
        return it_->first;
    }    

private:
    It it_;
};

std::map<std::string, int> m1{{"n1", 1}, {"n2", 2}, {"n3", 3}};
std::map<std::string, int> m2{{"n2", 3}, {"n4", 2}, {"n1", 9}};

std::vector<std::string> s;
std::set_intersection(Key_iterator(m1.begin()), Key_iterator(m1.end()),
        Key_iterator(m2.begin()), Key_iterator(m2.end()), std::back_inserter(s));

// s = {"n1", "n2"}

std::set_intersection requires both ranges to be sorted, and std::map keeps its keys in the sorted order. So they fit nicely.

---

If Boost is available, there is no need to code Key_iterator adapter. With boost::transform_iterator this code can be simplified to:

std::map<std::string, int> m1{{"n1", 1}, {"n2", 2}, {"n3", 3}};
std::map<std::string, int> m2{{"n2", 3}, {"n4", 2}, {"n1", 9}};

auto key_iterator = [](auto it) {
    return boost::transform_iterator(it, [](auto& p) { return p.first; });
};

std::vector<std::string> s;
std::set_intersection(key_iterator(m1.begin()), key_iterator(m1.end()),
    key_iterator(m2.begin()), key_iterator(m2.end()), std::back_inserter(s));