3 #ifndef DUNE_COMMON_LRU_HH
4 #define DUNE_COMMON_LRU_HH
25 template <
typename Key,
typename Tp,
26 typename Alloc = std::allocator<Tp> >
27 struct _lru_default_traits
30 typedef Alloc allocator;
31 typedef std::list< std::pair<Key, Tp> > list_type;
32 typedef typename list_type::iterator iterator;
33 typedef typename std::less<key_type> cmp;
34 typedef std::map< key_type, iterator, cmp,
35 typename std::allocator_traits<allocator>::template rebind_alloc<std::pair<const key_type, iterator> > > map_type;
47 template <
typename Key,
typename Tp,
48 typename Traits = _lru_default_traits<Key, Tp> >
51 typedef typename Traits::list_type list_type;
52 typedef typename Traits::map_type map_type;
53 typedef typename Traits::allocator allocator;
54 typedef typename map_type::iterator map_iterator;
55 typedef typename map_type::const_iterator const_map_iterator;
60 using pointer =
typename allocator::value_type*;
74 return _data.front().second;
83 return _data.front().second;
92 return _data.back().second;
101 return _data.back().second;
131 const map_iterator it = _index.find(key);
132 if (it == _index.end())
return _data.end();
143 const map_iterator it = _index.find(key);
144 if (it == _index.end())
return _data.end();
161 std::pair<key_type, value_type> x(key, data);
163 iterator it = _data.insert(_data.begin(), x);
165 _index.insert(std::make_pair(key,it));
186 map_iterator it = _index.find(key);
187 if (it == _index.end())
189 "Failed to touch key " << key <<
", it is not in the lru container");
193 _data.splice(_data.begin(), _data, it->second);
194 return it->second->second;
213 assert(new_size <=
size());
215 while (new_size <
size())
A few common exception classes.
#define DUNE_THROW(E, m)
Definition: exceptions.hh:216
Dune namespace.
Definition: alignedallocator.hh:11
Default exception class for range errors.
Definition: exceptions.hh:252
LRU Cache Container.
Definition: lru.hh:50
void pop_back()
Removes the last element.
Definition: lru.hh:117
iterator find(const key_type &key)
Finds the element whose key is k.
Definition: lru.hh:129
reference insert(const key_type &key)
mark data associated with key as most recent
Definition: lru.hh:173
list_type::const_iterator const_iterator
Definition: lru.hh:66
void resize(size_type new_size)
ensure a maximum size of the container
Definition: lru.hh:211
allocator::size_type size_type
Definition: lru.hh:64
list_type::iterator iterator
Definition: lru.hh:65
allocator::value_type value_type
Definition: lru.hh:59
const_reference front() const
Definition: lru.hh:81
const_reference back([[maybe_unused]] int i) const
Definition: lru.hh:99
typename allocator::value_type const * const_pointer
Definition: lru.hh:61
size_type size() const
Retrieve number of entries in the container.
Definition: lru.hh:200
typename allocator::value_type & reference
Definition: lru.hh:63
reference back()
Definition: lru.hh:90
void pop_front()
Removes the first element.
Definition: lru.hh:108
reference front()
Definition: lru.hh:72
void clear()
Definition: lru.hh:222
reference touch(const key_type &key)
mark data associated with key as most recent
Definition: lru.hh:183
reference insert(const key_type &key, const_reference data)
Insert a value into the container.
Definition: lru.hh:159
typename allocator::value_type * pointer
Definition: lru.hh:60
const_iterator find(const key_type &key) const
Finds the element whose key is k.
Definition: lru.hh:141
typename allocator::value_type const & const_reference
Definition: lru.hh:62
Traits::key_type key_type
Definition: lru.hh:58