在两个完全不同的容器上使用std::set_intersection

Question

在两个完全不同的容器上使用std::set_intersection

4

我有一个简单的需求，需要在另一个向量中的主字符串列表中查找一个向量中的字符串出现次数。一开始我可以轻松地使用以下代码实现：

vector<string> custom_list;
set<string> master_list;
vector<string> target_list;

std::sort(custom_list.begin(), custom_list.end());
std::set_intersection(custom_list.begin(), custom_list.end(), master_list.begin(),
                      master_list.end(), back_inserter(target_list));

这个方案一开始很好用。但是后来发现 master_list 中的每个字符串都与一个标识符相关联。我希望能够以这样的方式使用 std::set_intersection，即可以使用目标列表中的交集元素作为索引来获取它们的标识符。实际上，我想把 master_list 更改为一个 map，如下所示：

map<string, SomeCustomId> master_list;

并且能够做到像这样：

auto I_want_this_id = master_list[target_list[0]);

但是现在我不确定是否可以使用set_intersection来比较两个完全不同的容器（custom_list，一个向量和master_list，一个映射），即使我编写自己的比较函数。类似于：

struct mycomparer {
    bool operator()(string const& lhs, pair<string, SomeCustomId> const& rhs) {
        return lhs == rhs.first;
    }
};

这种方法并不能很好地实现目标（我收到了各种编译器错误），直觉上也感觉有些不对。

有没有更好的方法来实现我想做的事情呢？

- ForeverLearning

2个回答

1

算法其实并不关心容器，它们关心的是迭代器。只要两种容器类型都满足算法的迭代器要求，并且你的元素类型与比较器匹配，兼容性就不应该成为问题。

因此，从根本上说，你所做的是可以的。

但是，你需要纠正比较器中的逻辑错误; operator() 应该实现小于谓词。正如 T.C. 指出的那样，你需要显式地实现反向比较，因为元素类型不能隐式转换为彼此。

- Lightness Races in Orbit

@Dilip：如果您只能比较元素是否相等，如何在线性时间内确定两个范围的交集？ - T.C.

@T.C. 两个输入范围都需要排序，鉴于此，您只需要迭代其中一个。 - Lightness Races in Orbit

@T.C. Oh，好的，我现在明白你当时是在对Dilip的提案进行提问，而且你实际上已经知道了所有这些。所以没关系:) 是的，如果没有<或>，你就没办法了。 - Lightness Races in Orbit

@LightnessRacesinOrbit 看起来我试图做的基本上是不可以的 :-) 我试图在为vector<string>提供back_inserter的同时在set_intersection中使用不同的容器。看起来我所要做的就是交换set_intersection的前四个参数的顺序（先是map，后是vector），这会让我陷入麻烦。 - ForeverLearning

@Dilip 标准规定必须从第一个提供的范围中复制值。但是您显然是正确的，如果交换范围，将会出现编译错误。 - T.C.

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- T.C. · Accepted Answer

std::set_intersection函数需要一个比较器，如果lhs < rhs返回true，而不是lhs == rhs。此外，它还必须能够比较其两个参数，无论顺序如何（毕竟，确定参数是否等效是通过(!comp(a, b) && !comp(b, a))来完成的）。

因此，您需要像这样的代码：

struct mycomparer {
    bool operator()(string const& lhs, pair<string const, SomeCustomId> const& rhs) {
        return lhs < rhs.first;
    }
    bool operator()(pair<string const, SomeCustomId> const& lhs, string const& rhs) {
        return lhs.first < rhs;
    }
};

演示。

编辑：已更新演示代码，包括所有必要的头文件（<iterator> 和 <string> 丢失了。它们可能被 GCC 中的其他头文件包含，但在 VC++ 中没有）。

VC++ 2012 在进行调试构建时，似乎对提供的谓词运行了一些额外的测试。这会导致编译失败，并出现类似于“error C2664: 'bool mycomparer::operator ()(const std::pair<_Ty1,_Ty2> &,const std::string &)' : 无法将参数1从'std::basic_string<_Elem,_Traits,_Alloc>'转换为'const std::pair<_Ty1,_Ty2>&'” 的错误。（一旦修复了头文件并切换到旧的初始化样式，它在发布版本上可以正常编译。）

要解决此问题，请提供重载 operator ()，以使用所有四个可能的参数组合：

struct mycomparer {
    bool operator()(string const& lhs, pair<string const, SomeCustomId> const& rhs) {
        return lhs < rhs.first;
    }
    bool operator()(pair<string const, SomeCustomId> const& lhs, string const& rhs) {
        return lhs.first < rhs;
    }
    bool operator()(string const& lhs, string const& rhs) {
        return lhs < rhs;
    }
    bool operator()(pair<string const, SomeCustomId> const& lhs,
                    pair<string const, SomeCustomId> const& rhs) {
        return lhs.first < rhs.first;
    }
};

编辑2：如果您可以使用Boost.Range，那么它会更容易。只需：

boost::set_intersection(custom_list, 
                        master_list | boost::adaptors::map_keys,
                        back_inserter(target_list));

没有需要自定义谓词，同时也非常易读。演示。