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

Question

我有两个要合并的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 trickery:

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

有没有更好的方法或者我错过了明显出血的东西？

Answer 1

对于无序列表,您的设置技巧可能是最好的.每个插入应该是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;
}