c++ - 哪个容器存储唯一值？

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

它每帧可能必须存储少于100个项目，但是插入调用的数量会更多(由于唯一性，许多拒绝操作)。仅在框架的末端，我需要遍历容器。因此，每帧容器约有60次迭代，但插入次数更多。

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

我可以用一堆容器来做这件事，但是我不能下定决心要拿什么。性能是关键。

我收集的一些优点/缺点:

vector

(PRO):连续内存，一个很大的因素。

(PRO):可以先保留内存，然后再保留很少的分配/取消分配

(CON):除了遍历容器(std::find)每个insert()以查找唯一键之外，别无选择吗？尽管比较很简单(整数)，并且整个容器可能适合缓存

设置

(PRO):简单，显然是针对此

的意思

(CON):插入时间不恒定

(CON):每帧很多分配/取消分配

(CON):不连续的内存。遍历一组数百个对象意味着在内存中大量跳转。

无序设置

(PRO):简单，显然是针对此

的意思

(PRO):平均情况下恒定时间插入

(CON):看到我存储整数时，哈希运算可能比其他任何东西都昂贵

(CON):每帧很多分配/取消分配

(CON):不连续的内存。遍历一组数百个对象意味着在内存中大量跳转。

由于内存访问模式，我倾向于采用 vector 路由，即使set显然是针对此问题的。对我而言，一个尚不清楚的大问题是，遍历每个插入的 vector 是否比分配/取消分配(尤其是考虑必须多久执行一次)和集合的内存查找的开销更大。

我知道最终归结为对每种情况进行概要分析，但是如果只是作为先例或从理论上讲，在这种情况下，哪种方法最好？我还有可能错过的优点/缺点吗？

编辑:正如我没有提到的，容器在每一帧的末尾处都被clear()

最佳答案

我将在这里说一下，建议 vector 路径在大小为100且存储的对象是整数值时可能是最有效的。这样做的简单原因是set和unordered_set为每个插入分配内存，而 vector 不必超过一次。

通过保持 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;
}