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;
76 typedef Alloc allocator_type;
78 typedef const Key& const_reference;
80 typedef typename VectorType::iterator
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;
96 template <
class InputIterator>
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>
122 size_type erase(
const key_type& );
130 size_type count(
const key_type&)
const;
133 std::pair<const_iterator,const_iterator>
equal_range(
const key_type&)
const;
136 std::pair<iterator,iterator>
equal_range(
const key_type&) ;
140 void reserve(
const size_t size){
143 size_t capacity()
const{
149 vector_.assign(set.begin(),set.end());
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);
397template<
class Key,
class Compare,
class Alloc>
398inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
399RandomAccessSet<Key,Compare,Alloc>::insert
401 typename RandomAccessSet<Key,Compare,Alloc>::const_iterator position,
402 const typename RandomAccessSet<Key,Compare,Alloc>::value_type& value
405 if((position == begin() || value_comp()(*(position-1),value))
406 && (position == end() || value_comp()(value, *position))) {
407 return vector_.insert(position, value);
409 return insert(value).first;
414template<
class Key,
class Compare,
class Alloc>
416RandomAccessSet<Key,Compare,Alloc>::erase
418 typename RandomAccessSet<Key,Compare,Alloc>::iterator position
421 vector_.erase(position);
426template<
class Key,
class Compare,
class Alloc>
427inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
428RandomAccessSet<Key,Compare,Alloc>::erase
430 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& x
445template<
class Key,
class Compare,
class Alloc>
447RandomAccessSet<Key,Compare,Alloc>::erase
449 const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator first,
450 const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator last
453 vector_.erase(first,last);
458template<
class Key,
class Compare,
class Alloc>
460RandomAccessSet<Key,Compare,Alloc>::swap
462 RandomAccessSet<Key,Compare,Alloc>& rhs
465 vector_.swap(rhs.vector_);
466 std::swap(compare_, rhs.compare_);
472template<
class Key,
class Compare,
class Alloc>
474RandomAccessSet<Key,Compare,Alloc>::clear()
481template<
class Key,
class Compare,
class Alloc>
482inline typename RandomAccessSet<Key,Compare,Alloc>::key_compare
483RandomAccessSet<Key,Compare,Alloc>::key_comp()
const
490template<
class Key,
class Compare,
class Alloc>
491inline typename RandomAccessSet<Key,Compare,Alloc>::value_compare
492RandomAccessSet<Key,Compare,Alloc>::value_comp()
const
501template<
class Key,
class Compare,
class Alloc>
502inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
503RandomAccessSet<Key,Compare,Alloc>::find
505 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
508 const_iterator i(lower_bound(value));
509 if (i != end() && compare_(value, *i))
520template<
class Key,
class Compare,
class Alloc>
521inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
522RandomAccessSet<Key,Compare,Alloc>::find
524 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
527 iterator i(lower_bound(value));
528 if (i != end() && compare_(value, *i))
538template<
class Key,
class Compare,
class Alloc>
539inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
540RandomAccessSet<Key,Compare,Alloc>::count
542 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
545 return find(value) != end() ? 1 : 0;
551template<
class Key,
class Compare,
class Alloc>
552inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
553RandomAccessSet<Key,Compare,Alloc>::lower_bound
555 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
558 return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
564template<
class Key,
class Compare,
class Alloc>
565inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
566RandomAccessSet<Key,Compare,Alloc>::lower_bound
568 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
571 return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
577template<
class Key,
class Compare,
class Alloc>
578inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
579RandomAccessSet<Key,Compare,Alloc>::upper_bound
581 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
584 return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
590template<
class Key,
class Compare,
class Alloc>
591inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
592RandomAccessSet<Key,Compare,Alloc>::upper_bound
594 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
597 return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
603template<
class Key,
class Compare,
class Alloc>
604inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::const_iterator,
typename RandomAccessSet<Key,Compare,Alloc>::const_iterator>
605RandomAccessSet<Key,Compare,Alloc>::equal_range
607 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
610 return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
616template<
class Key,
class Compare,
class Alloc>
617inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::iterator,
typename RandomAccessSet<Key,Compare,Alloc>::iterator>
618RandomAccessSet<Key,Compare,Alloc>::equal_range
620 const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
623 return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
627template<
class Key,
class Compare,
class Alloc>
628inline typename RandomAccessSet<Key,Compare,Alloc>::allocator_type
629RandomAccessSet<Key,Compare,Alloc>::get_allocator()
const
631 return vector_.get_allocator();
RGBValue()
Definition rgbvalue.hxx:209
Base::iterator iterator
Definition rgbvalue.hxx:144
Base::value_type value_type
Definition rgbvalue.hxx:141
Base::const_iterator const_iterator
Definition rgbvalue.hxx:147
size_type size() const
Definition tinyvector.hxx:913
reference operator[](difference_type i)
Definition tinyvector.hxx:845
iterator end()
Definition tinyvector.hxx:864
iterator begin()
Definition tinyvector.hxx:861