减少泛化
我尝试了一下这个，因为它很有趣，而且我认为我自己也可以使用这样的结构。通常情况下，如果你不能做出比他们更具限制性（可能还更加健壮）的缩小范围的假设，就极难击败专业编写的标准库。
例如，如果你的目标只是编写一个与malloc和free一样通用、全面的内存分配器，那么要超越它们就非常困难。然而，如果你为特定用例做出很多假设，就很容易编写一个在该特定用例中超越它们的分配器。
这就是为什么，如果你对数据结构有这样的问题，我建议尽可能提供关于特定用例的奇特细节的信息（例如你需要从结构中获得什么，如迭代、排序、搜索、从中间删除、在前面插入、键的范围、类型等）。你想要做什么的一些测试代码（即使是伪代码）也会很有帮助。我们希望尽可能多地做出这些缩小范围的假设。
高度动态内容的次优搜索算法
在你的情况下，我们有一个非常动态的大型堆类型结构。我最初来自于老派游戏界，在这种非常动态的情况下，通常一个次优的搜索算法实际上比一个具有更高算法复杂度的算法要好，因为那种搜索优势往往伴随着更昂贵的构建/更新过程（较慢的插入/删除）。
例如，如果你有大量精灵在2D游戏中每帧移动，甚至一个粗略编写、算法较差的固定网格加速器对于最近邻搜索通常在实践中比算法上更优秀的专业编写的四叉树更好，因为不断移动和重新平衡树的成本会增加超过优秀加速和理论对数复杂度的开销。固定网格在所有精灵聚集在一个区域时会出现病态情况，但这种情况很少发生。
所以我采取了这种策略。我做了一些假设，其中最大的一个是您的键在范围内合理分布。另一个假设是您可以粗略地近似容器应处理的最大元素数量（尽管您可以超过或低于此数字，但对于一些粗略的知识和预期效果最好）。我没有麻烦提供迭代器来遍历容器（如果您想要，但与 std::multimap 不同，键不会被完美排序，它们将“有点”排序），但它确实提供了从中间删除元素以及弹出最小键元素。在我的解决方案中存在一种病理情况，在 std::multimap 中不存在，即如果您有大量元素，其中键的值大致相同（例如：0.000001、0.00000012、0.000000011 等）对于所有百万个元素，它会退化为通过所有元素进行线性搜索，并且执行比 multimap 差得多。
但是，如果我的假设符合您的用例，我得到了一个比 std::multmap 快约 8 倍的解决方案。
注意：这是仓促编写的代码，并带有许多快速而肮脏的分析器支持的微优化，甚至提供了一个池分配器，并以位和字节级别操作事物，使用最大对齐性假设“足够可移植”。它还不会为异常安全等提供麻烦。但是，对于 C++ 对象来说，应该是安全的。
作为测试用例，我创建了一百万个随机键，并开始弹出最小键、更改它们并重新插入它们。我对 multimap 和我的结构执行此操作以比较性能。
平衡分布堆/优先队列（有点类似）
#include <iostream>
#include <cassert>
#include <utility>
#include <stdexcept>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <map>
#include <vector>
#include <malloc.h>
#if defined(_MSC_VER)
#define MAX_ALIGN __declspec(align(16))
#else
#define MAX_ALIGN __attribute__((aligned(16)))
#endif
using namespace std;
static void* max_malloc(size_t amount)
{
#ifdef _MSC_VER
return _aligned_malloc(amount, 16);
#else
void* mem = 0;
posix_memalign(&mem, 16, amount);
return mem;
#endif
}
static void max_free(void* mem)
{
#ifdef _MSC_VER
return _aligned_free(mem);
#else
free(mem);
#endif
}
template <class Key, class Value, class KeyToIndex>
class BalancedQueue
{
public:
enum {zone_len = 256};
explicit BalancedQueue(int n):
num_nodes(0), num_buckets(n+1), min_bucket(n+1), buckets(static_cast<Bucket*>(max_malloc((n+1) * sizeof(Bucket)))), free_nodes(0), pools(0)
{
const int num_zones = num_buckets / zone_len + 1;
zone_counts = new int[num_zones];
for (int j=0; j < num_zones; ++j)
zone_counts[j] = 0;
for (int j=0; j < num_buckets; ++j)
{
buckets[j].num = 0;
buckets[j].head = 0;
}
}
~BalancedQueue()
{
clear();
max_free(buckets);
while (pools)
{
Pool* to_free = pools;
pools = pools->next;
max_free(to_free);
}
delete[] zone_counts;
}
void clear()
{
const int num_zones = num_buckets / zone_len + 1;
for (int j=0; j < num_zones; ++j)
zone_counts[j] = 0;
for (int j=0; j < num_buckets; ++j)
{
while (buckets[j].head)
{
Node* to_free = buckets[j].head;
buckets[j].head = buckets[j].head->next;
node_free(to_free);
}
buckets[j].num = 0;
}
num_nodes = 0;
min_bucket = num_buckets+1;
}
void push(const Key& key, const Value& value)
{
const int index = KeyToIndex()(key);
assert(index >= 0 && index < num_buckets && "Key is out of range!");
Node* new_node = node_alloc();
new (&new_node->key) Key(key);
new (&new_node->value) Value(value);
new_node->next = buckets[index].head;
buckets[index].head = new_node;
assert(new_node->key == key && new_node->value == value);
++num_nodes;
++buckets[index].num;
++zone_counts[index/zone_len];
min_bucket = std::min(min_bucket, index);
}
bool empty() const
{
return num_nodes == 0;
}
int size() const
{
return num_nodes;
}
std::pair<Key, Value> pop()
{
assert(!empty() && "Queue is empty!");
for (int j=min_bucket; j < num_buckets; ++j)
{
if (buckets[j].head)
{
Node* node = buckets[j].head;
Node* prev_node = node;
Node* min_node = node;
Node* prev_min_node = 0;
const Key* min_key = &min_node->key;
const Value* min_val = &min_node->value;
for (node = node->next; node; prev_node = node, node = node->next)
{
if (node->key < *min_key)
{
prev_min_node = prev_node;
min_node = node;
min_key = &min_node->key;
min_val = &min_node->value;
}
}
std::pair<Key, Value> kv(*min_key, *min_val);
if (min_node == buckets[j].head)
buckets[j].head = buckets[j].head->next;
else
{
assert(prev_min_node);
prev_min_node->next = min_node->next;
}
removed_node(j);
node_free(min_node);
return kv;
}
}
throw std::runtime_error("Trying to pop from an empty queue.");
}
bool erase(const Key& key, const Value& value)
{
assert(!empty() && "Queue is empty!");
const int index = KeyToIndex()(key);
if (buckets[index].head)
{
Node* node = buckets[index].head;
if (node_key(node) == key && node_val(node) == value)
{
buckets[index].head = buckets[index].head->next;
removed_node(index);
node_free(node);
return true;
}
Node* prev_node = node;
for (node = node->next; node; prev_node = node, node = node->next)
{
if (node_key(node) == key && node_val(node) == value)
{
prev_node->next = node->next;
removed_node(index);
node_free(node);
return true;
}
}
}
return false;
}
private:
BalancedQueue(const BalancedQueue&);
BalancedQueue& operator=(const BalancedQueue&);
struct Node
{
Key key;
Value value;
Node* next;
};
struct Bucket
{
int num;
Node* head;
};
struct Pool
{
Pool* next;
MAX_ALIGN char buf[1];
};
Node* node_alloc()
{
if (free_nodes)
{
Node* node = free_nodes;
free_nodes = free_nodes->next;
return node;
}
const int pool_size = std::max(4096, static_cast<int>(sizeof(Node)));
Pool* new_pool = static_cast<Pool*>(max_malloc(sizeof(Pool) + pool_size - 1));
new_pool->next = pools;
pools = new_pool;
for (int j=0; j < pool_size; j += sizeof(Node))
{
Node* node = reinterpret_cast<Node*>(new_pool->buf + j);
node->next = free_nodes;
free_nodes = node;
}
return node_alloc();
}
void node_free(Node* node)
{
node->key.~Key();
node->value.~Value();
node->next = free_nodes;
free_nodes = node;
}
void removed_node(int bucket_index)
{
--num_nodes;
--zone_counts[bucket_index/zone_len];
if (--buckets[bucket_index].num == 0 && bucket_index == min_bucket)
{
const int num_zones = num_buckets / zone_len + 1;
for (int j=bucket_index/zone_len; j < num_zones; ++j)
{
if (zone_counts[j] > 0)
{
for (min_bucket=j*zone_len; min_bucket < num_buckets && buckets[min_bucket].num == 0; ++min_bucket) {}
assert(min_bucket/zone_len == j);
return;
}
}
min_bucket = num_buckets+1;
assert(empty());
}
}
int* zone_counts;
int num_nodes;
int num_buckets;
int min_bucket;
Bucket* buckets;
Node* free_nodes;
Pool* pools;
};
enum {num_keys = 1000000};
enum {buckets = 100000};
static double sys_time()
{
return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}
struct KeyToIndex
{
int operator()(double val) const
{
return static_cast<int>(val * buckets);
}
};
int main()
{
vector<double> keys(num_keys);
for (int j=0; j < num_keys; ++j)
keys[j] = static_cast<double>(rand()) / RAND_MAX;
for (int k=0; k < 5; ++k)
{
{
const double start_time = sys_time();
multimap<double, int> q;
for (int j=0; j < num_keys; ++j)
q.insert(make_pair(keys[j], j));
for (int j=0; j < num_keys; ++j)
{
pair<double, int> top = *q.begin();
q.erase(q.begin());
top.first = static_cast<double>(rand()) / RAND_MAX;
q.insert(top);
}
cout << (sys_time() - start_time) << " secs for multimap" << endl;
}
{
const double start_time = sys_time();
BalancedQueue<double, int, KeyToIndex> q(buckets);
for (int j=0; j < num_keys; ++j)
q.push(keys[j], j);
for (int j=0; j < num_keys; ++j)
{
pair<double, int> top = q.pop();
top.first = static_cast<double>(rand()) / RAND_MAX;
q.push(top.first, top.second);
}
cout << (sys_time() - start_time) << " secs for BalancedQueue" << endl;
}
cout << endl;
}
}
我的机器上的结果：
3.023 secs for multimap
0.34 secs for BalancedQueue
2.807 secs for multimap
0.351 secs for BalancedQueue
2.771 secs for multimap
0.337 secs for BalancedQueue
2.752 secs for multimap
0.338 secs for BalancedQueue
2.742 secs for multimap
0.334 secs for BalancedQueue
std::priority_queue中的元素的吗？堆没有搜索功能，而且std::priority_queue甚至没有迭代器。 - Brian Bi