我目前正在寻找满足我要求的 C++ 中最快的数据结构:

最佳答案

减少一般性

我尝试了这个，因为它很有趣，我想我自己可以使用这样的结构。击败专业编写的标准库通常非常困难，除非您可以做出缩小的假设，从而比他们的解决方案的普遍性(以及可能的稳健性)限制更多。

例如，很难击败malloc和 free如果您的目标只是编写一个通用且全面的内存分配器，如 malloc .但是，如果您对特定用例做出很多假设，则很容易编写一个分配器，仅针对特定用例就可以胜过这些假设。

这就是为什么，如果您对数据结构有这样的问题，我建议尽可能多地提供有关您的特定用例的特殊细节的信息(您需要从结构中获取的信息，例如迭代、排序、搜索、从中间删除，插入到前面，键的范围，类型等)。您想要做的一些测试代码(甚至伪代码)是有帮助的。我们想要尽可能多的缩小假设。

高动态内容的低于标准搜索算法

在您的情况下，我们对如此大的堆类型结构进行了特殊的动态使用。我最初来自老派游戏背景，在那些非常动态的情况下，通常低于标准的搜索算法实际上比具有卓越算法复杂性的搜索算法更有效，因为搜索优势通常伴随着更昂贵的价格标签构建/更新过程(较慢的插入/删除)。

例如，如果您有大量 Sprite 在 2D 游戏中的每一帧周围移动，那么平均而言，用于最近邻搜索的粗略编写的、算法上较差的固定网格 boost 器在实践中通常比算法上高级的、专业的——书面四叉树，因为不断移动事物和重新平衡树的成本可能会增加开销，超过一切的优越 boost 和理论对数复杂性。当所有 Sprite 聚集在一个区域时，固定网格会出现病态情况，但这种情况很少发生。

所以我采取了这种策略。我在做一些假设，其中最大的假设是您的 key 在一个范围内合理分布。另一个是你可以粗略地估计容器应该处理的最大元素数(虽然你可以超过或低于这个数字，但最好有一些粗略的知识和预期)。而且我没有费心提供迭代器来遍历容器(如果您愿意，可以这样做，但是键不会像 std::multimap 那样完美排序，它们会被“有点”排序)，但它确实提供除了使用最小键弹出元素之外，还从中间移除。我的解决方案中存在一个病理案例，例如 std::multimap 中不存在的案例，如果您有大量元素的键值大致相同(例如:0.000001、0.00000012、0.000000011 等)对于所有百万个元素，它会降级为对所有元素的线性搜索，并且性能比 multimap 差得多。 .

但我得到了一个比 std::multmap 快约 8 倍的解决方案如果我的假设适合您的用例。

注意:它是草率的代码，并且使用了许多快速而肮脏的分析器辅助的微优化编写，甚至提供了一个池分配器并在位和字节级别使用对齐假设来操纵事物(使用最大对齐假设“足够便携”) .它也不关心异常安全之类的事情。但是，用于 C++ 对象应该是安全的。

作为测试用例，我创建了一百万个随 secret 钥并开始弹出最小 key 、更改它们并重新插入它们。我对多重映射和我的结构都这样做了，以比较性能。

平衡分布堆/优先队列(有点)

#include <iostream>
#include <cassert>
#include <utility>
#include <stdexcept>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <map>
#include <vector>
#include <malloc.h>

// Max Alignment
#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
}

// Balanced priority queue for very quick insertions and 
// removals when the keys are balanced across a distributed range.
template <class Key, class Value, class KeyToIndex>
class BalancedQueue
{
public:
    enum {zone_len = 256};

    /// Creates a queue with 'n' buckets.
    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;
        }
    }

    /// Destroys the queue.
    ~BalancedQueue()
    {
        clear();
        max_free(buckets);
        while (pools)
        {
            Pool* to_free = pools;
            pools = pools->next;
            max_free(to_free);
        }
        delete[] zone_counts;
    }

    /// Makes the queue empty.
    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;
    }

    /// Pushes an element to the queue.
    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);
    }

    /// @return size() == 0.
    bool empty() const
    {
        return num_nodes == 0;
    }

    /// @return The number of elements in the queue.
    int size() const
    {
        return num_nodes;
    }

    /// Pops the element with the minimum key from the queue.
    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.");
    }

    /// Erases an element from the middle of the queue.
    /// @return True if the element was found and removed.
    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:
    // Didn't bother to make it copyable -- left as an exercise.
    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;

        // Push the new pool's nodes to the free stack.
        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)
    {
        // Destroy the key and value and push the node back to the free stack.
        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)
        {
            // If the bucket became empty, search for next occupied minimum zone.
            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;
};

/// Test Parameters
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)
    {
        // Multimap
        {
            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));

            // Pop each key, modify it, and reinsert.
            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;
        }

        // Balanced Queue
        {
            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);

            // Pop each key, modify it, and reinsert.
            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

关于c++ - C++ 中的 Fast(est) 可变堆实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29931592/