查找3个C ++中1个唯一的单词

Question

我有3个包含单词的集合。

a: car, boat, table, ball

b: car, goat, helicopter

c: square, car, goat, boat

我需要创建一个向量或仅包含集合a中包含的单词的集合。

所以答案将是：

result: table, ball

我试图使用set_difference和set_intersection使其实现，但到目前为止还没有运气。你能建议我一些吗？

我尝试过

set_difference(a.begin(), a.end(), b.begin(), b.end(), res.begin()); 
set_difference(res.begin(), res.end(), c.begin(), c.end(), res.begin());

但是结果为空

Answer 1

您的错误在这里：

set_difference(res.begin(), res.end(), c.begin(), c.end(), res.begin());
//             ^            ^                              ^

您迭代res并将结果写在同一组中。您需要另一组存储结果。

解决方案将是：

std::set<std::string> a {"car", "boat", "table", "ball"};
std::set<std::string> b {"car", "goat", "helicopter"};
std::set<std::string> c {"square", "car", "goat", "boat"};

std::set<std::string> tmp;
std::set<std::string> res;

// Difference between a and b --> stored in tmp
std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::inserter(tmp, tmp.begin()));

// Difference between tmp and c --> stored in res
std::set_difference(tmp.begin(), tmp.end(), c.begin(), c.end(), std::inserter(res, res.begin()));

for(const std::string & s : res)
    std::cout << s << '\n';

输出：

球表格

Live example

---

注意：如果查看std::set_difference的文档，我们可以看到：

将在排序范围[first2，last2）中找不到的元素从排序范围[first1，last1）复制到从d_first开始的范围。

结果范围也已排序。 等效元素被单独对待，也就是说，如果某个元素在[first1，last1）中被发现m次，在[first2，last2）中被发现n次，它将被精确地复制到d_first std :: max（mn，0）次。结果范围不能与任何一个输入范围重叠。

^重点矿

因此，如果要使用另一个不能保证其元素唯一性的容器（例如std::set_difference，则需要确保每个元素在您的容器中不会多次出现。

---

注2：如果您不想打扰std::vector设置（在获得tmp设置之后就没用了），可以将其放在一个块内，以便以后将其销毁：

res

std::set<std::string> res;

{
    std::set<std::string> tmp;
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::inserter(tmp, tmp.begin()));
    std::set_difference(tmp.begin(), tmp.end(), c.begin(), c.end(), std::inserter(res, res.begin()));
} // tmp destroyed here

Answer 2

如果不共享您的代码，我们只能猜测您的代码在做什么错。

这是我所做的。我将差异逻辑包装在助手Live example中。我故意使用了operator-，因为它们不能直接在std::unordered_set中使用。

由于我的答案可能会被否决，因此我将在以后删除它。

std::set_difference

UPDATE回答Fareanor的问题

为什么使用std :: unordered_set（而不是std :: set）？

我选择了unordered_set来证明set_difference需要排序的容器。 unordered_set缺少该功能。

并且在原始未经编辑的问题中，原始张贴者未提供使用哪种容器的详细信息。

为什么将其转换为需要排序的std :: vector（而不是转换为std :: set）？

向量是一个非常有效的容器，因为其中的元素具有局部性，因此具有良好的缓存。这是我的首选容器。

一个集合具有更多的内存分配，因为它是节点的网格，并且缺乏局部性。

所包含的字符串对象无论如何都可能缺少局部性，因为它基本上是指向字符数组的智能指针。但是由于小字符串优化（SSO）并且这些都是小字符串，因此它也不会在堆外分配。

在原始海报的情况下，每个容器中只有几件物品，因此效率问题可以忽略不计。但是值得考虑的是，如果问题域扩大了。

我认为您应该使用std :: set（至少没有OP的任何说明），并且如果用户获得了std :: unordered_set，则由他决定将其转换为合适的std :::设置然后呼叫您的

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <unordered_set>
#include <vector>

using std::cout;
using std::inserter;
using std::ostream;
using std::set_difference;
using std::sort;
using std::string;
using std::unordered_set;
using std::vector;

namespace {

unordered_set<string> operator-(unordered_set<string> const& minuend, unordered_set<string> const& subtrahend) {
    vector<string> m(minuend.begin(), minuend.end());
    vector<string> s(subtrahend.begin(), subtrahend.end());
    sort(m.begin(), m.end());
    sort(s.begin(), s.end());
    unordered_set<string> diff;
    set_difference(m.begin(), m.end(), s.begin(), s.end(), inserter(diff, diff.begin()));
    return diff;
}

ostream& operator<<(ostream& out, unordered_set<string> const& container) {
    char const* sep = " ";
    out << "{";

    for (auto const& s : container) {
        out << sep << "\"" << s << "\"";
        sep = ", ";
    }
    out << " }";
    return out;
}

}

int main() {
    auto a = unordered_set<string>{ "car", "boat", "table", "ball" };
    auto b = unordered_set<string>{ "car", "goat", "helicopter" };
    auto c = unordered_set<string>{ "square", "car", "goat", "boat" };
    auto d = a - b - c;
    cout << d << "\n";
}

。

这是一个可行的选择。当时缺乏上下文，我认为这是“最糟糕的情况”，因为unordered_set容器不能满足set_difference算法的要求。