Posted By

omarelsaid on 07/10/15


Tagged

map Vector


Versions (?)

Vector Map


 / Published in: C++
 

An implementation of a map using a vector

  1. #ifndef CADENCE_VECTORMAP_HPP
  2. #define CADENCE_VECTORMAP_HPP
  3.  
  4. #include <vector>
  5. #include <iterator>
  6.  
  7. template<typename Key, typename Value>
  8. class vectormap
  9. {
  10. public:
  11. vectormap() : mNeedSorting(false) { }
  12.  
  13. class iterator : public std::iterator<std::forward_iterator_tag, std::pair<Key, Value> >
  14. {
  15. iterator(std::pair<Key, Value>* ptr) : p(ptr) { }
  16. public:
  17. iterator() : p(NULL) { }
  18.  
  19. typedef std::pair<Key, Value>& reference;
  20. typedef std::pair<Key, Value>* pointer;
  21.  
  22. iterator operator+(const unsigned int n)
  23. {
  24. iterator temp(*this);
  25. for (unsigned int i = 0; i < n; ++i)
  26. ++temp;
  27.  
  28. return temp;
  29. }
  30.  
  31. iterator operator++(int dummy) { iterator temp(*this); ++p; return temp; }
  32. iterator operator++() { ++p; return *this; }
  33. bool operator==(const iterator& rhs) { return p == rhs.p; }
  34. bool operator!=(const iterator& rhs) { return p != rhs.p; }
  35.  
  36. reference operator*() { return *p; }
  37. pointer operator->() { return p; }
  38.  
  39. private:
  40. std::pair<Key, Value>* p;
  41.  
  42. friend class vectormap;
  43. };
  44.  
  45. iterator begin()
  46. {
  47. if (mNeedSorting)
  48. {
  49. _sort(0, mData.size() - 1);
  50. mNeedSorting = false;
  51. }
  52.  
  53. return iterator(&mData.at(0));
  54. }
  55.  
  56. iterator end()
  57. {
  58. if (mNeedSorting)
  59. {
  60. _sort(0, mData.size() - 1);
  61. mNeedSorting = false;
  62. }
  63.  
  64. return iterator(&mData.at(0)) + mData.size();
  65. }
  66.  
  67. void insert(const std::pair<Key, Value>& element)
  68. {
  69. if (mNeedSorting)
  70. {
  71. _sort(0, mData.size() - 1);
  72. mNeedSorting = false;
  73. }
  74.  
  75. if (!mData.empty())
  76. {
  77. iterator itr = find(element.first);
  78. if (itr != end())
  79. {
  80. *itr = element;
  81. return;
  82. }
  83. }
  84.  
  85. mData.push_back(element);
  86. _sort(0, mData.size() - 1);
  87. }
  88.  
  89. iterator find(const Key& key)
  90. {
  91. if (mNeedSorting)
  92. {
  93. _sort(0, mData.size() - 1);
  94. mNeedSorting = false;
  95. }
  96.  
  97. return _find(key, begin(), end());
  98. }
  99.  
  100. Value& operator[](const Key& key)
  101. {
  102. if (mNeedSorting)
  103. {
  104. _sort(0, mData.size() - 1);
  105. mNeedSorting = false;
  106. }
  107.  
  108. if (!mData.empty())
  109. {
  110. iterator foundItr = find(key);
  111.  
  112. if (foundItr != end())
  113. return foundItr->second;
  114. }
  115.  
  116. mData.push_back(std::make_pair(key, Value()));
  117. mNeedSorting = true;
  118. return mData.back().second;
  119. }
  120.  
  121. private:
  122. iterator _find(const Key& key, iterator beginItr, iterator endItr)
  123. {
  124. if (1 == std::distance(beginItr, endItr))
  125. {
  126. if (beginItr->first == key)
  127. return beginItr;
  128. else
  129. return end();
  130. }
  131.  
  132. iterator midItr = beginItr + (std::distance(beginItr, endItr) - 1) / 2;
  133. if (key <= midItr->first)
  134. return _find(key, beginItr, ++midItr);
  135. else
  136. return _find(key, ++midItr, endItr);
  137. }
  138.  
  139. void _sort(unsigned int begin, unsigned int end)
  140. {
  141. if (begin == end)
  142. return;
  143.  
  144. unsigned int mid = (begin + end) / 2;
  145. if (mData.at(end).first < mData.at(mid).first)
  146. {
  147. std::swap(mData[end], mData[mid]);
  148. _sort(begin, mid);
  149. _sort(mid + 1, end);
  150. }
  151. else
  152. {
  153. _sort(mid + 1, end);
  154. }
  155. }
  156.  
  157. std::vector<std::pair<Key, Value> > mData;
  158. bool mNeedSorting;
  159. };
  160.  
  161. #endif // CADENCE_VECTORMAP_HPP

Report this snippet  

You need to login to post a comment.