1 /* STL-conforming "sorted vector" container 2 * 3 * (C) 2002 Martin Holzherr (holzherr@infobrain.com). All rights reserved. 4 * 5 * Permission is granted to use, distribute and modify this code provided that: 6 * � this copyright notice appears, 7 * � 8 * The author welcomes any suggestions on the code or reportings of actual 9 * use of the code. Please send your comments to holzherr@infobrain.com. 10 * 11 * The author makes NO WARRANTY or representation, either express or implied, 12 * with respect to this code, its quality, accuracy, merchantability, or 13 * fitness for a particular purpose. This software is provided "AS IS", and 14 * you, its user, assume the entire risk as to its quality and accuracy. 15 * 16 * Created: November 19th, 2002 17 * Last modified: November 27th, 2002 18 (changed namespace from std to codeproject; 19 uses template member functions for MSCVER>=1300) 20 21 */ 22 23 #ifndef SORTED_VECTOR_ 24 #define SORTED_VECTOR_ 25 26 #include <algorithm> 27 #include <vector> 28 #include <utility> 29 #include <functional> 30 31 namespace pan 32 { 33 /** 34 * std::set implemented as a sorted vector. 35 * 36 * This can give a significant memory improvement over std::set, 37 * which is implemented as a tree. The tradeoff is that insertion 38 * and removal is slow, so this is best used on sets whose contents 39 * rarely change. 40 * 41 * This class was written by Martin Holzherr and is in the public domain. 42 */ 43 template<class K, bool bNoDuplicates= false,class Pr = std::less<K>, class A = std::allocator<K> > 44 class sorted_vector { 45 public: 46 typedef sorted_vector<K,bNoDuplicates,Pr,A> Myt_; 47 typedef std::vector<K,A> Cont; 48 typedef typename Cont::allocator_type allocator_type; 49 typedef typename Cont::size_type size_type; 50 typedef typename Cont::difference_type difference_type; 51 typedef typename Cont::reference reference; 52 typedef typename Cont::const_reference const_reference; 53 typedef typename Cont::value_type value_type; 54 typedef K key_type; 55 typedef typename Cont::iterator iterator; 56 typedef typename Cont::const_iterator const_iterator; 57 typedef Pr key_compare; 58 typedef Pr value_compare; 59 60 typedef typename Cont::const_reverse_iterator 61 const_reverse_iterator; 62 typedef typename Cont::reverse_iterator reverse_iterator; 63 64 typedef std::pair<iterator, iterator> Pairii_; 65 typedef std::pair<const_iterator, const_iterator> Paircc_; 66 typedef std::pair<iterator, bool> Pairib_; 67 explicit sorted_vector(const Pr& pred = Pr(),const A& al = A()) key_compare_(pred)68 :key_compare_(pred),vec_(al){} 69 template<class It> 70 sorted_vector(It first, It beyond, 71 const Pr& pred = Pr(),const A& al = A()) key_compare_(pred)72 :key_compare_(pred),vec_(first,beyond,al) 73 {stable_sort();} sorted_vector(const Myt_ & x)74 sorted_vector(const Myt_& x) 75 : key_compare_(x.key_compare_), vec_(x.vec_) 76 {} ~sorted_vector()77 ~sorted_vector() {} 78 Myt_& operator=(const Myt_& x) {vec_.operator=(x.vec_); 79 key_compare_= x.key_compare_; 80 return *this;} 81 Myt_& operator=(const Cont& x){vec_.operator=(x); 82 sort();return *this;} 83 reserve(size_type n)84 void reserve(size_type n) {vec_.reserve(n);} begin()85 iterator begin() {return vec_.begin(); } begin()86 const_iterator begin() const {return vec_.begin(); } end()87 iterator end() {return vec_.end();} end()88 const_iterator end() const {return vec_.end();} rbegin()89 reverse_iterator rbegin() {return vec_.rbegin();} rbegin()90 const_reverse_iterator rbegin() const 91 {return vec_.rbegin();} 92 rend()93 reverse_iterator rend() {return vec_.rend();} rend()94 const_reverse_iterator rend() const 95 {return vec_.rend();} 96 97 size()98 size_type size() const {return vec_.size();} max_size()99 size_type max_size() const {return vec_.max_size();} empty()100 bool empty() const {return vec_.empty();} get_allocator()101 A get_allocator() const {return vec_.get_allocator();} at(size_type p)102 const_reference at(size_type p) const {return vec_.at(p);} at(size_type p)103 reference at(size_type p) {return vec_.at(p);} 104 const_reference operator[](size_type p) const 105 {return vec_.operator[](p);} 106 107 reference operator[](size_type p) {return vec_.operator[](p);} front()108 reference front() {return vec_.front();} front()109 const_reference front() const {return vec_.front();} back()110 reference back() {return vec_.back();} back()111 const_reference back() const {return vec_.back();} pop_back()112 void pop_back() {vec_.pop_back();} 113 assign(const_iterator first,const_iterator beyond)114 void assign(const_iterator first, const_iterator beyond) 115 {vec_.assign(first,beyond);} 116 void assign(size_type n, const K& x = K()) 117 {vec_.assign(n,x);} 118 /*insert members*/ insert(const value_type & x)119 Pairib_ insert(const value_type& x) 120 { 121 if(bNoDuplicates){ 122 iterator p= lower_bound(x); 123 if(p==end()||key_compare_(x,*p)){ 124 return Pairib_(InsertImpl_(p,x),true); 125 }else{ 126 return Pairib_(p,false); 127 } 128 }else{ 129 iterator p= upper_bound(x); 130 return Pairib_(InsertImpl_(p,x),true); 131 } 132 } insert(iterator it,const value_type & x)133 iterator insert(iterator it, const value_type& x)//it is the hint 134 { 135 if(it!=end() ){ 136 if(bNoDuplicates){ 137 if(key_compare_(*it,x)){ 138 if((it+1)==end()||KeyCompare_Gt_(*(it+1),x)){//use hint 139 return InsertImpl_(it+1,x); 140 }else if(KeyCompare_Geq_(*(it+1),x)){ 141 return end(); 142 } 143 } 144 }else{ 145 if( KeyCompare_Leq_(*it,x) 146 &&((it+1)==end()||KeyCompare_Geq_(*(it+1),x))){ 147 return InsertImpl_(it+1,x); 148 } 149 } 150 } 151 return insert(x).first; 152 } 153 template<class It> insert(It first,It beyond)154 void insert(It first, It beyond) 155 { 156 size_type n= std::distance(first,beyond); 157 reserve(size()+n); 158 for( ;first!=beyond;++first){ 159 insert(*first); 160 } 161 } erase(iterator p)162 iterator erase(iterator p) {return vec_.erase(p);} erase(iterator first,iterator beyond)163 iterator erase(iterator first, iterator beyond) 164 {return vec_.erase(first,beyond);} erase(const K & key)165 size_type erase(const K& key) 166 { 167 Pairii_ begEnd= equal_range(key); 168 size_type n= std::distance(begEnd.first,begEnd.second); 169 erase(begEnd.first,begEnd.second); 170 return n; 171 } clear()172 void clear() {return vec_.clear();} 173 Eq_(const Myt_ & x)174 bool Eq_(const Myt_& x) const 175 {return (size() == x.size() 176 && std::equal(begin(), end(), x.begin())); } Lt_(const Myt_ & x)177 bool Lt_(const Myt_& x) const 178 {return (std::lexicographical_compare(begin(), end(), 179 x.begin(), x.end()));} swap(Myt_ & x)180 void swap(Myt_& x) 181 {vec_.swap(x.vec_);std::swap(key_compare_,x.key_compare_);} 182 swap(Myt_ & x,Myt_ & Y_)183 friend void swap(Myt_& x, Myt_& Y_) 184 {x.swap(Y_); } 185 key_comp()186 key_compare key_comp() const {return key_compare_; } value_comp()187 value_compare value_comp() const {return (key_comp()); } 188 find(const KeyType & k)189 template<class KeyType> iterator find (const KeyType& k) 190 { iterator p(lower_bound(k)), e(end()); return (p==e||key_compare_(k,*p))?e:p; } find(const KeyType & k)191 template<class KeyType> const_iterator find (const KeyType& k) const 192 { const_iterator p(lower_bound(k)), e(end()); return (p==e||key_compare_(k,*p))?e:p; } 193 count(const K & k)194 size_type count(const K& k) const 195 {Paircc_ Ans_ = equal_range(k); 196 size_type n = std::distance(Ans_.first, Ans_.second); 197 return (n); } 198 lower_bound(const KeyType & k)199 template<class KeyType> iterator lower_bound (const KeyType& k) 200 { return std::lower_bound(begin(), end(), k, key_compare_); } lower_bound(const KeyType & k)201 template<class KeyType> const_iterator lower_bound (const KeyType& k) const 202 { return std::lower_bound(begin(), end(), k, key_compare_); } upper_bound(const KeyType & k)203 template<class KeyType> iterator upper_bound (const KeyType& k) 204 { return std::upper_bound(begin(), end(), k, key_compare_); } upper_bound(const KeyType & k)205 template<class KeyType> const_iterator upper_bound (const KeyType& k) const 206 { return std::upper_bound(begin(), end(), k, key_compare_); } equal_range(const KeyType & k)207 template<class KeyType> Pairii_ equal_range (const KeyType& k) 208 { return std::equal_range(begin(), end(), k, key_compare_); } equal_range(const KeyType & k)209 template<class KeyType> Paircc_ equal_range (const KeyType& k) const 210 { return std::equal_range(begin(), end(), k, key_compare_); } 211 212 /*functions for use with direct std::vector-access*/ get_container()213 Cont& get_container() 214 {return vec_;} sort()215 void sort()//restore sorted order after low level access 216 { std::sort(vec_.begin(),vec_.end(),key_compare_); 217 if( bNoDuplicates ){ 218 vec_.erase(Unique_(),vec_.end()); 219 } 220 } stable_sort()221 void stable_sort()//restore sorted order after low level access 222 { std::stable_sort(vec_.begin(),vec_.end(),key_compare_); 223 if( bNoDuplicates ){ 224 erase(Unique_(),end()); 225 } 226 } 227 protected: Unique_()228 iterator Unique_() 229 { iterator front_= vec_.begin(),out_= vec_.end(),end_=vec_.end(); 230 bool bCopy_= false; 231 for(iterator prev_; (prev_=front_)!=end_ && ++front_!=end_; ){ 232 if( key_compare_(*prev_,*front_)){ 233 if(bCopy_){ 234 *out_= *front_; 235 out_++; 236 } 237 }else{ 238 if(!bCopy_){out_=front_;bCopy_=true;} 239 } 240 } 241 return out_; 242 } InsertImpl_(iterator p,const value_type & x)243 iterator InsertImpl_(iterator p,const value_type& x) 244 {return vec_.insert(p,x);} KeyCompare_Leq_(const K & ty0,const K & ty1)245 bool KeyCompare_Leq_(const K& ty0,const K& ty1) 246 {return !key_compare_(ty1,ty0);} KeyCompare_Geq_(const K & ty0,const K & ty1)247 bool KeyCompare_Geq_(const K& ty0,const K& ty1) 248 {return !key_compare_(ty0,ty1);} KeyCompare_Gt_(const K & ty0,const K & ty1)249 bool KeyCompare_Gt_(const K& ty0,const K& ty1) 250 {return key_compare_(ty1,ty0);} 251 252 key_compare key_compare_; 253 Cont vec_; 254 }; 255 256 257 template<class K,bool bNoDuplicates,class Pr, class A> inline 258 bool operator==(const sorted_vector<K, bNoDuplicates,Pr,A>& x, 259 const sorted_vector<K, bNoDuplicates,Pr,A>& Y_) 260 {return x.Eq_(Y_); } 261 template<class K,bool bNoDuplicates,class Pr, class A> inline 262 bool operator!=(const sorted_vector<K, bNoDuplicates,Pr,A>& x, 263 const sorted_vector<K, bNoDuplicates,Pr,A>& Y_) 264 {return !(x == Y_); } 265 template<class K,bool bNoDuplicates,class Pr, class A> inline 266 bool operator<(const sorted_vector<K, bNoDuplicates,Pr,A>& x, 267 const sorted_vector<K, bNoDuplicates,Pr,A>& Y_) 268 {return x.Lt_(Y_);} 269 template<class K,bool bNoDuplicates,class Pr,class A> inline 270 bool operator>(const sorted_vector<K, bNoDuplicates,Pr,A>& x, 271 const sorted_vector<K, bNoDuplicates,Pr,A>& Y_) 272 {return Y_ < x; } 273 template<class K,bool bNoDuplicates,class Pr, class A> inline 274 bool operator<=(const sorted_vector<K, bNoDuplicates,Pr,A>& x, 275 const sorted_vector<K, bNoDuplicates,Pr,A>& Y_) 276 {return !(Y_ < x); } 277 template<class K, bool bNoDuplicates,class Pr,class A> inline 278 bool operator>=(const sorted_vector<K, bNoDuplicates,Pr,A>& x, 279 const sorted_vector<K, bNoDuplicates,Pr,A>& Y_) 280 {return (!(x < Y_)); } 281 } 282 283 #endif 284