c++ - 类似双端队列的数据结构，可在任意位置快速查找和删除

Question

我正在寻找一种可以解决以下用例的数据结构:

• 值从后面插入
• 各个值的大小为几十个字节。
• 值自然按其字段之一升序排列，该字段作为唯一标识符。
• 值通常从前面删除，但也可以从键指定的任意位置删除，因此查找和删除应该很快。
• 将值的连续子集复制到这种类型的新数据结构应该很便宜。
• 清算应该很便宜。
• 通常包含数十或数百个值，但也有可能包含数千个。
• 性能应该一致，因为我将其用于软实时系统。

我一直在思考双端队列+辅助双端队列持有一个位图，可以用来指示值的删除，但在我坐下来编写代码之前，我会感谢你的建议。谢谢!

Answer 1

您可以尝试链接unordered_map其模板参数为 key_type和node<value_type> ，并且该节点将具有前一个\下一个值的键。

该类将与此有些类似:(含义不完整)

#include <unordered_map>

template<typename key, typename value>
struct linked_map {

    void push_back(key key_, value value_) {
        if (!is_first_last_set)
            first_last.first = key_;
        assert(base.find(key_) == base.end());
        base[key_] = value_;
        // TODO: set prev/next_node_key
        first_last.second = key_;
        is_first_last_set = true;
    }
    void erase(key key_) {
        // TODO: update previous and next node's previous and next keys
        base.erase(base.find(key_));
    }
    value &front() {
        return base[first_last.first].data;
    }
    void pop_front() {
        erase(first_last.first);
    }
    ...

    bool is_first_last_set = false;
    std::pair<key,key> first_last;
    struct node {
        value data;
        key prev_node_key,next_node_key;
    };
    std::unordered_map<key,std::pair<key,value>> base;
};

unordered_map就是让O(1)随机访问删除。 node值中的内容是保存unordered_map中的顺序.

我选择使用unordered_map ，因为它比 map 具有更一致的性能因为它不必为每次插入进行分配(当内存碎片或出于任何原因时，分配可能需要更长的时间)，并且处理器在插入\删除\前端时必须执行的最大操作是一些缓存未命中。