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

Невозможно ли использовать контейнер, который обеспечивает такую "гарантию" с самого начала? Будет ли полезно отмечать дубликаты в момент вставки, а не в какой-то момент в будущем? Когда я хотел сделать что-то подобное, я пошел именно в этом направлении; просто используя набор в качестве "основного" контейнера, и, возможно, создавая параллельный вектор, если мне нужно сохранить первоначальный порядок, но, конечно, это делает некоторые предположения о доступности памяти и процессора...

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

template <typename T>
bool is_unique(std::vector<T> vec)
{
    std::sort(vec.begin(), vec.end());
    return std::unique(vec.begin(), vec.end()) == vec.end();
}

Будет ли это быстрее, чем использование std :: set , как вы знаете, зависит :-).

Вы можете использовать std :: unique , но для этого сначала нужно отсортировать диапазон:

template <class T>
bool is_unique(vector<T> X) {
  std::sort(X.begin(), X.end());
  return std::unique(X.begin(), X.end()) == X.end();
}

std :: unique изменяет последовательность и возвращает итератор в конец уникального установлен, поэтому, если это все еще конец вектора, он должен быть уникальным.

Это выполняется в nlog (n); так же, как ваш пример. Я не думаю, что вы теоретически можете гарантировать, что это будет быстрее, хотя использование C ++ 0x std :: unordered_set вместо std :: set сделает это за ожидаемое линейное время. - но для этого требуется, чтобы ваши элементы были хешируемыми, а также были определены operator == , что может быть не так просто.

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

Ну, ваш первый должен принимать только N log ( N) , так что это явно лучший и худший сценарий для этого приложения.

Тем не менее, вы сможете получить лучший случай, если будете проверять, добавляя элементы в набор:

template <class T>
bool is_unique3(vector<T> X) {
  set<T> Y;
  typename vector<T>::const_iterator i;
  for(i=X.begin(); i!=X.end(); ++i) {
    if (Y.find(*i) != Y.end()) {
      return false;
    }
    Y.insert(*i);
  }
  return true;
}

Это должно иметь O (1) в лучшем случае, O ( N log (N)) наихудший случай, а средний случай зависит от распределения входных данных.

Если тип T, который вы храните в вашем векторе, велик и его копирование требует больших затрат, подумайте о создании вектора указателей или итераторов на элементы вашего вектора. Отсортируйте его на основе элемента, на который указывают, а затем проверьте на уникальность.

Вы также можете использовать для этого std::set. Шаблон выглядит так

template <class Key,class Traits=less<Key>,class Allocator=allocator<Key> > class set

Я думаю, вы можете предоставить соответствующий параметр Traits и вставить необработанные указатели для скорости или реализовать простой класс-обертку для указателей с оператором <.

Не используйте конструктор для вставки в набор. Используйте метод insert. Метод (одна из перегрузок) имеет сигнатуру

pair <iterator, bool> insert(const value_type& _Val);

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

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

bool is_unique(const vector<int>& X, int N)
{
  vector<int> buckets(N,0);
  typename vector<int>::const_iterator i;
  for(i = X.begin(); i != X.end(); ++i)
    if(++buckets[*i] > 1)
      return false;
  return true;
}

Сложность этого будет O (n).

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

Могу я добавить свои 2 цента.

Прежде всего, как заметил @Potatoswatter , если ваши элементы не дешевы для копирования (встроенные / небольшие POD), вы захотите использовать указатели на исходные элементы, а не копировать их.

Во-вторых, доступны 2 стратегии.

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

Должен признать, я склоняюсь к первому. Инкапсуляция, четкое разделение ответственности и все такое.

В любом случае, есть несколько способов, в зависимости от требований. Первый вопрос:

• должны ли мы размещать элементы в векторе в определенном порядке или мы можем «возиться» с ними?

Если мы можем возиться с ними, я бы посоветовал сохранение сортировки вектора : Loki :: AssocVector должно помочь вам начать работу. Если нет, то нам нужно сохранить индекс в структуре, чтобы гарантировать это свойство .. Подождите минутку: Boost.MultiIndex на помощь?

В-третьих: как вы сами заметили, простой линейный поиск, удвоенный, дает в среднем сложность O (N ² ), что составляет не хорошо.

Если < уже определено, то сортировка очевидна с ее сложностью O (N log N). Возможно, стоит сделать T Hashable, потому что std :: tr1 :: hash_set может дать лучшее время (я знаю, вам нужен RandomAccessIterator , но если T Hashable, то легко получить T * Hashable to;))

Но, в конце концов, настоящая проблема здесь в том, что наши советы необходимы общие, потому что мы не хватает данных.

• Что такое T , вы хотите, чтобы алгоритм был универсальным?
• Какое количество элементов? 10, 100, 10.000, 1.000.000? Поскольку асимптотическая сложность является спорным вопросом при работе с несколькими сотнями ....
• И, конечно же: можете ли вы обеспечить единство во время вставки? Можете ли вы изменить сам вектор?

Для начала вы могли бы объединить преимущества обоих: прекратить строить множество, если вы уже обнаружили дубликат:

template <class T>
bool is_unique(const std::vector<T>& vec)
{
    std::set<T> test;
    for (typename std::vector<T>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
        if (!test.insert(*it).second) {
            return false;
        }
    }
    return true;
}

BTW, Potatoswatter делает хорошее замечание, что в общем случае вы можете захотеть избежать копирования T, в этом случае вы можете использовать std::set вместо этого.

Конечно, потенциально вы могли бы сделать гораздо лучше, если бы это не было общим. Например, если у вас есть вектор целых чисел известного диапазона, вы можете просто пометить в массиве (или даже наборе битов), если элемент существует.

Необходимо отсортировать вектор, если необходимо быстро определить, есть ли в нем только уникальные элементы. В противном случае лучшее, что вы можете сделать, это O(n^2) среда выполнения или O(n log n) с пространством O(n). Я думаю, что лучше всего написать функцию, которая предполагает, что входные данные отсортированы.

template<class Fwd>
bool is_unique(In first, In last)
{
    return adjacent_find(first, last) == last;
}

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