我有以下问题。我的游戏平均每秒运行60帧。我需要在容器中存储值的每个帧，并且必须没有重复。
它可能每帧存储少于100个项目，但插入调用的数量将更多（并且许多被拒绝，因为它必须是唯一的）。只有在框架的末尾，我才需要遍历容器。因此，每帧约60次迭代容器，但插入的次数更多。
请记住，要存储的项目是简单整数。
我可以使用一堆容器，但我无法决定选择什么。性能是这方面的关键问题。
我收集的一些优点/缺点：
向量
- （PRO）：有条件的记忆，一个巨大的因素。
- （PRO）：可以先保留内存，然后再保留很少的分配/解除分配
- （CON）：除了遍历容器（std :: find）每个insert（）以找到唯一键之外别无选择？虽然比较很简单（整数），但整个容器可能适合缓存
组
- （专业）：简单，显然意味着这一点
- （CON）：不是恒定的插入时间
- （CON）：每帧有很多分配/解除分配
- （CON）：没有重点记忆。遍历一组数百个对象意味着在内存中跳转很多。
unordered_set
- （专业）：简单，显然意味着这一点
- （PRO）：平均情况常数时间插入
- （CON）：看作我存储整数，哈希操作可能比其他任何东西都要贵
- （CON）：每帧有很多分配/解除分配
- （CON）：没有重点记忆。遍历一组数百个对象意味着在内存中跳转很多。
由于内存访问模式，我倾向于使用向量路由，即使set明显是针对此问题的。我不清楚的一个大问题是，遍历每个插入的向量是否比分配/解除分配（特别是考虑必须这样做的频率）和set的内存查找更昂贵。
我知道最终这一切都归结为每个案例的分析，但如果不是作为一个开头或理论上，在这种情况下可能最好的是什么？我可能会错过任何优点/缺点吗？
编辑：正如我没有提到的，容器在每帧结束时被清除（）
我将把我的脖子放在这里的块上，并建议当大小为100并且存储的对象是整数值时，向量路径可能是最有效的。原因很简单，set和unordered_set为每个插入分配内存，而向量不需要多于一次。
您可以通过保持向量排序来显着提高搜索性能，因为所有搜索都可以是二进制搜索，因此在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;
}