C++ и наверно STL: Как бы попроще сделать?

0000

Имеется два множества с недублирующимися элементами вида (int, int). Необходимо найти элементы, которые есть в одном множестве и нет в другом.
Предположительно можно воспользоваться stl-set + pair или stl-vector, но как вот тогда разницу в множествах искать?
P.S. Перебором не хочется, ибо код длинный получается.

slonishka

template<class In, class In2, class Out>

    Out set_difference(In first, In last, In2 first2, In2 last2, Out res); // 18.7.5 в Страуструпе.

оператор сравнения можно задать свой, или использовать тот, который определен для pair<int,int>.
вроде так. =)

Missi4ka

Без перебора всех элементов, вообще говоря, никак. Если множества упорядочены, то можно их представить в виде набора интервалов и смотреть только на концы интервалов. Даже если не мудрить с концами, множество стоит держать упорядоченным, чтобы делать сравнение и брать разность за O(n) операций.

0000

Как выяснил, Страуструп третьего издания у меня только на английском

- посмотрел ничего не понял и стал читать Аммераля, чтоб STL понять.

erotic

Создаешь два множества со своими элементами, задаешь критерий сравнения, сортируешь оба множества, вызываешь set_difference для них, получаешь на выходе третье, нужное тебе, множество.
typedef pair<int, int> ElType;
typedef std::set< ElType > SetType;
SetType s1, s2, s3;
s1.insert(bla-bla); // заполняешь первое множество
s2.insert(bla-bla); // заполняешь второе множество
struct Cmp
{
bool operator (const ElType& left, const ElType& right)
{
return // возвращаешь результат сравнения двух элементов;
}
};
sort(s1.begin s1.end Cmp;
sort(s2.begin s2.end Cmp;
set_difference(s1.begin s1.end s2.begin s2.end inserter(s3, s3.end;

0000

Блин, что то sort не хочет компилится - матерится на число передавамеых аргументов

Делаю так



#include <set>

#include <vector>

#include <algorithm>

...

typedef std::set<std::pair<int, int >  > Set;

Set s1, s2, s3;

...

    s1.insert (std::make_pair (1, 2;

    s1.insert (std::make_pair (1, 3;



    s2.insert (std::make_pair (1, 2;

    s2.insert (std::make_pair (2, 3;

..

    sort(s1.begin s1.end;

или

    sort(s1.begin s1.end cmp ;

...

    std::set_symmetric_difference(s1.begin s1.end s2.begin s2.end inserter(s3, s3.end;

smit1

typedef pair<int, int> ElType;
typedef std::set< ElType > SetType;
SetType s1, s2, s3;
s1.insert(bla-bla); // заполняешь первое множество
s2.insert(bla-bla); // заполняешь второе множество
struct Cmp
{
bool operator (const ElType& left, const ElType& right)
{
return // возвращаешь результат сравнения двух элементов;
}
};
sort(s1.begin s1.end Cmp;
sort(s2.begin s2.end Cmp;
set_difference(s1.begin s1.end s2.begin s2.end inserter(s3, s3.end;

Автор жжот. Сортировать set'ы - это сильно.

0000

Так что не надо что ли сортировать?

А то я уже вот такое начал смотреть



typedef std::set<std::pair<int, int >, std::less< std::pair <int, int> >  > Set;

slonishka

контейнеры map и set всегда находятся в отсортированном (с помощью функции cmp — параметра шаблона) состоянии. засчёт этого и получается время доступа по индексу O(log(n. если тебе нужно какое-то необычное сравнение, ты можешь задать его при создании своего множества, как параметр шаблона:
std::set<std::pair<int,int>, cmp> your_set;
cmp — это структура с перегруженным operator которую описал . к ней предъявляется три требования:
1. cmp(x,x) == false
2. если cmp(x,y) и cmp(y,z то cmp(x,z)
3. равенство определяется, как !( cmp(x,y) || cmp(y,x) ). соответственно, равенство транзитивно!
и тогда каждый элемент будет добавляться таким образом, чтобы множество оставалось отсортированным.

slonishka

пример такой структуры есть в страуструпе 17.1.4.1

можно еще почитать 18.4.
если где ошибся — поправьте.

0000

О, пасиб

Буду писать ужасссный код дальше.

erotic

Автор жжот. Сортировать set'ы - это сильно.

О, shit, простите, ошибся, просто в оригинале там не set'ы были

Оставить комментарий