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 这样一种方式，即我可以使用 target_list 中的相交元素作为索引来获取它们的标识符。实际上，我认为我会将 master_list 更改为地图，如下所示：

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

这不太奏效（我遇到了各种编译器错误），而且直观地说，这对我来说有些不对劲。

有没有更好的方法来完成我想做的事情？

4

2 回答 2

4

std::set_intersection期望返回trueif的比较器lhs < rhs，而不是 if 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 &)' : cannot convert parameter 1 from 'std::basic_string<_Elem,_Traits,_Alloc>' to '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));

不需要自定义谓词，而且可读性也很强。演示。

于 2014-05-24T15:58:17.317 回答
1

算法并不真正关心容器。他们关心迭代器，只要两种容器类型都满足算法的迭代器要求，并且您的元素类型与比较器匹配，兼容性应该不是问题。

所以，从根本上说，你在做什么是好的。

但是，您需要更正比较器中的逻辑；operator()应该实现小于谓词。而且，正如 TC 指出的那样，您需要显式地实现反向比较，因为元素类型之间不能隐式转换。

于 2014-05-24T16:06:02.080 回答