1

我正在寻找具有以下特性的数据结构： - 具有键和值 - 可以在 O(n) > t > O(logn ) 或 O(1) 中找到值 - 可以提取第一个元素和最后一个元素我插入。

TreeMep 不好，因为如果我插入键（作为字符串）“b”然后键“a”如果我要拉第一个我会得到“a”而不是“b”

ConcurrentSkipListMap 不好，因为我不能依赖 size func'

将不胜感激任何帮助

谢谢

4

1 回答 1

0

您可以使用（通常是二叉搜索树）deque交叉引用的（双端队列） ，它允许重复键。multimap

队列的每个元素都会有一个对映射对应元素的引用（一个迭代器），反之亦然。

这样，您可以在 O(log N) 中的地图中进行搜索，并且可以在 O(log N) 中的序列的任一端进行推/拉。

您可以决定将字符串存储在地图中或队列中。

这是 C++ 中的一个实现：

#include <string>
#include <map>
#include <deque>

typedef int         my_key_type;       // Key type
typedef std::string my_value_type;     // Value type

struct queueitem;                                   // Queue element

typedef std::deque<queueitem> my_queue;             // Queue

typedef std::multimap <my_key_type,               
                       my_queue::iterator> my_map;  // Map

typedef std::pair <my_key_type,                  
                   my_queue::iterator> my_map_pair; // Map element

struct queueitem
{
    my_value_type value;
    my_map::iterator mapitem;

    queueitem (const my_value_type & val) : value(val) {}
};

class mapqueue
{
    public:

        mapqueue () {}

        my_value_type find (my_key_type key) const;
        size_t index_of (my_key_type key) const;

        my_value_type front_value () const { return Q.front().value; }
        my_value_type back_value () const { return Q.back().value; }

        my_key_type front_key () const
        { return Q.front().mapitem->first; }

        my_key_type back_key () const
        { return Q.back().mapitem->first; }

        void push_front (my_key_type key,
                         const my_value_type & value);

        void push_back (my_key_type key,
                        const my_value_type & value);

        void pop_front ();
        void pop_back ();

    private:

        my_queue Q;
        my_map M;

        mapqueue (const mapqueue &) {}
        mapqueue & operator= (const mapqueue &) { return *this; }
};

using namespace std;

my_value_type mapqueue::find (my_key_type key) const
{
    my_map::const_iterator it = M.find (key);

    if (it==M.end())
        throw "Not found";

    return it->second->value;
}

size_t mapqueue::index_of (my_key_type key) const
{
    my_map::const_iterator it = M.find (key);

    if (it==M.end())
        throw "Not found";

    return it->second - Q.begin();
}

void mapqueue::push_front (my_key_type key,
                           const my_value_type & value)
{
    Q.push_front (queueitem(value));
    my_queue::iterator qit = Q.begin ();
    qit->mapitem = M.insert (my_map_pair(key,qit));
}

void mapqueue::push_back (my_key_type key,
                          const my_value_type & value)
{
    Q.push_back (queueitem(value));
    my_queue::iterator qit = Q.end () - 1;
    qit->mapitem = M.insert (my_map_pair(key,qit));
}

void mapqueue::pop_front ()
{
    M.erase (Q.front().mapitem);
    Q.pop_front ();
}

void mapqueue::pop_back ()
{
    M.erase (Q.back().mapitem);
    Q.pop_back ();
}

这也支持在 O(log N) 中查找任何给定键的队列中的索引。如果您不需要这个，您可以简化将字符串存储在映射中的设计，并从映射中删除对队列的引用。

更新：键和值类型现在通过typedefs 指定。这样很容易改变它们。将整个事物转换为由这两种类型参数化的模板会很有趣。这样，即使在同一个程序中，相同的代码也可以用于不同的键值类型对。

更新：一般情况下有一个工具：Boost Multi-index Containers Library。请参阅文档中的此示例。

于 2013-02-07T06:37:38.653 回答