Лучший способ объединить несколько контейнеров 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 обман, я думаю:

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), поэтому, если вы беспокоитесь о производительности, вам придется профилировать. Если это не так, делайте, что имеет для вас больше смысла.

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

Answer 2

Вам нужно будет либо отсортировать (либо явно, либо неявно через отсортированный контейнер, например, set).

Существует общая идиома, использующая std :: sort / std :: unique / std :: erase для получения уникальных элементов в контейнере.

Итак, создайте контейнер с содержимым c1, добавьте содержимое c2, затем сортируйте, перемещайте уникальные элементы до конца и стирайте их. Как то так:

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

Answer 3

Используйте алгоритм std :: set_union из STL. Вам сначала нужно будет отсортировать свои входные списки - или создать копии своих входных списков, отсортировать их, а затем использовать std :: set_union.