| // This file is part of the ustl library, an STL implementation. |
| // |
| // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net> |
| // This file is free software, distributed under the MIT License. |
| // |
| // uset.h |
| // |
| |
| #ifndef USET_H_45543F516E02A87A3FCEA5024052A6F5 |
| #define USET_H_45543F516E02A87A3FCEA5024052A6F5 |
| |
| #include "uassert.h" |
| #include "uvector.h" |
| |
| namespace ustl { |
| |
| /// \class set uset.h ustl.h |
| /// \ingroup Sequences |
| /// |
| /// \brief Unique sorted container. Sorted vector with all values unique. |
| /// |
| template <typename T> |
| class set : public vector<T> { |
| public: |
| typedef const set<T>& rcself_t; |
| typedef vector<T> base_class; |
| typedef typename base_class::value_type key_type; |
| typedef typename base_class::value_type data_type; |
| typedef typename base_class::value_type value_type; |
| typedef typename base_class::size_type size_type; |
| typedef typename base_class::pointer pointer; |
| typedef typename base_class::const_pointer const_pointer; |
| typedef typename base_class::reference reference; |
| typedef typename base_class::const_reference const_reference; |
| typedef typename base_class::const_iterator const_iterator; |
| typedef typename base_class::iterator iterator; |
| typedef typename base_class::reverse_iterator reverse_iterator; |
| typedef typename base_class::const_reverse_iterator const_reverse_iterator; |
| public: |
| inline set (void) : vector<T> () { } |
| explicit inline set (size_type n) : vector<T> (n) { } |
| inline set (rcself_t v) : vector<T> (v) { } |
| inline set (const_iterator i1, const_iterator i2) : vector<T> () { insert (i1, i2); } |
| inline rcself_t operator= (rcself_t v) { base_class::operator= (v); return (*this); } |
| inline size_type size (void) const { return (base_class::size()); } |
| inline iterator begin (void) { return (base_class::begin()); } |
| inline const_iterator begin (void) const { return (base_class::begin()); } |
| inline iterator end (void) { return (base_class::end()); } |
| inline const_iterator end (void) const { return (base_class::end()); } |
| inline void assign (const_iterator i1, const_iterator i2) { clear(); insert (i1, i2); } |
| inline void push_back (const_reference v) { insert (v); } |
| inline const_iterator find (const_reference v) const { return (binary_search (begin(), end(), v)); } |
| inline iterator find (const_reference v) { return (const_cast<iterator>(const_cast<rcself_t>(*this).find (v))); } |
| iterator insert (const_reference v); |
| inline void insert (const_iterator i1, const_iterator i2); |
| inline void erase (const_reference v); |
| inline iterator erase (iterator ep) { return (base_class::erase (ep)); } |
| inline iterator erase (iterator ep1, iterator ep2) { return (base_class::erase (ep1, ep2)); } |
| inline void clear (void) { base_class::clear(); } |
| }; |
| |
| /// Inserts \p v into the container, maintaining the sort order. |
| template <typename T> |
| typename set<T>::iterator set<T>::insert (const_reference v) |
| { |
| iterator ip = lower_bound (begin(), end(), v); |
| if (ip == end() || v < *ip) |
| ip = base_class::insert (ip, v); |
| else |
| *ip = v; |
| return (ip); |
| } |
| |
| /// Inserts the contents of range [i1,i2) |
| template <typename T> |
| void set<T>::insert (const_iterator i1, const_iterator i2) |
| { |
| assert (i1 <= i2); |
| reserve (size() + distance (i1, i2)); |
| for (; i1 < i2; ++i1) |
| push_back (*i1); |
| } |
| |
| /// Erases the element with value \p v. |
| template <typename T> |
| inline void set<T>::erase (const_reference v) |
| { |
| iterator ip = find (v); |
| if (ip != end()) |
| erase (ip); |
| } |
| |
| |
| } // namespace ustl |
| |
| #endif |
| |