合并多个STL容器的最佳方法，删除重复元素？

Question

合并多个STL容器的最佳方法，删除重复元素？

9

我有两个STL容器，想要将它们合并，同时删除出现多次的元素。例如：

typedef std::list<int> container;
container c1;
container c2;

c1.push_back(1);
c1.push_back(2);
c1.push_back(3);

c2.push_back(2);
c2.push_back(3);
c2.push_back(4);

container c3 = unique_merge(c1, c2);
// c3 now contains the following 4 elements:
//   1, 2, 3, 4

std::unique似乎只适用于相邻元素，而在我的情况下，容器可以是任意顺序的。我想我可以使用一些std::set技巧：

container unique_merge(const container& c1, const container& c2)
{
    std::set<container::value_type> s;
    BOOST_FOREACH(const container::value_type& val, c1)
        s.insert(val);
    BOOST_FOREACH(const container::value_type& val, c2)
        s.insert(val);
    return container(s.begin(), s.end());
}

有没有更好的方法或者我错过了什么非常明显的东西？

- Rob

如果你要求的是“显而易见”的东西，那么你的实现对于大多数情况已经足够好了。但是确实存在一种更好的算法，代价是O(N * log(M))，其中N是所有容器中元素的总数，M是容器的数量。这段代码并不简单，我会在有时间的时候写出来。 - RnMss

@RnMss 真的吗？你能发表一个答案吗？... - user202729

@user202729 哇，那是在2014年的事情了... - RnMss

@user202729 现在我不太确定。我认为，根据我写的内容，可能当时我认为每个容器都已经排序了，但容器的数量可能会更多（比如1000个或更多）。 - RnMss

3个回答

4

你需要对内容进行排序（可以明确排序，也可以通过类似set的排序容器隐式排序）。

有一个常见的用法是使用std::sort/std::unique/std::erase来获取容器中唯一的元素。

因此，创建一个包含c1内容的容器，附加c2的内容，然后排序，将唯一元素移动到末尾并删除它们。类似这样：

container c(c1.begin(), c1.end());
c.insert(c.end(), c2.begin(), c2.end());
std::sort(c.begin(), c.end());
c.erase(std::unique(c.begin(), c.end()), c.end());

- Chris Morley

3

使用STL中的std::set_union算法。但需要先对输入列表进行排序，或者创建输入列表的副本，将其排序后再使用std::set_union。

- Uhall

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

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

- Josh · Accepted Answer

对于无序列表，你的set技巧可能是最好的之一。每个插入应该是O(log n)，需要N个插入，并且遍历将是O(n)，给你O(N*log n)。另一个选择是在每个列表上分别运行std::sort，然后使用std::set_union并行遍历它们，这将为您删除重复项。这也将是O(n*log n)，因此如果您担心性能，您将不得不进行分析。如果你不担心，请做出更有意义的选择。

编辑：set_union仅在原始列表中没有重复项时才有效，否则您必须选择sort，merge，unique和erase。大O性能仍然相同，并且具有关于分析的相同警告。

template <typename container>
container unique_merge(container c1, container c2)
{
    std::sort(c1.begin(), c1.end());
    std::sort(c2.begin(), c2.end());
    container mergeTarget;
    std::merge(c1.begin(), c1.end(), c2.begin(), c2.end(), 
        std::insert_iterator(mergeTarget, mergeTarget.end())
    );
    std::erase(
        std::unique(mergeTarget.begin(), mergeTarget.end()), 
        mergeTarget.end()
    );

    return mergeTarget;
}