blocxx
SortedVectorSet.hpp
Go to the documentation of this file.
1/*******************************************************************************
2* Copyright (C) 2005, Vintela, Inc. All rights reserved.
3* Copyright (C) 2006, Novell, Inc. All rights reserved.
4*
5* Redistribution and use in source and binary forms, with or without
6* modification, are permitted provided that the following conditions are met:
7*
8* * Redistributions of source code must retain the above copyright notice,
9* this list of conditions and the following disclaimer.
10* * Redistributions in binary form must reproduce the above copyright
11* notice, this list of conditions and the following disclaimer in the
12* documentation and/or other materials provided with the distribution.
13* * Neither the name of
14* Vintela, Inc.,
15* nor Novell, Inc.,
16* nor the names of its contributors or employees may be used to
17* endorse or promote products derived from this software without
18* specific prior written permission.
19*
20* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
24* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30* POSSIBILITY OF SUCH DAMAGE.
31*******************************************************************************/
32
33
37
38#ifndef BLOCXX_SORTED_VECTOR_SET_HPP_
39#define BLOCXX_SORTED_VECTOR_SET_HPP_
40#include "blocxx/BLOCXX_config.h"
42#include "blocxx/vector.hpp"
43#include <utility> // for std::pair
44#include <functional> // for std::less
45#include <algorithm>
46
47namespace BLOCXX_NAMESPACE
48{
49
50template<class T, class Compare >
51class SortedVectorSet;
52
53template<class T, class Compare>
54inline bool operator==(const SortedVectorSet<T, Compare>& x,
56
57template<class T, class Compare>
58inline bool operator<(const SortedVectorSet<T, Compare>& x,
60
61template<class T, class Compare = std::less<T> >
63{
64 typedef std::vector<T> container_t;
65#ifdef BLOCXX_WIN32
66#pragma warning (push)
67#pragma warning (disable: 4251)
68#endif
70#ifdef BLOCXX_WIN32
71#pragma warning (pop)
72#endif
73public:
74 typedef T key_type;
75 typedef T data_type;
76 typedef T value_type;
77 typedef Compare key_compare;
78 typedef Compare value_compare;
79 typedef typename container_t::pointer pointer;
80 typedef typename container_t::const_pointer const_pointer;
81 typedef typename container_t::reference reference;
82 typedef typename container_t::const_reference const_reference;
83 typedef typename container_t::iterator iterator;
84 typedef typename container_t::const_iterator const_iterator;
85 typedef typename container_t::reverse_iterator reverse_iterator;
86 typedef typename container_t::const_reverse_iterator const_reverse_iterator;
87 typedef typename container_t::size_type size_type;
88 typedef typename container_t::difference_type difference_type;
90 explicit SortedVectorSet(container_t* toWrap) : m_impl(toWrap)
91 {
92 std::sort(m_impl->begin(), m_impl->end(), Compare());
93 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end());
94 }
95 template <class InputIterator>
96 SortedVectorSet(InputIterator first, InputIterator last) :
97 m_impl(new container_t(first, last))
98 {
99 std::sort(m_impl->begin(), m_impl->end(), Compare());
100 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end());
101 }
102 const_iterator begin() const { return m_impl->begin(); }
103 const_iterator end() const { return m_impl->end(); }
104 const_reverse_iterator rbegin() const { return m_impl->rbegin(); }
105 const_reverse_iterator rend() const { return m_impl->rend(); }
106 bool empty() const { return m_impl->empty(); }
107 size_type size() const { return m_impl->size(); }
108 size_type max_size() const { return m_impl->max_size(); }
110 {
111 m_impl.swap(x.m_impl);
112 }
113 std::pair<iterator, bool> insert(const value_type& x)
114 {
115 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
116 if (i != m_impl->end() && equivalent(*i, x))
117 {
118 return std::pair<iterator, bool>(i, false);
119 }
120 else
121 {
122 return std::pair<iterator, bool>(m_impl->insert(i, x), true);
123 }
124 }
126 {
127 return insert(x).first;
128 }
129 template <class InputIterator>
130 void insert(InputIterator first, InputIterator last)
131 {
132 m_impl->insert(m_impl->end(), first, last);
133 std::sort(m_impl->begin(), m_impl->end(), Compare());
134 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end());
135 }
137 {
138 return m_impl->erase(position);
139 }
141 {
142 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
143 if (i != m_impl->end() && equivalent(*i, x))
144 {
145 m_impl->erase(i);
146 return 1;
147 }
148 else
149 {
150 return 0;
151 }
152 }
154 {
155 return m_impl->erase(first, last);
156 }
157 void clear()
158 {
159 m_impl->clear();
160 }
162 {
163 iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
164 if (pos != m_impl->end() && equivalent(*pos, x))
165 {
166 return pos;
167 }
168 else
169 {
170 return m_impl->end();
171 }
172 }
174 {
175 const_iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
176 if (pos != m_impl->end() && equivalent(*pos, x))
177 {
178 return pos;
179 }
180 else
181 {
182 return m_impl->end();
183 }
184 }
185 size_type count(const key_type& x) const
186 {
187 if (std::binary_search(m_impl->begin(), m_impl->end(), x, Compare()))
188 {
189 return 1;
190 }
191 else
192 {
193 return 0;
194 }
195 }
197 {
198 return std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
199 }
201 {
202 return std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
203 }
205 {
206 return std::upper_bound(m_impl->begin(), m_impl->end(), x, Compare());
207 }
209 {
210 return std::upper_bound(m_impl->begin(), m_impl->end(), x, Compare());
211 }
212
213 std::pair<iterator, iterator>
215 {
216 return std::equal_range(m_impl->begin(), m_impl->end(), x, Compare());
217 }
218
219 std::pair<const_iterator, const_iterator>
220 equal_range(const key_type& x) const
221 {
222 return std::equal_range(m_impl->begin(), m_impl->end(), x, Compare());
223 }
224
227 friend bool operator< <>(const SortedVectorSet<T, Compare>& x,
229
230private:
231 static bool equivalent(const key_type& x, const key_type& y)
232 {
233 // Strict weak ordering: Two objects x and y are equivalent if both f(x, y) and f(y, x) are false.
234 return (!Compare()(x, y) && !Compare()(y, x));
235 }
236};
237template<class T, class Compare>
240{
241 return *x.m_impl == *y.m_impl;
242}
243template<class T, class Compare>
246{
247 return *x.m_impl < *y.m_impl;
248}
249template <class T, class Compare>
252{
253 x.swap(y);
254}
255
256} // end namespace BLOCXX_NAMESPACE
257
258#endif
COWReference A smart pointer that uses non-intrusive reference counting.
iterator erase(iterator first, iterator last)
container_t::const_reverse_iterator const_reverse_iterator
iterator find(const key_type &x)
iterator upper_bound(const key_type &x)
const_reverse_iterator rend() const
container_t::reverse_iterator reverse_iterator
size_type erase(const key_type &x)
COWReference< container_t > m_impl
const_iterator find(const key_type &x) const
static bool equivalent(const key_type &x, const key_type &y)
size_type count(const key_type &x) const
const_iterator upper_bound(const key_type &x) const
container_t::const_iterator const_iterator
friend bool operator==(const SortedVectorSet< T, Compare > &x, const SortedVectorSet< T, Compare > &y)
container_t::const_reference const_reference
std::pair< iterator, iterator > equal_range(const key_type &x)
iterator erase(iterator position)
const_reverse_iterator rbegin() const
iterator lower_bound(const key_type &x)
SortedVectorSet(InputIterator first, InputIterator last)
std::pair< iterator, bool > insert(const value_type &x)
container_t::difference_type difference_type
iterator insert(iterator, const value_type &x)
container_t::const_pointer const_pointer
const_iterator lower_bound(const key_type &x) const
void swap(SortedVectorSet< T, Compare > &x)
std::pair< const_iterator, const_iterator > equal_range(const key_type &x) const
void insert(InputIterator first, InputIterator last)
Taken from RFC 1321.
bool operator<(const Array< T > &x, const Array< T > &y)
bool operator==(const Array< T > &x, const Array< T > &y)
void swap(Array< T > &x, Array< T > &y)