如何获取两个std::map的公共键？

Question

假设有两个 C++ 的 std::map：

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

我希望获得一个std::set，其中包含两个映射的公共键。

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

我希望能够优雅地完成它，因此最好避免使用循环，如果能够在std命名空间或<algorithm>中找到一些方法，那就更好了。我该怎么做呢？

- coin cheung

---

这个回答解决了你的问题吗？如何找到两个映射中共同的键？ - t.niese

理论上，你可以将std::transform和std::erase_if结合起来使用，如果你不想直接使用循环的话。但更高效的方法是使用可能重复的问题的被接受答案。 - t.niese

使用std::set_intersection怎么样？ - Jesper Juhl

Answer 1

可以使用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需要对两个范围进行排序，而std::map会按照键的顺序进行排序，因此它们非常匹配。

---

如果Boost可用，则无需编写Key_iterator适配器。使用boost::transform_iterator，可以简化此代码：

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));

- Evg

---

真的很喜欢那个Key_iterator解决方案。现在正在做很多map算法，这对我帮助很大。 - Narase

Answer 2

要找到共同的键，你需要过滤掉m1中键不在m2中的项目，然后提取键。不幸的是，在<algorithm>中没有transform_if或任何组合的过滤/映射操作，因此如果你使用的是纯算法，则需要两步操作：

std::map<string, int> common_m;
std::copy_if(
    m1.begin(), m1.end(), 
    std::inserter(common_m, common_m.end()), 
    [&m2](auto&& kv) { return m2.find(kv.first) != m2.end(); });

std::set<string> common_keys;
std::transform(
    common_m.begin(), common_m.end(), 
    std::inserter(common_keys, common_keys.end()), 
    [](auto&& kv) { return kv.first; });

演示 - https://godbolt.org/z/6982Pm

<algorithm>中的组合步骤很笨拙，因为没有惰性操作，每个操作都必须在新容器中实现。

ranges-v3库解决了这个问题，并已被纳入C++20标准作为Ranges TS。它允许使用ML风格的惰性操作进行组合，使这个过程可以变成一行代码：

std::set<string> common_keys = m1
    | views::remove_if([&m2](auto&& kv) { return m2.find(kv.first) == m2.end(); })
    | views::transform([](auto&& kv) { return kv.first; })
    | to<std::set>;

演示 - https://godbolt.org/z/CKUFFz

- parktomatomi