c++ - C ++マップと循環バッファを混在させる方法は?

Question

ブースト循環バッファーのように機能するマップを作成することは可能でしょうか。つまり、サイズが制限され、制限されたサイズに達すると、最初に挿入された要素が上書きされ始めます。find or createまた、そのようなバッファを介して検索できるようにしたいと考えています[name]。そのようなものを作成することは可能ですか？

Answer 1

必要なものは、必要に応じて、LRU (最近使用されていない) マップまたは LRA (最近追加されていない) マップです。

実装は既に存在します。

Answer 2

それはマップにとってあまり意味がないので、実際には「循環バッファ」ではありませんが、リンクされたリストなどを追加せずに単純な配列を使用できます。

これはクローズドハッシュと呼ばれます - ウィキの記事はそれを非常にうまく要約しています. ダブル ハッシュは、クラスタリング (パフォーマンスの低下につながる) を回避するため、最もよく使用されますが、独自の問題 (局所性) があります。

編集：特定の実装が必要なので、ブーストには実装がないと思いますが、これまたはこれはクローズドハッシュに関する別のSO投稿で言及されました..

Answer 3

まあ、構造はブーストにそのままでは存在しないと思います（ただし、他の場所に存在する可能性があります）ので、作成する必要があります。operator[]()ただし、少なくとも で実装されているため、を使用することはお勧めしませんstd::map。これは、マップに追加された要素を追跡するのが難しくなる可能性があるためです (たとえば、値で使用operator[]()すると、その空の値がマップに追加されます)。マップの要素を追加および取得するためのより明示的な get および put 操作。

map最も簡単な実装については、ストレージとして実際のを使用し、deque追加された要素のストレージに (テストされていません) を使用します。

template <typename K, typename V>
struct BoundedSpaceMap
{
    typedef std::map<K,V> map_t;
    typedef std::deque<K> deque_t;

    // ...
    typedef value_type map_t::value_type;
    // Reuse map's iterators
    typedef iterator map_t::iterator;

    // ...
    iterator begin() { return map_.begin(); }

    // put
    void put ( K k, V v)
    { map_.insert(std::make_pair(k,v));
      deque_.push_back(k);
      _ensure();  // ensure the size of the map, and remove the last element
    }

     // ...

private:
     map_t map_;
     deque_t deque_;

     void _ensure() { 
       if (deque_size() > LIMIT) { 
         map_.erase(deque_.front()); deque_.pop_front();
       }
     }
};