c++ - 少量项目的最快插入且不重复
问题描述
我将整数插入容器中。许多整数是重复的，在这种情况下，我只想插入一个。我预计最后容器中的物品不会超过 100 个（通常只有 <10 个）。
自然的解决方案是使用std::unordered_set或std::set。但我仍然有一些问题：
- unordered_set 是 O(1) 而 set 是 O(log n)，但是对于少量元素可能设置得更快？
- 我的元素数量非常少，所以我并不真正关心内存复杂性。有没有比 unordered_set（即 hashmap）更快的更专业的算法？
详细信息和背景：我使用常规 3D 网格将对象存储在 3D 引擎中。一些对象与更多单元格重叠。当我检查哪些对象与对象 A 重叠时，我会遍历与 A 重叠的所有单元格并在每个单元格中插入所有对象
int findInCells( int n, int* cells, int* objects ){
std::unordered_set<int> found;
for(int i=0; i<n; i++){ // go over cells
auto range = map.equal_range( cells[i] ); // list all objects in std::unordered_multimap<int,int> map;
for(auto it = range.first; it != range.second; it++){ //
found.insert(it->second);
}
}
int io=0;
for(int o : found){ objects[io]=o; }
return io;
}
我试图让它比不关心重复的简单版本慢很多。
int findInCellsNaive( int n, int* cells, int* objects ){
// problem - what if we have same object in two different cells? we will insert it multiple times
int io=0;
for(int i=0; i<n; i++){ // go over cells
auto range = map.equal_range( cells[i] ); // list all objects in std::unordered_multimap<int,int> map;
for(auto it = range.first; it != range.second; it++){ //
outInds[io]=it->second;
io++;
}
}
return io;
}
我正在尝试的另一个解决方案是使用具有所有对象数量大小的附加布尔数组来“绘制”已经插入的对象。
bool* painted = new bool[NOBJECTS];
for(int i=0; i<NOBJECTS; i++){ painted[o]=true; };
inline int findInCellsPaint( int n, int* cells, int* objects ){
int io=0;
for(int i=0; i<n; i++){ // go over cells
auto range = map.equal_range( cells[i] ); // list all objects in std::unordered_multimap<int,int> map;
for(auto it = range.first; it != range.second; it++){ //
int o = it->second;
if( painted[o] ){
objects[io]=o;
painted[o]=false;
io++;
}
}
}
for(int i=0; i<io; i++){ painted[objects[o]]=true; };
return io;
}