1 // Copyright (c) 2012-2015 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5 #ifndef BITCOIN_MRUSET_H
6 #define BITCOIN_MRUSET_H
12 /** STL-like set container that only keeps the most recent N elements. */
19 typedef typename
std::set
<T
>::iterator iterator
;
20 typedef typename
std::set
<T
>::const_iterator const_iterator
;
21 typedef typename
std::set
<T
>::size_type size_type
;
25 std::vector
<iterator
> order
;
27 size_type first_unused
;
28 const size_type nMaxSize
;
31 mruset(size_type nMaxSizeIn
= 1) : nMaxSize(nMaxSizeIn
) { clear(); }
32 iterator
begin() const { return set
.begin(); }
33 iterator
end() const { return set
.end(); }
34 size_type
size() const { return set
.size(); }
35 bool empty() const { return set
.empty(); }
36 iterator
find(const key_type
& k
) const { return set
.find(k
); }
37 size_type
count(const key_type
& k
) const { return set
.count(k
); }
41 order
.assign(nMaxSize
, set
.end());
45 bool inline friend operator==(const mruset
<T
>& a
, const mruset
<T
>& b
) { return a
.set
== b
.set
; }
46 bool inline friend operator==(const mruset
<T
>& a
, const std::set
<T
>& b
) { return a
.set
== b
; }
47 bool inline friend operator<(const mruset
<T
>& a
, const mruset
<T
>& b
) { return a
.set
< b
.set
; }
48 std::pair
<iterator
, bool> insert(const key_type
& x
)
50 std::pair
<iterator
, bool> ret
= set
.insert(x
);
52 if (set
.size() == nMaxSize
+ 1) {
53 set
.erase(order
[first_used
]);
54 order
[first_used
] = set
.end();
55 if (++first_used
== nMaxSize
) first_used
= 0;
57 order
[first_unused
] = ret
.first
;
58 if (++first_unused
== nMaxSize
) first_unused
= 0;
62 size_type
max_size() const { return nMaxSize
; }
65 #endif // BITCOIN_MRUSET_H