[C++] STL을 사용한 linked map 구현~

최근 LRU Cache 구현을 위해 STL을 사용한 template 기반의 class를 찾았습니다~
(예전 같으면 그냥 구현을 했을텐데.. 이것도 귀찮아 지네요^^)

필요하신 분들이 있을것 같아 올립니다~

#include <list>
#include <set>
#include <utility>

template < typename KeyType, typename MappedType,
typename Comp = std::less< KeyType > >
struct linked_map {
 typedef KeyType key_type;
 typedef MappedType mapped_type;
 typedef std::pair< const key_type, mapped_type > value_type;

private:
 typedef std::list< value_type >      list_type;
 typedef typename list_type::iterator list_iterator;

 struct compare_keys {
  Comp _order;

  compare_keys ( Comp o): _order(o) {}
  bool operator() ( list_iterator lhs, list_iterator rhs) const {
   return _order( lhs->first, rhs->first);
  }
 };

 typedef std::set< list_iterator, compare_keys > set_type;
 typedef typename set_type::iterator             set_iterator;

 list_type _list;
 set_type  _set;

public:
 typedef list_iterator iterator;
 typedef typename set_type::size_type size_type;

 linked_map( Comp o = Comp())
  : _list()
  , _set( compare_keys(o)) {}

 iterator find( key_type const &key) {
  value_type v( key, mapped_type());
  list_type  l;
  l.push_back( v);
  set_iterator where = _set.find( l.begin());
  return ((where == _set.end()) ? _list.end(): *where);
 }

 iterator insert( value_type const &value) {
  list_type l;
  l.push_back( value);
  set_iterator where = _set.find( l.begin());
  if (where == _set.end()) {
   _list.push_back( value);
   list_iterator pos = _list.end();
   --pos;
   _set.insert( pos);
   return pos;
  } else {
   (*where)->second = value.second;
   return *where;
  }
 }

 iterator erase( iterator where) {
  _set.erase( where);
  return _list.erase( where);
 }

 iterator begin(void) { return _list.begin(); }
 iterator end(void) { return _list.end(); }

 size_type size(void) const { return _set.size(); }

 mapped_type & operator[]( key_type const &key) {
  iterator pos = insert( std::make_pair( key, mapped_type()));
  return pos->second;
 }

 void splice( iterator position, iterator where) { _list.splice( position, _list, where); }
 // push_front() { splice( begin(), find(x)); }
};

일단, 구조 자체는 LRU cache처럼 저장 가능한 갯수의 제한을 하지는 않습니다. 그리고, 읽은 위치를
처음으로 조정하기 위해서는 splice()함수를 사용하시면 됩니다^^

몇가지만 수정하시면 lru 관련된 class를 쉽게 구현하실수 있습니다~