我有以下问题。我的游戏平均每秒运行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;
}
我用一些我认为可能候选的不同方法做了计时。运用 std::unordered_set 是赢家。
这是我的结果：
使用UnorderedSet：0.078s
使用UnsortedVector：0.193s
使用OrderedSet：0.278s
使用SortedVector：0.282s
时间基于每种情况的五次运行的中位数。
编译器：gcc版本4.9.1
flags：-std = c ++ 11 -O2
操作系统：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";
}
正如你所说，你有很多插入和只有一次遍历，我建议使用一个向量并推送元素，无论它们是否在向量中是唯一的。这是完成的 O(1)。
就在您需要浏览向量时，然后对其进行排序并删除重复的元素。我相信这可以做到 O(n) 因为它们是有界的整数。
编辑：通过线性时间排序 数排序 介绍 这个视频。如果不可行，那么你又回来了 O(n lg(n))。
由于内存中向量的连续性，以及很少的分配（特别是如果在向量中保留足够的内存），您将只有非常少的高速缓存未命中。