5#ifndef DUNE_COMMON_LRU_HH
6#define DUNE_COMMON_LRU_HH
27 template <
typename Key,
typename Tp,
28 typename Alloc = std::allocator<Tp> >
29 struct _lru_default_traits
32 typedef Alloc allocator;
33 typedef std::list< std::pair<Key, Tp> > list_type;
34 typedef typename list_type::iterator iterator;
35 typedef typename std::less<key_type> cmp;
36 typedef std::map< key_type, iterator, cmp,
37 typename std::allocator_traits<allocator>::template rebind_alloc<std::pair<const key_type, iterator> > > map_type;
49 template <
typename Key,
typename Tp,
50 typename Traits = _lru_default_traits<Key, Tp> >
53 typedef typename Traits::list_type list_type;
54 typedef typename Traits::map_type map_type;
55 typedef typename Traits::allocator allocator;
56 typedef typename map_type::iterator map_iterator;
57 typedef typename map_type::const_iterator const_map_iterator;
60 typedef typename Traits::key_type key_type;
61 typedef typename allocator::value_type value_type;
62 using pointer =
typename allocator::value_type*;
63 using const_pointer =
typename allocator::value_type
const*;
64 using const_reference =
typename allocator::value_type
const&;
65 using reference =
typename allocator::value_type&;
66 typedef typename allocator::size_type size_type;
67 typedef typename list_type::iterator iterator;
68 typedef typename list_type::const_iterator const_iterator;
76 return _data.front().second;
85 return _data.front().second;
94 return _data.back().second;
101 const_reference
back ([[maybe_unused]]
int i)
const
103 return _data.back().second;
112 key_type k = _data.front().first;
121 key_type k = _data.back().first;
131 iterator
find (
const key_type & key)
133 const map_iterator it = _index.find(key);
134 if (it == _index.end())
return _data.end();
143 const_iterator
find (
const key_type & key)
const
145 const map_iterator it = _index.find(key);
146 if (it == _index.end())
return _data.end();
161 reference
insert (
const key_type & key, const_reference data)
163 std::pair<key_type, value_type> x(key, data);
165 iterator it = _data.insert(_data.begin(), x);
167 _index.insert(std::make_pair(key,it));
185 reference
touch (
const key_type & key)
188 map_iterator it = _index.find(key);
189 if (it == _index.end())
191 "Failed to touch key " << key <<
", it is not in the lru container");
195 _data.splice(_data.begin(), _data, it->second);
196 return it->second->second;
215 assert(new_size <=
size());
217 while (new_size <
size())
Default exception class for range errors.
Definition: exceptions.hh:254
LRU Cache Container.
Definition: lru.hh:52
void pop_back()
Removes the last element.
Definition: lru.hh:119
iterator find(const key_type &key)
Finds the element whose key is k.
Definition: lru.hh:131
reference insert(const key_type &key)
mark data associated with key as most recent
Definition: lru.hh:175
void resize(size_type new_size)
ensure a maximum size of the container
Definition: lru.hh:213
const_reference front() const
Definition: lru.hh:83
size_type size() const
Retrieve number of entries in the container.
Definition: lru.hh:202
reference back()
Definition: lru.hh:92
void pop_front()
Removes the first element.
Definition: lru.hh:110
reference front()
Definition: lru.hh:74
reference touch(const key_type &key)
mark data associated with key as most recent
Definition: lru.hh:185
reference insert(const key_type &key, const_reference data)
Insert a value into the container.
Definition: lru.hh:161
const_iterator find(const key_type &key) const
Finds the element whose key is k.
Definition: lru.hh:143
const_reference back(int i) const
Definition: lru.hh:101
A few common exception classes.
#define DUNE_THROW(E, m)
Definition: exceptions.hh:218
Dune namespace.
Definition: alignedallocator.hh:13