uset.h

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6 // uset.h
   7 //
   8
   9 #ifndef USET_H_45543F516E02A87A3FCEA5024052A6F5
  10 #define USET_H_45543F516E02A87A3FCEA5024052A6F5
  11
  12 #include "uvector.h"
  13
  14 namespace ustl {
  15
  16 /// \class set uset.h ustl.h
  17 /// \ingroup Sequences
  18 ///
  19 /// \brief Unique sorted container. Sorted vector with all values unique.
  20 ///
  21 template <typename T>
  22 class set : public vector<T> {
  23 public:
  24     typedef const set<T>&                       rcself_t;
  25     typedef vector<T>                           base_class;
  26     typedef typename base_class::value_type             key_type;
  27     typedef typename base_class::value_type             data_type;
  28     typedef typename base_class::value_type             value_type;
  29     typedef typename base_class::size_type              size_type;
  30     typedef typename base_class::pointer                        pointer;
  31     typedef typename base_class::const_pointer          const_pointer;
  32     typedef typename base_class::reference              reference;
  33     typedef typename base_class::const_reference                const_reference;
  34     typedef typename base_class::const_iterator         const_iterator;
  35     typedef typename base_class::iterator               iterator;
  36     typedef typename base_class::reverse_iterator       reverse_iterator;
  37     typedef typename base_class::const_reverse_iterator const_reverse_iterator;
  38 public:
  39     inline                      set (void)              : vector<T> () { }
  40     explicit inline             set (size_type n)       : vector<T> (n) { }
  41     inline                      set (rcself_t v)        : vector<T> (v) { }
  42     inline                      set (const_iterator i1, const_iterator i2) : vector<T> () { insert (i1, i2); }
  43     inline rcself_t             operator= (rcself_t v)  { base_class::operator= (v); return (*this); }
  44     inline size_type            size (void) const       { return (base_class::size()); }
  45     inline iterator             begin (void)            { return (base_class::begin()); }
  46     inline const_iterator       begin (void) const      { return (base_class::begin()); }
  47     inline iterator             end (void)              { return (base_class::end()); }
  48     inline const_iterator       end (void) const        { return (base_class::end()); }
  49     inline void                 assign (const_iterator i1, const_iterator i2)   { clear(); insert (i1, i2); }
  50     inline void                 push_back (const_reference v)   { insert (v); }
  51     inline const_iterator       find (const_reference v) const  { return (binary_search (begin(), end(), v)); }
  52     inline iterator             find (const_reference v)        { return (const_cast<iterator>(const_cast<rcself_t>(*this).find (v))); }
  53     iterator                    insert (const_reference v);
  54     inline void                 insert (const_iterator i1, const_iterator i2);
  55     inline void                 erase (const_reference v);
  56     inline iterator             erase (iterator ep)     { return (base_class::erase (ep)); }
  57     inline iterator             erase (iterator ep1, iterator ep2) { return (base_class::erase (ep1, ep2)); }
  58     inline void                 clear (void)            { base_class::clear(); }
  59 };
  60
  61 /// Inserts \p v into the container, maintaining the sort order.
  62 template <typename T>
  63 typename set<T>::iterator set<T>::insert (const_reference v)
  64 {
  65     iterator ip = lower_bound (begin(), end(), v);
  66     if (ip == end() || v < *ip)
  67         ip = base_class::insert (ip, v);
  68     else
  69         *ip = v;
  70     return (ip);
  71 }
  72
  73 /// Inserts the contents of range [i1,i2)
  74 template <typename T>
  75 void set<T>::insert (const_iterator i1, const_iterator i2)
  76 {
  77     assert (i1 <= i2);
  78     reserve (size() + distance (i1, i2));
  79     for (; i1 < i2; ++i1)
  80         push_back (*i1);
  81 }
  82
  83 /// Erases the element with value \p v.
  84 template <typename T>
  85 inline void set<T>::erase (const_reference v)
  86 {
  87     iterator ip = find (v);
  88     if (ip != end())
  89         erase (ip);
  90 }
  91
  92
  93 } // namespace ustl
  94
  95 #endif
  96