1

次の機能を備えたデータ構造を探しています：-キーと値を持っています-O（n）> t> O（logn）またはO（1）で値を見つけることができます-最初の要素と最後の要素をプルできます挿入します。

TreeMepは良くありません。なぜなら、キー（文字列として） "b"を挿入し、次にキー "a"を挿入すると、最初のキーをプルすると、"b"ではなく"a"が返されるからです。

サイズ関数に頼ることができないため、ConcurrentSkipListMapは適切ではありません。

助けていただければ幸いです

ありがとう

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で指定されるようになりました。このように、それらを変更するのは簡単です。これらの2つのタイプによってパラメーター化されたテンプレートですべてを変換することは興味深いでしょう。このように、同じプログラム内であっても、同じコードをKey-Valueタイプの異なるペアに再利用できます。

更新：一般的な場合のツールがあります： Boost Multi-indexContainersLibrary。ドキュメントのこの例を参照してください。

于 2013-02-07T06:37:38.653 に答える