3

メモリ アドレスを格納する非常に単純な LRU キャッシュを実装する必要があります。

  • これらのアドレスの数は (実行時に) 固定されています。
  • 最後に使用されたアドレスのみに関心があります (他の要素の順序は気にしません)。
  • 各アドレスには対応するインデックス番号 (単純な整数) がありますが、これは一意ではなく、変更される可能性があります。

実装は、可能な限り少ないオーバーヘッドで実行する必要があります。各アドレスに加えて、関連する情報構造 (インデックスを含む) もあります。

私の現在のアプローチはstd::list、アドレス/情報のペアを格納するために a を使用しており、boost::unordered_multimapこれはインデックスとリストの関連する反復子の間のマッピングです。

次の例は、私の製品コードとは関係ありません。これは、理解を深めるためのものであることに注意してください。

struct address_info
{
    address_info() : i(-1) {}
    int i;
    // more ...
};


int main()
{
    int const MAX_ADDR_COUNT = 10,
              MAX_ADDR_SIZE  = 64;

    char** s           = new char*[MAX_ADDR_COUNT];
    address_info* info = new address_info[MAX_ADDR_COUNT]();

    for (int i = 0; i < MAX_ADDR_COUNT; ++i)
        s[i] = new char[MAX_ADDR_SIZE]();

    typedef boost::unordered_multimap<int, std::list<std::pair<address_info, char*>>::const_iterator> index_address_map;

    std::list<std::pair<address_info, char*>> list(MAX_ADDR_COUNT);
    index_address_map                  map;

    {
        int i = 0;
        for (std::list<std::pair<address_info, char*>>::iterator iter = list.begin(); i != MAX_ADDR_COUNT; ++i, ++iter)
            *iter = std::make_pair(info[i], s[i]);
    }

    // usage example:
    // try to find address_info 4
    index_address_map::const_iterator iter = map.find(4);
    if (iter == map.end())
    {
        std::pair<address_info, char*>& lru = list.back();

        if (lru.first.i != -1)
            map.erase(lru.first.i);
        lru.first.i = 4;

        list.splice(list.begin(), list, boost::prior(list.end()));
        map.insert(std::make_pair(4, list.begin()));
    }
    else
        list.splice(list.begin(), list, iter->second);

    for (int i = 0; i < MAX_ADDR_COUNT; ++i)
        delete[] s[i];

    delete[] info;
    delete[] s;

    return 0;
}
4

1 に答える 1

2

通常の推奨事項は、タスクの Boost.MultiIndex を掘り下げることです。

  • インデックス 0: 挿入の順序
  • index 1: 要素のキー (バイナリ検索またはハッシュ)

私の記憶が正しければ、Boost サイトでもデモが行われています。

于 2011-07-04T12:40:53.620 に答える