Определение, имеет ли неупорядоченный вектор <T>все уникальные элементы - PullRequest
Новая
       47

Определение, имеет ли неупорядоченный вектор <T>все уникальные элементы

36 голосов
/ 05 мая 2010

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

Первое использование набора: 

template <class T>
bool is_unique(vector<T> X) {
  set<T> Y(X.begin(), X.end());
  return X.size() == Y.size();
}

Второй цикл по элементам: 

template <class T>
bool is_unique2(vector<T> X) {
  typename vector<T>::iterator i,j;
  for(i=X.begin();i!=X.end();++i) {
    for(j=i+1;j!=X.end();++j) {
      if(*i == *j) return 0;
    }
  }
  return 1;
}

Я протестировал их как можно лучше, и из того, что я могу почерпнуть из прочтения документации по STL, ответ (как обычно) зависит. Я думаю, что в первом случае, если все элементы уникальны, это очень быстро, но при большом вырождении операция, похоже, займет O (N ^ 2) времени. Для подхода с вложенными итераторами, похоже, верно обратное: он светится быстро, если X[0]==X[1], но занимает (понятно) O (N ^ 2) время, если все элементы уникальны.

Есть ли лучший способ сделать это, возможно, алгоритм STL, созданный для этой цели? Если нет, то есть ли какие-нибудь предложения по повышению эффективности?

Ответы [ 11 ]

0 голосов
/ 05 мая 2010

Используя текущие стандартные контейнеры C ++, у вас есть хорошее решение в первом примере. Но если вы можете использовать хеш-контейнер, вы можете добиться большего успеха, поскольку хеш-набор будет n O (1) вместо n O (log n) для стандартного набора. Конечно, все будет зависеть от размера n и вашей конкретной реализации библиотеки.

Страница:
...