Panda3D

Loading...
Searching...
No Matches
ordered_vector.I
Go to the documentation of this file.
1/**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file ordered_vector.I
10 * @author drose
11 * @date 2002-02-20
12 */
13
14/**
15 *
16 */
17 template<class Key, class Compare, class Vector>
18INLINE ordered_vector<Key, Compare, Vector>::
19 ordered_vector(TypeHandle type_handle) :
20 _compare(Compare()),
21 _vector(type_handle)
22{
23}
24
25/**
26 *
27 */
28 template<class Key, class Compare, class Vector>
29INLINE ordered_vector<Key, Compare, Vector>::
30 ordered_vector(const Compare &compare, TypeHandle type_handle) :
31 _compare(compare),
32 _vector(type_handle)
33{
34}
35
36/**
37 * Returns the iterator that marks the first element in the ordered vector.
38 */
39 template<class Key, class Compare, class Vector>
40INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
41 begin() {
42 return _vector.begin();
43}
44
45/**
46 * Returns the iterator that marks the end of the ordered vector.
47 */
48 template<class Key, class Compare, class Vector>
49INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
50 end() {
51 return _vector.end();
52}
53
54/**
55 * Returns the iterator that marks the first element in the ordered vector,
56 * when viewed in reverse order.
57 */
58 template<class Key, class Compare, class Vector>
59INLINE typename ordered_vector<Key, Compare, Vector>::REVERSE_ITERATOR ordered_vector<Key, Compare, Vector>::
60 rbegin() {
61 return _vector.rbegin();
62}
63
64/**
65 * Returns the iterator that marks the end of the ordered vector, when viewed
66 * in reverse order.
67 */
68 template<class Key, class Compare, class Vector>
69INLINE typename ordered_vector<Key, Compare, Vector>::REVERSE_ITERATOR ordered_vector<Key, Compare, Vector>::
70 rend() {
71 return _vector.rend();
72}
73
74/**
75 * Returns the iterator that marks the first element in the ordered vector.
76 */
77 template<class Key, class Compare, class Vector>
78INLINE typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR ordered_vector<Key, Compare, Vector>::
79 begin() const {
80 return _vector.begin();
81}
82
83/**
84 * Returns the iterator that marks the end of the ordered vector.
85 */
86 template<class Key, class Compare, class Vector>
87INLINE typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR ordered_vector<Key, Compare, Vector>::
88 end() const {
89 return _vector.end();
90}
91
92/**
93 * Returns the iterator that marks the first element in the ordered vector,
94 * when viewed in reverse order.
95 */
96 template<class Key, class Compare, class Vector>
97INLINE typename ordered_vector<Key, Compare, Vector>::CONST_REVERSE_ITERATOR ordered_vector<Key, Compare, Vector>::
98 rbegin() const {
99 return _vector.rbegin();
100}
101
102/**
103 * Returns the iterator that marks the end of the ordered vector, when viewed
104 * in reverse order.
105 */
106 template<class Key, class Compare, class Vector>
107INLINE typename ordered_vector<Key, Compare, Vector>::CONST_REVERSE_ITERATOR ordered_vector<Key, Compare, Vector>::
108 rend() const {
109 return _vector.rend();
110}
111
112/**
113 * Returns the iterator that marks the first element in the ordered vector.
114 */
115 template<class Key, class Compare, class Vector>
116INLINE typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR ordered_vector<Key, Compare, Vector>::
117 cbegin() const {
118 return _vector.begin();
119}
120
121/**
122 * Returns the iterator that marks the end of the ordered vector.
123 */
124 template<class Key, class Compare, class Vector>
125INLINE typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR ordered_vector<Key, Compare, Vector>::
126 cend() const {
127 return _vector.end();
128}
129
130/**
131 * Returns the iterator that marks the first element in the ordered vector,
132 * when viewed in reverse order.
133 */
134 template<class Key, class Compare, class Vector>
135INLINE typename ordered_vector<Key, Compare, Vector>::CONST_REVERSE_ITERATOR ordered_vector<Key, Compare, Vector>::
136 crbegin() const {
137 return _vector.rbegin();
138}
139
140/**
141 * Returns the iterator that marks the end of the ordered vector, when viewed
142 * in reverse order.
143 */
144 template<class Key, class Compare, class Vector>
145INLINE typename ordered_vector<Key, Compare, Vector>::CONST_REVERSE_ITERATOR ordered_vector<Key, Compare, Vector>::
146 crend() const {
147 return _vector.rend();
148}
149
150/**
151 * Returns the nth element.
152 */
153 template<class Key, class Compare, class Vector>
154INLINE typename ordered_vector<Key, Compare, Vector>::REFERENCE ordered_vector<Key, Compare, Vector>::
155operator [] (typename ordered_vector<Key, Compare, Vector>::SIZE_TYPE n) {
156 return _vector[n];
157}
158
159/**
160 * Returns the nth element.
161 */
162 template<class Key, class Compare, class Vector>
163INLINE typename ordered_vector<Key, Compare, Vector>::CONST_REFERENCE ordered_vector<Key, Compare, Vector>::
164operator [] (typename ordered_vector<Key, Compare, Vector>::SIZE_TYPE n) const {
165 return _vector[n];
166}
167
168/**
169 * Returns a reference to the first element.
170 */
171 template<class Key, class Compare, class Vector>
172INLINE typename ordered_vector<Key, Compare, Vector>::REFERENCE ordered_vector<Key, Compare, Vector>::
173 front() {
174#ifdef _DEBUG
175 assert(!_vector.empty());
176#endif
177 return _vector[0];
178}
179
180/**
181 * Returns a const reference to the first element.
182 */
183 template<class Key, class Compare, class Vector>
184INLINE typename ordered_vector<Key, Compare, Vector>::CONST_REFERENCE ordered_vector<Key, Compare, Vector>::
185 front() const {
186#ifdef _DEBUG
187 assert(!_vector.empty());
188#endif
189 return _vector[0];
190}
191
192/**
193 * Returns a reference to the first element.
194 */
195 template<class Key, class Compare, class Vector>
196INLINE typename ordered_vector<Key, Compare, Vector>::REFERENCE ordered_vector<Key, Compare, Vector>::
197 back() {
198#ifdef _DEBUG
199 assert(!_vector.empty());
200#endif
201 return _vector[_vector.size() - 1];
202}
203
204/**
205 * Returns a const reference to the last element.
206 */
207 template<class Key, class Compare, class Vector>
208INLINE typename ordered_vector<Key, Compare, Vector>::CONST_REFERENCE ordered_vector<Key, Compare, Vector>::
209 back() const {
210#ifdef _DEBUG
211 assert(!_vector.empty());
212#endif
213 return _vector[_vector.size() - 1];
214}
215
216/**
217 * Returns the number of elements in the ordered vector.
218 */
219 template<class Key, class Compare, class Vector>
220INLINE typename ordered_vector<Key, Compare, Vector>::SIZE_TYPE ordered_vector<Key, Compare, Vector>::
221 size() const {
222 return _vector.size();
223}
224
225/**
226 * Returns the maximum number of elements that can possibly be stored in an
227 * ordered vector.
228 */
229 template<class Key, class Compare, class Vector>
230INLINE typename ordered_vector<Key, Compare, Vector>::SIZE_TYPE ordered_vector<Key, Compare, Vector>::
231 max_size() const {
232 return _vector.max_size();
233}
234
235/**
236 * Returns true if the ordered vector is empty, false otherwise.
237 */
238 template<class Key, class Compare, class Vector>
239INLINE bool ordered_vector<Key, Compare, Vector>::
240 empty() const {
241 return _vector.empty();
242}
243
244/**
245 * Returns true if the two ordered vectors are memberwise equivalent, false
246 * otherwise.
247 */
248 template<class Key, class Compare, class Vector>
249INLINE bool ordered_vector<Key, Compare, Vector>::
250 operator == (const ordered_vector<Key, Compare, Vector> &other) const {
251 return _vector == other._vector;
252}
253
254/**
255 * Returns true if the two ordered vectors are not memberwise equivalent,
256 * false if they are.
257 */
258 template<class Key, class Compare, class Vector>
259INLINE bool ordered_vector<Key, Compare, Vector>::
260 operator != (const ordered_vector<Key, Compare, Vector> &other) const {
261 return _vector != other._vector;
262}
263
264/**
265 * Returns true if this ordered vector sorts lexicographically before the
266 * other one, false otherwise.
267 */
268 template<class Key, class Compare, class Vector>
269INLINE bool ordered_vector<Key, Compare, Vector>::
270 operator < (const ordered_vector<Key, Compare, Vector> &other) const {
271 return _vector < other._vector;
272}
273
274/**
275 * Returns true if this ordered vector sorts lexicographically after the other
276 * one, false otherwise.
277 */
278 template<class Key, class Compare, class Vector>
279INLINE bool ordered_vector<Key, Compare, Vector>::
280 operator > (const ordered_vector<Key, Compare, Vector> &other) const {
281 return _vector > other._vector;
282}
283
284/**
285 * Returns true if this ordered vector sorts lexicographically before the
286 * other one or is equivalent, false otherwise.
287 */
288 template<class Key, class Compare, class Vector>
289INLINE bool ordered_vector<Key, Compare, Vector>::
290 operator <= (const ordered_vector<Key, Compare, Vector> &other) const {
291 return _vector <= other._vector;
292}
293
294/**
295 * Returns true if this ordered vector sorts lexicographically after the other
296 * one or is equivalent, false otherwise.
297 */
298 template<class Key, class Compare, class Vector>
299INLINE bool ordered_vector<Key, Compare, Vector>::
300 operator >= (const ordered_vector<Key, Compare, Vector> &other) const {
301 return _vector >= other._vector;
302}
303
304
305/**
306 * Inserts the indicated key into the ordered vector, at the appropriate
307 * place. If there is already an element sorting equivalent to the key in the
308 * vector, the new key is not inserted.
309 *
310 * The return value is a pair, where the first component is the iterator
311 * referencing the new element (or the original element), and the second
312 * componet is true if the insert operation has taken place.
313 */
314 template<class Key, class Compare, class Vector>
315INLINE std::pair<typename ordered_vector<Key, Compare, Vector>::ITERATOR, bool> ordered_vector<Key, Compare, Vector>::
316insert_unique(const typename ordered_vector<Key, Compare, Vector>::VALUE_TYPE &key) {
317 TAU_PROFILE("ordered_vector::insert_unique(const value_type &)", " ", TAU_USER);
318 ITERATOR position = find_insert_position(begin(), end(), key);
319#ifdef NDEBUG
320 std::pair<ITERATOR, bool> bogus_result(end(), false);
321 nassertr(position >= begin() && position <= end(), bogus_result);
322#endif
323
324 // If there's already an equivalent key in the vector, it's at *(position -
325 // 1).
326 if (position != begin() && !_compare(*(position - 1), key)) {
327 std::pair<ITERATOR, bool> result(position - 1, false);
328 nassertr(!_compare(key, *(position - 1)), result);
329 return result;
330 }
331
332 ITERATOR result = _vector.insert(position, key);
333 return std::pair<ITERATOR, bool>(result, true);
334}
335
336/**
337 * Inserts the indicated key into the ordered vector, at the appropriate
338 * place. If there are already elements sorting equivalent to the key in the
339 * vector, the new value is inserted following them.
340 *
341 * The return value is the iterator referencing the new element.
342 */
343 template<class Key, class Compare, class Vector>
344INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
345 insert_nonunique(const typename ordered_vector<Key, Compare, Vector>::VALUE_TYPE &key) {
346 TAU_PROFILE("ordered_vector::insert_nonunique(const value_type &)", " ", TAU_USER);
347 ITERATOR position = find_insert_position(begin(), end(), key);
348 nassertr(position >= begin() && position <= end(), end());
349
350 ITERATOR result = _vector.insert(position, key);
351 return result;
352}
353
354
355/**
356 * Inserts the indicated key into the ordered vector at the indicated place.
357 * The user is trusted to have already verified that this is the correct
358 * sorting position; no checks are made.
359 */
360 template<class Key, class Compare, class Vector>
361INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
362 insert_unverified(typename ordered_vector<Key, Compare, Vector>::ITERATOR position,
363 const typename ordered_vector<Key, Compare, Vector>::VALUE_TYPE &key) {
364 TAU_PROFILE("ordered_vector::insert_unverified(iterator, const value_type &)", " ", TAU_USER);
365 ITERATOR result = _vector.insert(position, key);
366 return result;
367}
368
369/**
370 * Removes the element indicated by the given iterator, and returns the next
371 * sequential iterator.
372 */
373 template<class Key, class Compare, class Vector>
374INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
375 erase(typename ordered_vector<Key, Compare, Vector>::ITERATOR position) {
376 TAU_PROFILE("ordered_vector::erase(iterator)", " ", TAU_USER);
377 SIZE_TYPE count = position - begin();
378 _vector.erase(position);
379 return begin() + count;
380}
381
382/**
383 * Removes all elements matching the indicated key; returns the number of
384 * elements removed.
385 */
386 template<class Key, class Compare, class Vector>
387INLINE typename ordered_vector<Key, Compare, Vector>::SIZE_TYPE ordered_vector<Key, Compare, Vector>::
388 erase(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) {
389 TAU_PROFILE("ordered_vector::erase(const key_type &)", " ", TAU_USER);
390 std::pair<ITERATOR, ITERATOR> result = equal_range(key);
391 SIZE_TYPE count = result.second - result.first;
392 erase(result.first, result.second);
393 return count;
394}
395
396/**
397 * Removes all elements indicated by the given iterator range.
398 */
399 template<class Key, class Compare, class Vector>
400INLINE void ordered_vector<Key, Compare, Vector>::
401 erase(typename ordered_vector<Key, Compare, Vector>::ITERATOR first,
402 typename ordered_vector<Key, Compare, Vector>::ITERATOR last) {
403 TAU_PROFILE("ordered_vector::erase(iterator, iterator)", " ", TAU_USER);
404 _vector.erase(first, last);
405}
406
407/**
408 * Removes all elements from the ordered vector.
409 */
410 template<class Key, class Compare, class Vector>
411INLINE void ordered_vector<Key, Compare, Vector>::
412 clear() {
413 TAU_PROFILE("ordered_vector::clear()", " ", TAU_USER);
414 _vector.erase(_vector.begin(), _vector.end());
415}
416
417/**
418 * Searches for an element with the indicated key and returns its iterator if
419 * it is found, or end() if it is not. If there are multiple elements
420 * matching the key, the particular iterator returned is not defined.
421 */
422 template<class Key, class Compare, class Vector>
423INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
424 find(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) {
425 TAU_PROFILE("ordered_vector::find(const key_type &)", " ", TAU_USER);
426 return nci(r_find(begin(), end(), end(), key));
427}
428
429/**
430 * Searches for an element with the indicated key and returns its iterator if
431 * it is found, or end() if it is not. If there are multiple elements
432 * matching the key, the particular iterator returned is not defined.
433 */
434 template<class Key, class Compare, class Vector>
435INLINE typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR ordered_vector<Key, Compare, Vector>::
436 find(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) const {
437 TAU_PROFILE("ordered_vector::find(const key_type &)", " ", TAU_USER);
438 return r_find(begin(), end(), end(), key);
439}
440
441/**
442 * Searches for a particular element and returns its iterator if it is found,
443 * or end() if it is not.
444 *
445 * First, the Compare function is used to narrow down the range of elements
446 * the element might be located within; then the element is compared
447 * elementwise, via ==, until the exact matching element is found. If
448 * multiple matches exist within the vector, the particular iterator returned
449 * is not defined.
450 *
451 * The assumption is that == implies !Compare(a, b) and !Compare(b, a), but
452 * not necessarily the converse.
453 */
454 template<class Key, class Compare, class Vector>
455INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
456 find_particular(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) {
457 TAU_PROFILE("ordered_vector::find_particular(const key_type &)", " ", TAU_USER);
458 return nci(r_find_particular(begin(), end(), end(), key));
459}
460
461/**
462 * Searches for a particular element and returns its iterator if it is found,
463 * or end() if it is not.
464 *
465 * First, the Compare function is used to narrow down the range of elements
466 * the element might be located within; then the element is compared
467 * elementwise, via ==, until the exact matching element is found. If
468 * multiple matches exist within the vector, the particular iterator returned
469 * is not defined.
470 */
471 template<class Key, class Compare, class Vector>
472INLINE typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR ordered_vector<Key, Compare, Vector>::
473 find_particular(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) const {
474 TAU_PROFILE("ordered_vector::find_particular(const key_type &)", " ", TAU_USER);
475 return r_find_particular(begin(), end(), end(), key);
476}
477
478/**
479 * Returns the number of elements that sort equivalent to the key that are in
480 * the vector.
481 */
482 template<class Key, class Compare, class Vector>
483INLINE typename ordered_vector<Key, Compare, Vector>::SIZE_TYPE ordered_vector<Key, Compare, Vector>::
484 count(const key_type &key) const {
485 TAU_PROFILE("ordered_vector::count(const key_type &)", " ", TAU_USER);
486 return r_count(begin(), end(), key);
487}
488
489/**
490 * Returns the iterator for the first element not less than key, or end() if
491 * all elements are less than key.
492 */
493 template<class Key, class Compare, class Vector>
494INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
495 lower_bound(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) {
496 TAU_PROFILE("ordered_vector::lower_bound(const key_type &)", " ", TAU_USER);
497 return nci(r_lower_bound(begin(), end(), key));
498}
499
500/**
501 * Returns the iterator for the first element not less than key, or end() if
502 * all elements are less than key.
503 */
504 template<class Key, class Compare, class Vector>
505INLINE typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR ordered_vector<Key, Compare, Vector>::
506 lower_bound(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) const {
507 TAU_PROFILE("ordered_vector::lower_bound(const key_type &)", " ", TAU_USER);
508 return r_lower_bound(begin(), end(), key);
509}
510
511/**
512 * Returns the iterator for the first element greater than key, or end() if no
513 * element is greater than key.
514 */
515 template<class Key, class Compare, class Vector>
516INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
517 upper_bound(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) {
518 TAU_PROFILE("ordered_vector::upper_bound(const key_type &)", " ", TAU_USER);
519 return nci(r_upper_bound(begin(), end(), key));
520}
521
522/**
523 * Returns the iterator for the first element greater than key, or end() if no
524 * element is greater than key.
525 */
526 template<class Key, class Compare, class Vector>
527INLINE typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR ordered_vector<Key, Compare, Vector>::
528 upper_bound(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) const {
529 TAU_PROFILE("ordered_vector::upper_bound(const key_type &)", " ", TAU_USER);
530 return r_upper_bound(begin(), end(), key);
531}
532
533/**
534 * Returns the pair (lower_bound(key), upper_bound(key)).
535 */
536 template<class Key, class Compare, class Vector>
537INLINE std::pair<typename ordered_vector<Key, Compare, Vector>::ITERATOR, typename ordered_vector<Key, Compare, Vector>::ITERATOR> ordered_vector<Key, Compare, Vector>::
538 equal_range(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) {
539 TAU_PROFILE("ordered_vector::equal_range(const key_type &)", " ", TAU_USER);
540 std::pair<typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR, typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR> result;
541 result = r_equal_range(begin(), end(), key);
542 return std::pair<typename ordered_vector<Key, Compare, Vector>::ITERATOR, typename ordered_vector<Key, Compare, Vector>::ITERATOR>(nci(result.first), nci(result.second));
543}
544
545/**
546 * Returns the pair (lower_bound(key), upper_bound(key)).
547 */
548 template<class Key, class Compare, class Vector>
549INLINE std::pair<typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR, typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR> ordered_vector<Key, Compare, Vector>::
550 equal_range(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) const {
551 TAU_PROFILE("ordered_vector::equal_range(const key_type &)", " ", TAU_USER);
552 return r_equal_range(begin(), end(), key);
553}
554
555/**
556 * Exchanges the contents of this vector and the other vector, in constant
557 * time (e.g., with a pointer swap).
558 */
559 template<class Key, class Compare, class Vector>
560INLINE void ordered_vector<Key, Compare, Vector>::
561 swap(ordered_vector<Key, Compare, Vector> &copy) {
562 TAU_PROFILE("ordered_vector::swap(ordered_vector &)", " ", TAU_USER);
563 _vector.swap(copy._vector);
564}
565
566/**
567 * Informs the vector of a planned change in size; ensures that the capacity
568 * of the vector is greater than or equal to n.
569 */
570 template<class Key, class Compare, class Vector>
571INLINE void ordered_vector<Key, Compare, Vector>::
572 reserve(typename ordered_vector<Key, Compare, Vector>::SIZE_TYPE n) {
573 TAU_PROFILE("ordered_vector::reserve(size_type)", " ", TAU_USER);
574 _vector.reserve(n);
575}
576
577/**
578 * Ensures that the vector is properly sorted after a potentially damaging
579 * operation. This should not normally need to be called, unless the user has
580 * written to the vector using the non-const iterators or has called
581 * push_back().
582 *
583 * This flavor of sort also eliminates repeated elements.
584 */
585 template<class Key, class Compare, class Vector>
586INLINE void ordered_vector<Key, Compare, Vector>::
587 sort_unique() {
588 TAU_PROFILE("ordered_vector::sort_unique()", " ", TAU_USER);
589 sort(begin(), end(), _compare);
590 iterator new_end = unique(begin(), end(), EquivalentTest(_compare));
591 erase(new_end, end());
592}
593
594/**
595 * Ensures that the vector is properly sorted after a potentially damaging
596 * operation. This should not normally need to be called, unless the user has
597 * written to the vector using the non-const iterators or has called
598 * push_back().
599 */
600 template<class Key, class Compare, class Vector>
601INLINE void ordered_vector<Key, Compare, Vector>::
602 sort_nonunique() {
603 TAU_PROFILE("ordered_vector::sort_nonunique()", " ", TAU_USER);
604 std::stable_sort(begin(), end(), _compare);
605}
606
607/**
608 * Adds the new element to the end of the vector without regard for proper
609 * sorting. This is a bad idea to do except to populate the vector the first
610 * time; be sure to call sort() after you have added all the elements.
611 */
612 template<class Key, class Compare, class Vector>
613INLINE void ordered_vector<Key, Compare, Vector>::
614 push_back(const value_type &key) {
615 TAU_PROFILE("ordered_vector::push_back()", " ", TAU_USER);
616 _vector.push_back(key);
617}
618
619/**
620 * Adds the new element to the end of the vector without regard for proper
621 * sorting. This is a bad idea to do except to populate the vector the first
622 * time; be sure to call sort() after you have added all the elements.
623 */
624 template<class Key, class Compare, class Vector>
625INLINE void ordered_vector<Key, Compare, Vector>::
626 push_back(value_type &&key) {
627 TAU_PROFILE("ordered_vector::push_back()", " ", TAU_USER);
628 _vector.push_back(std::move(key));
629}
630
631/**
632 * Removes the last element at the end of the vector.
633 */
634 template<class Key, class Compare, class Vector>
635INLINE void ordered_vector<Key, Compare, Vector>::
636 pop_back() {
637 TAU_PROFILE("ordered_vector::pop_back()", " ", TAU_USER);
638 _vector.pop_back();
639}
640
641/**
642 * Resizes the vector to contain n elements. This should not be used except
643 * to populate the vector for the first time.
644 */
645 template<class Key, class Compare, class Vector>
646INLINE void ordered_vector<Key, Compare, Vector>::
647 resize(SIZE_TYPE n) {
648 TAU_PROFILE("ordered_vector::resize()", " ", TAU_USER);
649 _vector.resize(n);
650}
651
652/**
653 * Resizes the vector to contain n elements. This should not be used except
654 * to populate the vector for the first time.
655 */
656 template<class Key, class Compare, class Vector>
657INLINE void ordered_vector<Key, Compare, Vector>::
658 resize(SIZE_TYPE n, const VALUE_TYPE &value) {
659 TAU_PROFILE("ordered_vector::resize()", " ", TAU_USER);
660 _vector.resize(n, value);
661}
662
663/**
664 * I.e. "non-const iterator". This function is used to typecast a const
665 * iterator to a non-const iterator for easy definition of const vs. non-
666 * const flavors of some of these methods.
667 */
668 template<class Key, class Compare, class Vector>
669INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
670 nci(typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR i) {
671 return begin() + (i - begin());
672}
673
674/**
675 * Searches for the appropriate place in the ordered vector to insert the
676 * indicated key, and returns the corresponding iterator.
677 */
678 template<class Key, class Compare, class Vector>
679INLINE typename ordered_vector<Key, Compare, Vector>::ITERATOR ordered_vector<Key, Compare, Vector>::
680 find_insert_position(typename ordered_vector<Key, Compare, Vector>::ITERATOR first,
681 typename ordered_vector<Key, Compare, Vector>::ITERATOR last,
682 const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) {
683 ITERATOR result = r_find_insert_position(first, last, key);
684 return result;
685}
686
687/**
688 *
689 */
690 template<class Key, class Compare, class Vector>
691INLINE ov_set<Key, Compare, Vector>::
692 ov_set(TypeHandle type_handle) :
693 ordered_vector<Key, Compare, Vector>(type_handle)
694{
695}
696
697/**
698 *
699 */
700 template<class Key, class Compare, class Vector>
701INLINE ov_set<Key, Compare, Vector>::
702 ov_set(const Compare &compare, TypeHandle type_handle) :
703 ordered_vector<Key, Compare, Vector>(compare, type_handle)
704{
705}
706
707/**
708 * Maps to insert_unique().
709 */
710 template<class Key, class Compare, class Vector>
711 typename ov_set<Key, Compare, Vector>::ITERATOR ov_set<Key, Compare, Vector>::
712 insert(typename ov_set<Key, Compare, Vector>::ITERATOR position,
713 const typename ov_set<Key, Compare, Vector>::VALUE_TYPE &key) {
714 return ordered_vector<Key, Compare, Vector>::insert_unique(position, key);
715}
716
717/**
718 * Maps to insert_unique().
719 */
720 template<class Key, class Compare, class Vector>
721INLINE std::pair<typename ov_set<Key, Compare, Vector>::ITERATOR, bool> ov_set<Key, Compare, Vector>::
722 insert(const typename ov_set<Key, Compare, Vector>::VALUE_TYPE &key) {
723 return ordered_vector<Key, Compare, Vector>::insert_unique(key);
724}
725
726/**
727 * Maps to sort_unique().
728 */
729 template<class Key, class Compare, class Vector>
730INLINE void ov_set<Key, Compare, Vector>::
731 sort() {
732 ordered_vector<Key, Compare, Vector>::sort_unique();
733}
734
735/**
736 * Maps to verify_list_unique().
737 */
738 template<class Key, class Compare, class Vector>
739INLINE bool ov_set<Key, Compare, Vector>::
740 verify_list() const {
741 return ordered_vector<Key, Compare, Vector>::verify_list_unique();
742}
743
744/**
745 *
746 */
747 template<class Key, class Compare, class Vector>
748INLINE ov_multiset<Key, Compare, Vector>::
749 ov_multiset(TypeHandle type_handle) :
750 ordered_vector<Key, Compare, Vector>(type_handle)
751{
752}
753
754/**
755 *
756 */
757 template<class Key, class Compare, class Vector>
758INLINE ov_multiset<Key, Compare, Vector>::
759 ov_multiset(const Compare &compare, TypeHandle type_handle) :
760 ordered_vector<Key, Compare, Vector>(compare, type_handle)
761{
762}
763
764/**
765 * Maps to insert_nonunique().
766 */
767 template<class Key, class Compare, class Vector>
768 typename ov_multiset<Key, Compare, Vector>::ITERATOR ov_multiset<Key, Compare, Vector>::
769 insert(typename ov_multiset<Key, Compare, Vector>::ITERATOR position,
770 const typename ov_multiset<Key, Compare, Vector>::VALUE_TYPE &key) {
771 return ordered_vector<Key, Compare, Vector>::insert_nonunique(position, key);
772}
773
774/**
775 * Maps to insert_nonunique().
776 */
777 template<class Key, class Compare, class Vector>
778INLINE typename ov_multiset<Key, Compare, Vector>::ITERATOR ov_multiset<Key, Compare, Vector>::
779 insert(const typename ov_multiset<Key, Compare, Vector>::VALUE_TYPE &key) {
780 return ordered_vector<Key, Compare, Vector>::insert_nonunique(key);
781}
782
783/**
784 * Maps to sort_nonunique().
785 */
786 template<class Key, class Compare, class Vector>
787INLINE void ov_multiset<Key, Compare, Vector>::
788 sort() {
789 ordered_vector<Key, Compare, Vector>::sort_nonunique();
790}
791
792/**
793 * Maps to verify_list_nonunique().
794 */
795 template<class Key, class Compare, class Vector>
796INLINE bool ov_multiset<Key, Compare, Vector>::
797 verify_list() const {
798 return ordered_vector<Key, Compare, Vector>::verify_list_nonunique();
799}
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition typeHandle.h:81
ordered_vector
This template class presents an interface similar to the STL set or multiset (and ov_set and ov_multi...
Definition ordered_vector.h:95
ordered_vector::back
reference back()
Returns a reference to the first element.
Definition ordered_vector.I:197
ordered_vector::reserve
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...
Definition ordered_vector.I:572
ordered_vector::front
reference front()
Returns a reference to the first element.
Definition ordered_vector.I:173
ordered_vector::max_size
size_type_0 max_size() const
Returns the maximum number of elements that can possibly be stored in an ordered vector.
Definition ordered_vector.I:231
ordered_vector::crbegin
const_reverse_iterator_0 crbegin() const
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
Definition ordered_vector.I:136
ordered_vector::cbegin
const_iterator_0 cbegin() const
Returns the iterator that marks the first element in the ordered vector.
Definition ordered_vector.I:117
ordered_vector::count
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.
Definition ordered_vector.I:484
ordered_vector::cend
const_iterator_0 cend() const
Returns the iterator that marks the end of the ordered vector.
Definition ordered_vector.I:126
ordered_vector::rend
reverse_iterator_0 rend()
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
Definition ordered_vector.I:70
ordered_vector::operator>=
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,...
Definition ordered_vector.I:300
ordered_vector::operator!=
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.
Definition ordered_vector.I:260
ordered_vector::operator==
bool operator==(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if the two ordered vectors are memberwise equivalent, false otherwise.
Definition ordered_vector.I:250
ordered_vector::sort_unique
void sort_unique()
Ensures that the vector is properly sorted after a potentially damaging operation.
Definition ordered_vector.I:587
ordered_vector::operator<
bool operator<(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically before the other one, false otherwise.
Definition ordered_vector.I:270
ordered_vector::begin
iterator_0 begin()
Returns the iterator that marks the first element in the ordered vector.
Definition ordered_vector.I:41
ordered_vector::operator>
bool operator>(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically after the other one, false otherwise.
Definition ordered_vector.I:280
ordered_vector::push_back
void push_back(const value_type_0 &key)
Adds the new element to the end of the vector without regard for proper sorting.
Definition ordered_vector.I:614
ordered_vector::rbegin
reverse_iterator_0 rbegin()
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
Definition ordered_vector.I:60
ordered_vector::swap
void swap(ordered_vector< Key, Compare, Vector > &other)
Exchanges the contents of this vector and the other vector, in constant time (e.g....
Definition ordered_vector.I:561
ordered_vector::operator<=
bool operator<=(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically before the other one or is equivalent,...
Definition ordered_vector.I:290
ordered_vector::sort_nonunique
void sort_nonunique()
Ensures that the vector is properly sorted after a potentially damaging operation.
Definition ordered_vector.I:602
ordered_vector::size
size_type_0 size() const
Returns the number of elements in the ordered vector.
Definition ordered_vector.I:221
ordered_vector::empty
bool empty() const
Returns true if the ordered vector is empty, false otherwise.
Definition ordered_vector.I:240
ordered_vector::end
iterator_0 end()
Returns the iterator that marks the end of the ordered vector.
Definition ordered_vector.I:50
ordered_vector::crend
const_reverse_iterator_0 crend() const
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
Definition ordered_vector.I:146
ordered_vector::pop_back
void pop_back()
Removes the last element at the end of the vector.
Definition ordered_vector.I:636
ordered_vector::insert_unverified
iterator_0 insert_unverified(iterator_0 position, const value_type_0 &key)
Inserts the indicated key into the ordered vector at the indicated place.
Definition ordered_vector.I:362
ordered_vector::clear
void clear()
Removes all elements from the ordered vector.
Definition ordered_vector.I:412
ov_multiset
A specialization of ordered_vector that emulates a standard STL set: many copies of each element are ...
Definition ordered_vector.h:290
ov_multiset::verify_list
bool verify_list() const
Maps to verify_list_nonunique().
Definition ordered_vector.I:797
ov_multiset::sort
void sort()
Maps to sort_nonunique().
Definition ordered_vector.I:788
ov_set
A specialization of ordered_vector that emulates a standard STL set: one copy of each element is allo...
Definition ordered_vector.h:269
ov_set::sort
void sort()
Maps to sort_unique().
Definition ordered_vector.I:731
ov_set::verify_list
bool verify_list() const
Maps to verify_list_unique().
Definition ordered_vector.I:740