Как добавить разные пары в набор? - PullRequest
Новая
       33

Как добавить разные пары в набор?

0 голосов
/ 24 июня 2018

Я пытаюсь вставить несколько пар int в набор , эти пары не имеют никакого порядка;то есть (1,2) = (2,1).Просто я делаю следующее: 

typedef pair<int, int> pairs; 

set<pairs> Set;
pair <int,int> myPair;

// adding pairs:
myPair=pair<int,int>(0,1);
pathSet.insert(myPair);
myPair=pair<int,int>(0,2);
pathSet.insert(myPair);
myPair=pair<int,int>(1,0);
pathSet.insert(myPair);

Итак, я получаю набор, как 

(0,1), (0,2) , (1,0)

Я хочу получить 

(0,1), (0,2)

Как мне избежать дублирования?Там в любом случае?Есть ли лучший ADT, такой как std::unordered_set, с точки зрения эффективности по сравнению с 'set'?

Ответы [ 2 ]

0 голосов
/ 24 июня 2018

Вам нужна пользовательская функция сравнения для std::set, так как вы используете std::pair в качестве типа шаблона.В C ++ 11 вы также можете сделать это как лямбду.

Идея функции compare заключается в том, чтобы сначала проверить, является ли Pair значение Pair.first < Pair.second, если нет, поменять их местами, чтобы сделать ихв порядке внутри compare функции.Это не изменит порядок оригинальных вставленных парных элементов, но удалит дубликаты, как вы упомянули.

auto compare = [](pairs lhs, pairs rhs) 
   {
      if(lhs.first > lhs.second ) lhs = pairs{lhs.second, lhs.first };
      if(rhs.first > rhs.second ) rhs = pairs{rhs.second, rhs.first };
      return lhs< rhs;
   };

Примерно так: Смотрите в прямом эфире здесь 

#include <iostream>
#include <set>

typedef std::pair<int, int> pairs;

int main()
{
   auto compare = [](pairs lhs, pairs rhs) //custom compare lambda function
   {
      if(lhs.first > lhs.second ) lhs = pairs{lhs.second, lhs.first };
      if(rhs.first > rhs.second ) rhs = pairs{rhs.second, rhs.first };
      return lhs< rhs;
   };

   std::set<pairs, decltype(compare)> Set(compare);

   Set.emplace(std::make_pair(0,1)); // use can also emplace to the Set
   Set.emplace(pairs{0,2});
   Set.emplace(pairs{1,0});

   for(const auto& it: Set)
      std::cout << it.first << " " << it.second << std::endl;
}

Вывод: 

0 1
0 2
0 голосов
/ 24 июня 2018

Вам понадобится пользовательская функция сравнения.Там убедитесь, что порядок элементов в паре не имеет значения при сравнении.Простым способом было бы позволить первому элементу в паре всегда быть меньшим (и заменять первый и второй в противном случае).

Код может выглядеть следующим образом: 

int main() {

    typedef pair<int, int> pairs;

    auto cmp = [](pairs a, pairs b) {
        if (a.first > a.second) {
            swap(a.first, a.second);
        }
        if (b.first > b.second) {
            swap(b.first, b.second);
        }
        return a < b;
    };
    set<pairs, decltype(cmp)> pathSet(cmp);

    pairs myPair=pair<int,int>(0,1);
    pathSet.insert(myPair);
    myPair=pair<int,int>(0,2);
    pathSet.insert(myPair);
    myPair=pair<int,int>(1,0);
    pathSet.insert(myPair);

    cout << pathSet.size();
}

Выход: 

2
...