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