You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

limitedmap.h 3.4KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
  1. // Copyright (c) 2012-2016 The Starwels developers
  2. // Distributed under the MIT software license, see the accompanying
  3. // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  4. #ifndef STARWELS_LIMITEDMAP_H
  5. #define STARWELS_LIMITEDMAP_H
  6. #include <assert.h>
  7. #include <map>
  8. /** STL-like map container that only keeps the N elements with the highest value. */
  9. template <typename K, typename V>
  10. class limitedmap
  11. {
  12. public:
  13. typedef K key_type;
  14. typedef V mapped_type;
  15. typedef std::pair<const key_type, mapped_type> value_type;
  16. typedef typename std::map<K, V>::const_iterator const_iterator;
  17. typedef typename std::map<K, V>::size_type size_type;
  18. protected:
  19. std::map<K, V> map;
  20. typedef typename std::map<K, V>::iterator iterator;
  21. std::multimap<V, iterator> rmap;
  22. typedef typename std::multimap<V, iterator>::iterator rmap_iterator;
  23. size_type nMaxSize;
  24. public:
  25. limitedmap(size_type nMaxSizeIn)
  26. {
  27. assert(nMaxSizeIn > 0);
  28. nMaxSize = nMaxSizeIn;
  29. }
  30. const_iterator begin() const { return map.begin(); }
  31. const_iterator end() const { return map.end(); }
  32. size_type size() const { return map.size(); }
  33. bool empty() const { return map.empty(); }
  34. const_iterator find(const key_type& k) const { return map.find(k); }
  35. size_type count(const key_type& k) const { return map.count(k); }
  36. void insert(const value_type& x)
  37. {
  38. std::pair<iterator, bool> ret = map.insert(x);
  39. if (ret.second) {
  40. if (map.size() > nMaxSize) {
  41. map.erase(rmap.begin()->second);
  42. rmap.erase(rmap.begin());
  43. }
  44. rmap.insert(make_pair(x.second, ret.first));
  45. }
  46. }
  47. void erase(const key_type& k)
  48. {
  49. iterator itTarget = map.find(k);
  50. if (itTarget == map.end())
  51. return;
  52. std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second);
  53. for (rmap_iterator it = itPair.first; it != itPair.second; ++it)
  54. if (it->second == itTarget) {
  55. rmap.erase(it);
  56. map.erase(itTarget);
  57. return;
  58. }
  59. // Shouldn't ever get here
  60. assert(0);
  61. }
  62. void update(const_iterator itIn, const mapped_type& v)
  63. {
  64. // Using map::erase() with empty range instead of map::find() to get a non-const iterator,
  65. // since it is a constant time operation in C++11. For more details, see
  66. // https://stackoverflow.com/questions/765148/how-to-remove-constness-of-const-iterator
  67. iterator itTarget = map.erase(itIn, itIn);
  68. if (itTarget == map.end())
  69. return;
  70. std::pair<rmap_iterator, rmap_iterator> itPair = rmap.equal_range(itTarget->second);
  71. for (rmap_iterator it = itPair.first; it != itPair.second; ++it)
  72. if (it->second == itTarget) {
  73. rmap.erase(it);
  74. itTarget->second = v;
  75. rmap.insert(make_pair(v, itTarget));
  76. return;
  77. }
  78. // Shouldn't ever get here
  79. assert(0);
  80. }
  81. size_type max_size() const { return nMaxSize; }
  82. size_type max_size(size_type s)
  83. {
  84. assert(s > 0);
  85. while (map.size() > s) {
  86. map.erase(rmap.begin()->second);
  87. rmap.erase(rmap.begin());
  88. }
  89. nMaxSize = s;
  90. return nMaxSize;
  91. }
  92. };
  93. #endif // STARWELS_LIMITEDMAP_H