15 #ifndef ORDERED_VECTOR_H
16 #define ORDERED_VECTOR_H
17 #ifdef CPPPARSER // hack around this for interigate...
24 template<
class Key,
class Compare = less<
int>,
class Vector = pvector<Key> >
class ov_multiset
28 template<
class Key,
class Compare = less<
int>,
class Vector = pvector<Key> >
class ov_set
32 template<
class Key,
class Compare = less<
int>,
class Vector = pvector<Key> >
class ordered_vector
39 #include "pandabase.h"
59 #define KEY_TYPE key_type_0
60 #define VALUE_TYPE value_type_0
61 #define REFERENCE reference_0
62 #define CONST_REFERENCE const_reference_0
63 #define KEY_COMPARE key_compare_0
64 #define VALUE_COMPARE value_compare_0
65 #define ITERATOR iterator_0
66 #define CONST_ITERATOR const_iterator_0
67 #define REVERSE_ITERATOR reverse_iterator_0
68 #define CONST_REVERSE_ITERATOR const_reverse_iterator_0
69 #define DIFFERENCE_TYPE difference_type_0
70 #define SIZE_TYPE size_type_0
108 template<
class Key,
class Compare = less<Key>,
class Vector = pvector<Key> >
112 typedef Key KEY_TYPE;
113 typedef Key VALUE_TYPE;
114 typedef Key &REFERENCE;
115 typedef const Key &CONST_REFERENCE;
116 typedef Compare KEY_COMPARE;
117 typedef Compare VALUE_COMPARE;
122 typedef TYPENAME Vector::iterator ITERATOR;
123 typedef TYPENAME Vector::const_iterator CONST_ITERATOR;
124 typedef TYPENAME Vector::reverse_iterator REVERSE_ITERATOR;
125 typedef TYPENAME Vector::const_reverse_iterator CONST_REVERSE_ITERATOR;
127 typedef TYPENAME Vector::difference_type DIFFERENCE_TYPE;
128 typedef TYPENAME Vector::size_type SIZE_TYPE;
133 typedef KEY_TYPE key_type;
134 typedef VALUE_TYPE value_type;
135 typedef REFERENCE reference;
136 typedef CONST_REFERENCE const_reference;
137 typedef KEY_COMPARE key_compare;
138 typedef VALUE_COMPARE value_compare;
139 typedef ITERATOR iterator;
140 typedef CONST_ITERATOR const_iterator;
141 typedef REVERSE_ITERATOR reverse_iterator;
142 typedef CONST_REVERSE_ITERATOR const_reverse_iterator;
143 typedef DIFFERENCE_TYPE difference_type;
144 typedef SIZE_TYPE size_type;
150 INLINE ordered_vector(
const Compare &compare,
154 INLINE ~ordered_vector();
157 INLINE ITERATOR
begin();
158 INLINE ITERATOR
end();
159 INLINE REVERSE_ITERATOR
rbegin();
160 INLINE REVERSE_ITERATOR
rend();
162 INLINE CONST_ITERATOR
begin()
const;
163 INLINE CONST_ITERATOR
end()
const;
164 INLINE CONST_REVERSE_ITERATOR
rbegin()
const;
165 INLINE CONST_REVERSE_ITERATOR
rend()
const;
168 INLINE reference operator [] (SIZE_TYPE n);
169 INLINE const_reference operator [] (SIZE_TYPE n)
const;
172 INLINE SIZE_TYPE
size()
const;
174 INLINE
bool empty()
const;
180 INLINE
bool operator < (const ordered_vector<Key, Compare, Vector> &other)
const;
182 INLINE
bool operator <= (const ordered_vector<Key, Compare, Vector> &other)
const;
186 ITERATOR insert_unique(ITERATOR position,
const VALUE_TYPE &key);
187 ITERATOR insert_nonunique(ITERATOR position,
const VALUE_TYPE &key);
188 INLINE pair<ITERATOR, bool> insert_unique(
const VALUE_TYPE &key);
189 INLINE ITERATOR insert_nonunique(
const VALUE_TYPE &key);
193 INLINE ITERATOR erase(ITERATOR position);
194 INLINE SIZE_TYPE erase(
const KEY_TYPE &key);
195 INLINE
void erase(ITERATOR first, ITERATOR last);
199 INLINE ITERATOR find(
const KEY_TYPE &key);
200 INLINE CONST_ITERATOR find(
const KEY_TYPE &key)
const;
201 INLINE ITERATOR find_particular(
const KEY_TYPE &key);
202 INLINE CONST_ITERATOR find_particular(
const KEY_TYPE &key)
const;
203 INLINE SIZE_TYPE
count(
const KEY_TYPE &key)
const;
205 INLINE ITERATOR lower_bound(
const KEY_TYPE &key);
206 INLINE CONST_ITERATOR lower_bound(
const KEY_TYPE &key)
const;
207 INLINE ITERATOR upper_bound(
const KEY_TYPE &key);
208 INLINE CONST_ITERATOR upper_bound(
const KEY_TYPE &key)
const;
209 INLINE pair<ITERATOR, ITERATOR> equal_range(
const KEY_TYPE &key);
210 INLINE pair<CONST_ITERATOR, CONST_ITERATOR> equal_range(
const KEY_TYPE &key)
const;
214 INLINE
void reserve(SIZE_TYPE n);
217 bool verify_list_unique()
const;
218 bool verify_list_nonunique()
const;
220 INLINE
void push_back(
const VALUE_TYPE &key);
224 INLINE ITERATOR nci(CONST_ITERATOR i);
225 INLINE ITERATOR find_insert_position(ITERATOR first, ITERATOR last,
226 const KEY_TYPE &key);
227 ITERATOR r_find_insert_position(ITERATOR first, ITERATOR last,
228 const KEY_TYPE &key);
229 CONST_ITERATOR r_find(CONST_ITERATOR first, CONST_ITERATOR last,
230 CONST_ITERATOR not_found,
231 const KEY_TYPE &key)
const;
232 CONST_ITERATOR r_find_particular(CONST_ITERATOR first, CONST_ITERATOR last,
233 CONST_ITERATOR not_found,
234 const KEY_TYPE &key)
const;
235 SIZE_TYPE r_count(CONST_ITERATOR first, CONST_ITERATOR last,
236 const KEY_TYPE &key)
const;
237 CONST_ITERATOR r_lower_bound(CONST_ITERATOR first, CONST_ITERATOR last,
238 const KEY_TYPE &key)
const;
239 CONST_ITERATOR r_upper_bound(CONST_ITERATOR first, CONST_ITERATOR last,
240 const KEY_TYPE &key)
const;
241 pair<CONST_ITERATOR, CONST_ITERATOR>
242 r_equal_range(CONST_ITERATOR first, CONST_ITERATOR last,
243 const KEY_TYPE &key)
const;
247 class EquivalentTest {
253 INLINE EquivalentTest(
const Compare &compare) :
254 _compare(compare) { }
255 INLINE
bool operator () (
const KEY_TYPE &a,
const KEY_TYPE &b) {
256 nassertr(!_compare(b, a),
false);
257 return !_compare(a, b);
273 template<
class Key,
class Compare = less<Key>,
class Vector = pvector<Key> >
280 INLINE ov_set(
const Compare &compare,
285 INLINE ITERATOR insert(ITERATOR position,
const VALUE_TYPE &key0);
286 INLINE pair<ITERATOR, bool> insert(
const VALUE_TYPE &key0);
298 template<
class Key,
class Compare = less<Key>,
class Vector = pvector<Key> >
305 INLINE ov_multiset(
const Compare &compare,
310 INLINE ITERATOR insert(ITERATOR position,
const VALUE_TYPE &key);
311 INLINE ITERATOR insert(
const VALUE_TYPE &key);
317 #include "ordered_vector.I"
318 #include "ordered_vector.T"
319 #endif // cppparser ..
This template class presents an interface similar to the STL set or multiset (and ov_set and ov_multi...
bool verify_list() const
Maps to verify_list_unique().
void pop_back()
Removes the last element at the end of the vector.
bool operator==(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if the two ordered vectors are memberwise equivalent, false otherwise.
bool empty() const
Returns true if the ordered vector is empty, false otherwise.
bool operator!=(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if the two ordered vectors are not memberwise equivalent, false if they are...
void sort_unique()
Ensures that the vector is properly sorted after a potentially damaging operation.
void clear()
Removes all elements from the ordered vector.
void sort_nonunique()
Ensures that the vector is properly sorted after a potentially damaging operation.
size_type_0 count(const key_type_0 &key) const
Returns the number of elements that sort equivalent to the key that are in the vector.
iterator_0 begin()
Returns the iterator that marks the first element in the ordered vector.
bool operator>(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically after the other one, false otherwise...
iterator_0 end()
Returns the iterator that marks the end of the ordered vector.
void reserve(size_type_0 n)
Informs the vector of a planned change in size; ensures that the capacity of the vector is greater th...
size_type_0 max_size() const
Returns the maximum number of elements that can possibly be stored in an ordered vector.
A specialization of ordered_vector that emulates a standard STL set: one copy of each element is allo...
void swap(ordered_vector< Key, Compare, Vector > &other)
Exchanges the contents of this vector and the other vector, in constant time (e.g., with a pointer swap).
bool operator>=(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically after the other one or is equivalent...
iterator_0 insert_unverified(iterator_0 position, const value_type_0 &key)
Inserts the indicated key into the ordered vector at the indicated place.
bool verify_list() const
Maps to verify_list_nonunique().
void sort()
Maps to sort_nonunique().
void sort()
Maps to sort_unique().
reverse_iterator_0 rbegin()
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
A specialization of ordered_vector that emulates a standard STL set: many copies of each element are ...
void push_back(const value_type_0 &key)
Adds the new element to the end of the vector without regard for proper sorting.
reverse_iterator_0 rend()
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order...
size_type_0 size() const
Returns the number of elements in the ordered vector.
TypeHandle is the identifier used to differentiate C++ class types.