В каком контейнере хранятся уникальные значения?

Ответ 1

Я собираюсь поместить свою шею в блок здесь и предположить, что векторный маршрут, вероятно, наиболее эффективен, когда размер 100 и хранящиеся объекты являются целыми значениями. Простой причиной этого является то, что set и unordered_set выделяют память для каждой вставки, тогда как вектор нужен не более одного раза.

Вы можете значительно увеличить эффективность поиска, сохранив векторное упорядочение, так как тогда все поиски могут быть бинарными поисками и поэтому завершены в log2N время.

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

Заключительное слово: Напишите правильную логику. Беспокойство о производительности, когда пользователи жалуются.

EDIT: Поскольку я не мог помочь себе, здесь достаточно полная реализация:

template<typename T>
struct vector_set
{
    using vec_type = std::vector<T>;
    using const_iterator = typename vec_type::const_iterator;
    using iterator = typename vec_type::iterator;

    vector_set(size_t max_size)
    : _max_size { max_size }
    {
        _v.reserve(_max_size);
    }

    /// @returns: pair of iterator, bool
    /// If the value has been inserted, the bool will be true
    /// the iterator will point to the value, or end if it wasn't
    /// inserted due to space exhaustion
    auto insert(const T& elem)
    -> std::pair<iterator, bool>
    {
        if (_v.size() < _max_size) {
            auto it = std::lower_bound(_v.begin(), _v.end(), elem);
            if (_v.end() == it || *it != elem) {
                return make_pair(_v.insert(it, elem), true);
            }
            return make_pair(it, false);
        }
        else {
            return make_pair(_v.end(), false);
        }
    }

    auto find(const T& elem) const
    -> const_iterator
    {
        auto vend = _v.end();
        auto it = std::lower_bound(_v.begin(), vend, elem);
        if (it != vend && *it != elem)
            it = vend;
        return it;
    }

    bool contains(const T& elem) const {
        return find(elem) != _v.end();
    }

    const_iterator begin() const {
        return _v.begin();
    }

    const_iterator end() const {
        return _v.end();
    }


private:
    vec_type _v;
    size_t _max_size;
};

using namespace std;


BOOST_AUTO_TEST_CASE(play_unique_vector)
{
    vector_set<int> v(100);

    for (size_t i = 0 ; i < 1000000 ; ++i) {
        v.insert(int(random() % 200));
    }

    cout << "unique integers:" << endl;
    copy(begin(v), end(v), ostream_iterator<int>(cout, ","));
    cout << endl;

    cout << "contains 100: " << v.contains(100) << endl;
    cout << "contains 101: " << v.contains(101) << endl;
    cout << "contains 102: " << v.contains(102) << endl;
    cout << "contains 103: " << v.contains(103) << endl;
}

Ответ 2

Я сделал выбор времени с помощью нескольких разных методов, которые, как я думал, были вероятными кандидатами. Использование std::unordered_set было победителем.

Вот мои результаты:

Using UnorderedSet:    0.078s
Using UnsortedVector:  0.193s
Using OrderedSet:      0.278s
Using SortedVector:    0.282s

Сроки основаны на медиане пяти прогонов для каждого случая.

compiler: gcc version 4.9.1
flags:    -std=c++11 -O2
OS:       ubuntu 4.9.1
CPU:      Intel(R) Core(TM) i5-4690K CPU @ 3.50GHz

код:

#include <algorithm>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <random>
#include <set>
#include <unordered_set>
#include <vector>

using std::cerr;
static const size_t n_distinct = 100;

template <typename Engine>
static std::vector<int> randomInts(Engine &engine,size_t n)
{
  auto distribution = std::uniform_int_distribution<int>(0,n_distinct);
  auto generator = [&]{return distribution(engine);};
  auto vec = std::vector<int>();
  std::generate_n(std::back_inserter(vec),n,generator);
  return vec;
}


struct UnsortedVectorSmallSet {
  std::vector<int> values;
  static const char *name() { return "UnsortedVector"; }
  UnsortedVectorSmallSet() { values.reserve(n_distinct); }

  void insert(int new_value)
  {
    auto iter = std::find(values.begin(),values.end(),new_value);
    if (iter!=values.end()) return;
    values.push_back(new_value);
  }
};


struct SortedVectorSmallSet {
  std::vector<int> values;
  static const char *name() { return "SortedVector"; }
  SortedVectorSmallSet() { values.reserve(n_distinct); }

  void insert(int new_value)
  {
    auto iter = std::lower_bound(values.begin(),values.end(),new_value);
    if (iter==values.end()) {
      values.push_back(new_value);
      return;
    }
    if (*iter==new_value) return;
    values.insert(iter,new_value);
  }
};

struct OrderedSetSmallSet {
  std::set<int> values;
  static const char *name() { return "OrderedSet"; }
  void insert(int new_value) { values.insert(new_value); }
};

struct UnorderedSetSmallSet {
  std::unordered_set<int> values;
  static const char *name() { return "UnorderedSet"; }
  void insert(int new_value) { values.insert(new_value); }
};



int main()
{
  //using SmallSet = UnsortedVectorSmallSet;
  //using SmallSet = SortedVectorSmallSet;
  //using SmallSet = OrderedSetSmallSet;
  using SmallSet = UnorderedSetSmallSet;

  auto engine = std::default_random_engine();

  std::vector<int> values_to_insert = randomInts(engine,10000000);
  SmallSet small_set;
  namespace chrono = std::chrono;
  using chrono::system_clock;
  auto start_time = system_clock::now();
  for (auto value : values_to_insert) {
    small_set.insert(value);
  }
  auto end_time = system_clock::now();
  auto& result = small_set.values;

  auto sum = std::accumulate(result.begin(),result.end(),0u);
  auto elapsed_seconds = chrono::duration<float>(end_time-start_time).count();

  cerr << "Using " << SmallSet::name() << ":\n";
  cerr << "  sum=" << sum << "\n";
  cerr << "  elapsed: " << elapsed_seconds << "s\n";
}

Ответ 3

Как вы сказали, у вас много вставок и только один обход, Id предлагает использовать вектор и нажимать элементы независимо от того, являются ли они уникальными в векторе. Это делается в O(1).

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

EDIT. Сортировка по линейному времени с помощью подсчета сортировки представлена ​​в этом видео. Если это невозможно, вернитесь к O(n lg(n)).

У вас будет очень мало пропусков кеша из-за смежности вектора в памяти и очень мало распределений (особенно если вы зарезервируете достаточное количество памяти в векторе).