什么容器来存储唯一值？

Question

我遇到了以下问题。我有一款平均每秒运行 60 帧的游戏。每一帧我都需要将值存储在一个容器中，并且不能有重复项。

它可能必须每帧存储少于 100 个项目，但插入调用的数量会更多（并且由于它必须是唯一的而被拒绝的很多）。只有在框架的末尾，我才需要遍历容器。所以每帧大约 60 次容器迭代，但插入次数更多。

请记住要存储的项目是简单的整数。

有很多容器可供我使用，但我无法决定选择什么。性能是关键问题。

我收集了一些 pros/cons：

向量

(PRO)：连续内存，一个重要因素。
(PRO): 可以先预留内存，很少allocations/deallocations之后
(CON)：除了遍历容器 (std::find) 每个 insert() 来查找唯一键之外，别无选择？比较很简单（整数），整个容器可能适合缓存

设置

(PRO)：简单，显然是为了这个
(CON)：插入时间不恒定
(CON)：很多 allocations/deallocations 每帧
(CON)：内存不连续。遍历一组数百个对象意味着在内存中跳来跳去。

unordered_set

(PRO)：简单，显然是为了这个
(PRO): 平均情况常数时间插入
(CON): 鉴于我存储整数，散列运算可能比其他任何运算都昂贵得多
(CON)：很多 allocations/deallocations 每帧
(CON)：内存不连续。遍历一组数百个对象意味着在内存中跳来跳去。

由于内存访问模式，我倾向于使用矢量路由，尽管 set 显然是针对此问题的。我不清楚的一个大问题是遍历每个插入的向量是否比 allocations/deallocations （特别是考虑到必须多久完成一次）和 set.

的内存查找成本更高

我知道最终这一切都归结为分析每个案例，但如果只是作为一个开端或只是理论上的，那么在这种情况下什么可能是最好的？有没有 pros/cons 我可能也错过了？

编辑：正如我没有提到的，容器在每帧结束时被清除（）

Answer 1

我要在这里把我的脖子放在块上并建议当大小为 100 并且存储的对象是整数值时矢量路径可能是最有效的。这样做的简单原因是 set 和 unordered_set 为每个插入分配内存，而 vector 不需要超过一次。

您可以通过保持向量有序来显着提高搜索性能，从那时起所有搜索都可以是二进制搜索，因此可以在 log2N 时间内完成。

缺点是由于内存移动，插入将花费一小部分时间，但听起来搜索次数似乎比插入次数多得多，并且移动（平均）50 个连续的内存字几乎是瞬时的操作。

最后一句话：现在写出正确的逻辑。在用户抱怨时担心性能。

编辑：因为我忍不住，这里有一个相当完整的实现：

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;
}

Answer 2

正如你所说的，你有很多插入而只有一次遍历，我建议使用向量并将元素压入，而不管它们在向量中是否唯一。这是在 O(1).

中完成的

就在你需要遍历vector的时候，对它进行排序，去掉重复的元素。我相信这可以在 O(n) 中完成，因为它们是有界整数。

编辑：通过计数排序在线性时间内排序this video。如果不可行，则返回 O(n lg(n))。

由于向量在内存中的连续性以及很少的分配（特别是如果您在向量中预留足够的内存），您将很少有缓存未命中。

Answer 3

我用我认为可能的几种不同方法进行了计时。使用 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";
}

什么容器来存储唯一值？

What container to store unique values?

c++

containers

memory-management