Как получить уникальные пары значений из набора stl

Question

У меня есть набор целых чисел stl, и я хотел бы перебрать все уникальные пары целочисленных значений, где по уникальности я считаю val1, val2 и val2, val1 одинаковыми и я должен видеть только эту комбинацию однажды .

Я написал это на python, где я использую индекс списка (кластеров):

for i in range(len(clusters) - 1):
    for j in range(i+1,len(clusters)):
       #Do something with clusters[i],clusters[j])

, но без индекса я не уверен, как мне достичьто же самое с набором stl и итераторами.Я попытался:

for (set<int>::iterator itr = myset.begin(); itr != myset.end()-1; ++itr) {
    cout << *itr;
}

, но это не удалось, поскольку у итератора нет оператора -.

Как мне этого добиться или я должен использовать другой контейнер?

Answer 1

Как насчет чего-то следующего:

for(set<int>::const_iterator iter1 = myset.begin(); iter1 != myset.end(); ++iter1) {
    for(set<int>::const_iterator iter2 = iter1; ++iter2 != myset.end();) {
    {
        std::cout << *iter1 << " " << *iter2 << "\n"; 
    }
}

Это дает все N*(N-1)/2 уникальных пар, где N - количество целых чисел в вашем наборе.

Как отступление: используйте const_iterator всякий раз, когда вы перебираете контейнер, ничего не изменяя, это хороший стиль и может иметь лучшую производительность.

РЕДАКТИРОВАТЬ: изменил код, чтобы отразить предложение, сделанное Стивом Джессопом.

Answer 2

Вам не нужно делать end() - 1, поскольку end() является итератором, который указывает после последнего элемента в контейнере.

Исправленный код:

for (set<int>::iterator itr = myset.begin(); itr != myset.end(); ++itr) {
    for (set<int>::iterator itr2 = itr + 1; itr2 != myset.end(); ++itr2) {
        // Do whatever you want with itr and itr2
    }
}

Answer 3

Поместите ваши данные в boost :: bimap, затем выполните итерации в обоих направлениях, скопировав результаты в стандартную карту STL, которая обеспечит уникальность.