1

マップ ( ) があり、使用されているキーを最新のものから最も古いものへstd::map<key_t, val_t>と追跡したいと考えています。

これは私が試したものですが、循環依存の宣言で行き詰まります:

typedef ... key_t;

typedef struct {
    ...
    mru_list_t::iterator mru_it;
} val_t;

typedef std::map<key_t, val_t> foo_map_t;

typedef std::list<foo_map_t::iterator> mru_list_t;

更新ルーチンは非常に簡単に見えます。

foo_map_t foo_map;
mru_list_t mru_list;

void use(const key_t& key) {

    // get the entry corresponding to the key
    std::pair<foo_map_t::iterator, bool> r;
    r = foo_map.insert(std::make_pair(key, val_t()));
    foo_map_t::iterator map_it = r.first;

    // the corresponding value
    val_t *val = &(*map_it).second;

    // did it already exist?
    if (!r.second) {
        // remove from the mru list
        mru_list.erase(val->mru_it);
    }

    // push to the front of the list
    mru_list.push_front(map_it);
    val->mru_it = mru_list.begin();
}

これにどのように対処すればよいですか？(循環依存)

代わりにポインターを宣言して使用できることを知っています。

typedef struct _key_t key_t;
typedef struct _val_t val_t;
typedef std::list<std::pair<key_t, val_t> *> mru_list_t;

しかし、これは文書化されていない機能に依存しているようです。

編集:または、これはできないことを認識する必要がありますか? (そして、文書化されていない機能を使用するか、独自のリンクリストを展開するか、そうでなければ、パーツを他の非 stl コンテナーに置き換えますか?)

4

2 に答える 2

0

キーとして使用しているものの種類に応じて、単一値マップを使用しているという事実のためにkey_t、イテレータをstd::map. マップにはキーごとに 1 つの値しかないため、要素への一意のアクセス権が引き続きあり、この恐ろしい循環依存の問題を取り除くことができます。

コードは次のようになります。

typedef std::list<key_t> mru_list_t;

リストのタイプ、およびuse関数の最後で、次のように変更する必要があります。

mru_list.push_front(map_it);

に

mru_list.push_front(map_it->first);
于 2012-11-17T15:23:56.467 に答える
0

同じデータに対して複数のインデックスを許可するように構築されている (したがって、複数の注文に一致する可能性がある) Boost Multi Indexを確認することをお勧めします。

より具体的には、MRUの例が既にありますが、今は見たくないかもしれませんが、自分でライブラリを試してみてください。

Boost Multi-Index の主なアイデアは、要素へのポインタと、同期が取れなくなる可能性のある複数の相互に関連する構造を持つ代わりに、複数のインデックスにフックされるように設計されたコンテナー セルに各要素を刻み込むことです。

MRU の例では、たとえば、各「値」を に書き込むことにより、リンクされたリストを自分で実装できますstruct V { value_t value; V* next; }。

于 2012-11-17T16:32:21.253 に答える