39#ifndef VIGRA_RANDOM_ACCESS_SET_HXX
40#define VIGRA_RANDOM_ACCESS_SET_HXX
57template<
class Key,
class Compare=std::less<Key>,
class Alloc=std::allocator<Key> >
58class RandomAccessSet {
61 typedef std::vector<Key,Alloc> VectorType;
68 typedef Key ValueType;
70 typedef Key value_type;
72 typedef Compare key_compare;
74 typedef Compare value_compare;
76 typedef Alloc allocator_type;
78 typedef typename Alloc::const_reference const_reference;
80 typedef typename VectorType::iterator iterator;
82 typedef typename VectorType::const_iterator const_iterator;
84 typedef typename VectorType::size_type size_type;
86 typedef typename VectorType::difference_type difference_type;
88 typedef typename VectorType::const_pointer const_pointer;
90 typedef typename VectorType::const_reverse_iterator const_reverse_iterator;
94 RandomAccessSet(
const size_t,
const Compare& compare=Compare(),
const Alloc& alloc=Alloc());
95 RandomAccessSet(
const Compare& compare=Compare(),
const Alloc& alloc=Alloc());
96 template <
class InputIterator>
97 RandomAccessSet(InputIterator, InputIterator,
const Compare& compare =Compare(),
const Alloc & alloc=Alloc());
98 RandomAccessSet(
const RandomAccessSet&);
101 RandomAccessSet& operator=(
const RandomAccessSet &);
103 const value_type& operator[](
const size_type)
const;
105 const_iterator begin()
const;
106 const_iterator end()
const;
107 const_iterator rbegin()
const;
108 const_iterator rend()
const;
115 size_type size()
const;
116 size_type max_size()
const;
117 std::pair< const_iterator,bool> insert(
const value_type&);
118 template <
class InputIterator>
119 void insert(InputIterator, InputIterator);
120 const_iterator insert(const_iterator ,
const value_type&);
121 void erase(iterator position);
122 size_type erase(
const key_type& );
123 void erase( const_iterator, const_iterator);
124 void swap(RandomAccessSet&);
126 key_compare key_comp()
const;
127 value_compare value_comp()
const;
128 const_iterator find(
const key_type&)
const;
129 iterator find(
const key_type&);
130 size_type count(
const key_type&)
const;
131 const_iterator lower_bound(
const key_type&)
const;
132 const_iterator upper_bound(
const key_type&)
const;
133 std::pair<const_iterator,const_iterator> equal_range(
const key_type&)
const;
134 iterator lower_bound(
const key_type&) ;
135 iterator upper_bound(
const key_type&) ;
136 std::pair<iterator,iterator> equal_range(
const key_type&) ;
137 allocator_type get_allocator()
const;
140 void reserve(
const size_t size){
141 vector_.reserve(size);
143 size_t capacity()
const{
144 return vector_.capacity();
148 void assignFromSet(
const SET & set){
149 vector_.assign(set.begin(),set.end());
153 std::vector<Key> vector_;
161template<
class Key,
class Compare,
class Alloc>
163RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
165 const size_t reserveSize,
166 const Compare& compare,
171 vector_.reserve(reserveSize);
177template<
class Key,
class Compare,
class Alloc>
178inline const typename RandomAccessSet<Key,Compare,Alloc>::value_type&
179RandomAccessSet<Key,Compare,Alloc>::operator[]
181 const typename RandomAccessSet<Key,Compare,Alloc>::size_type index
184 return vector_[index];
190template<
class Key,
class Compare,
class Alloc>
192RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
194 const Compare& compare,
205template<
class Key,
class Compare,
class Alloc>
206template <
class InputIterator>
208RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
210 InputIterator beginInput,
211 InputIterator endInput,
212 const Compare& compare,
218 while(beginInput!=endInput) {
219 this->insert(*beginInput);
226template<
class Key,
class Compare,
class Alloc>
228RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
230 const RandomAccessSet<Key,Compare,Alloc>& src
232: vector_(src.vector_),
233 compare_(src.compare_) {
238template<
class Key,
class Compare,
class Alloc>
239inline RandomAccessSet<Key,Compare,Alloc>&
240RandomAccessSet<Key,Compare,Alloc>::operator=
242 const RandomAccessSet<Key,Compare,Alloc> & src
247 compare_=src.compare_;
254template<
class Key,
class Compare,
class Alloc>
255inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
256RandomAccessSet<Key,Compare,Alloc>::begin()
const
258 return vector_.begin();
263template<
class Key,
class Compare,
class Alloc>
264inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
265RandomAccessSet<Key,Compare,Alloc>::end()
const
267 return vector_.end();
271template<
class Key,
class Compare,
class Alloc>
272inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
273RandomAccessSet<Key,Compare,Alloc>::rbegin()
const
275 return vector_.rbegin();
280template<
class Key,
class Compare,
class Alloc>
281inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
282RandomAccessSet<Key,Compare,Alloc>::rend()
const
284 return vector_.rend();
289template<
class Key,
class Compare,
class Alloc>
290inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
291RandomAccessSet<Key,Compare,Alloc>::begin()
293 return vector_.begin();
298template<
class Key,
class Compare,
class Alloc>
299inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
300RandomAccessSet<Key,Compare,Alloc>::end()
302 return vector_.end();
307template<
class Key,
class Compare,
class Alloc>
308inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
309RandomAccessSet<Key,Compare,Alloc>::rbegin()
311 return vector_.rbegin();
316template<
class Key,
class Compare,
class Alloc>
317inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
318RandomAccessSet<Key,Compare,Alloc>::rend()
320 return vector_.rend();
325template<
class Key,
class Compare,
class Alloc>
327RandomAccessSet<Key,Compare,Alloc>::empty()
const
329 return vector_.empty();
334template<
class Key,
class Compare,
class Alloc>
335inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
336RandomAccessSet<Key,Compare,Alloc>::size()
const
338 return vector_.size();
343template<
class Key,
class Compare,
class Alloc>
344inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
345RandomAccessSet<Key,Compare,Alloc>::max_size()
const
347 return vector_.max_size();
357template<
class Key,
class Compare,
class Alloc>
358inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::const_iterator,
bool>
359RandomAccessSet<Key,Compare,Alloc>::insert
361 const typename RandomAccessSet<Key,Compare,Alloc>::value_type& value
364 iterator i(lower_bound(
static_cast<Key
>(value)));
365 if(i == end() || compare_(
static_cast<Key
>(value), *i)) {
366 i = vector_.insert(i,
static_cast<Key
>(value));
369 return std::make_pair(i, !found);
376template<
class Key,
class Compare,
class Alloc>
377template <
class InputIterator>
379RandomAccessSet<Key,Compare,Alloc>::insert
386 this->insert(*first);
395template<
class Key,
class Compare,
class Alloc>
396inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
397RandomAccessSet<Key,Compare,Alloc>::insert
399 typename RandomAccessSet<Key,Compare,Alloc>::const_iterator position,
400 const typename RandomAccessSet<Key,Compare,Alloc>::value_type& value
403 if((position == begin() || this->
operator()(*(position-1),value))
404 && (position == end() || this->
operator()(value, *position))) {
405 return vector_.insert(position, value);
407 return insert(value).first;
412template<
class Key,
class Compare,
class Alloc>
414RandomAccessSet<Key,Compare,Alloc>::erase
416 typename RandomAccessSet<Key,Compare,Alloc>::iterator position
419 vector_.erase(position);
424template<
class Key,
class Compare,
class Alloc>
425inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
426RandomAccessSet<Key,Compare,Alloc>::erase
428 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& x
443template<
class Key,
class Compare,
class Alloc>
445RandomAccessSet<Key,Compare,Alloc>::erase
447 const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator first,
448 const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator last
451 vector_.erase(first,last);
456template<
class Key,
class Compare,
class Alloc>
458RandomAccessSet<Key,Compare,Alloc>::swap
460 RandomAccessSet<Key,Compare,Alloc>& rhs
463 vector_.swap(rhs.vector_);
464 std::swap(compare_, rhs.compare_);
470template<
class Key,
class Compare,
class Alloc>
472RandomAccessSet<Key,Compare,Alloc>::clear()
479template<
class Key,
class Compare,
class Alloc>
480inline typename RandomAccessSet<Key,Compare,Alloc>::key_compare
481RandomAccessSet<Key,Compare,Alloc>::key_comp()
const
488template<
class Key,
class Compare,
class Alloc>
489inline typename RandomAccessSet<Key,Compare,Alloc>::value_compare
490RandomAccessSet<Key,Compare,Alloc>::value_comp()
const
499template<
class Key,
class Compare,
class Alloc>
500inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
501RandomAccessSet<Key,Compare,Alloc>::find
503 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
506 const_iterator i(lower_bound(value));
507 if (i != end() && compare_(value, *i))
518template<
class Key,
class Compare,
class Alloc>
519inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
520RandomAccessSet<Key,Compare,Alloc>::find
522 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
525 iterator i(lower_bound(value));
526 if (i != end() && compare_(value, *i))
536template<
class Key,
class Compare,
class Alloc>
537inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
538RandomAccessSet<Key,Compare,Alloc>::count
540 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
543 return find(value) != end() ? 1 : 0;
549template<
class Key,
class Compare,
class Alloc>
550inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
551RandomAccessSet<Key,Compare,Alloc>::lower_bound
553 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
556 return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
562template<
class Key,
class Compare,
class Alloc>
563inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
564RandomAccessSet<Key,Compare,Alloc>::lower_bound
566 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
569 return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
575template<
class Key,
class Compare,
class Alloc>
576inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
577RandomAccessSet<Key,Compare,Alloc>::upper_bound
579 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
582 return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
588template<
class Key,
class Compare,
class Alloc>
589inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
590RandomAccessSet<Key,Compare,Alloc>::upper_bound
592 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
595 return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
601template<
class Key,
class Compare,
class Alloc>
602inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::const_iterator,
typename RandomAccessSet<Key,Compare,Alloc>::const_iterator>
603RandomAccessSet<Key,Compare,Alloc>::equal_range
605 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
608 return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
614template<
class Key,
class Compare,
class Alloc>
615inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::iterator,
typename RandomAccessSet<Key,Compare,Alloc>::iterator>
616RandomAccessSet<Key,Compare,Alloc>::equal_range
618 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
621 return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
625template<
class Key,
class Compare,
class Alloc>
626inline typename RandomAccessSet<Key,Compare,Alloc>::allocator_type
627RandomAccessSet<Key,Compare,Alloc>::get_allocator()
const
629 return vector_.get_allocator();