Panda3D

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>
18 INLINE 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>
29 INLINE 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>
40 INLINE 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>
49 INLINE 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>
59 INLINE 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>
69 INLINE 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>
78 INLINE 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>
87 INLINE 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>
97 INLINE 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>
107 INLINE 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>
116 INLINE 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>
125 INLINE 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>
135 INLINE 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>
145 INLINE 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>
154 INLINE typename ordered_vector<Key, Compare, Vector>::REFERENCE ordered_vector<Key, Compare, Vector>::
155 operator [] (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>
163 INLINE typename ordered_vector<Key, Compare, Vector>::CONST_REFERENCE ordered_vector<Key, Compare, Vector>::
164 operator [] (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>
172 INLINE 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>
184 INLINE 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>
196 INLINE 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>
208 INLINE 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>
220 INLINE 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>
230 INLINE 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>
239 INLINE 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>
249 INLINE 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>
259 INLINE 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>
269 INLINE 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>
279 INLINE 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>
289 INLINE 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>
299 INLINE 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>
315 INLINE std::pair<typename ordered_vector<Key, Compare, Vector>::ITERATOR, bool> ordered_vector<Key, Compare, Vector>::
316 insert_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>
344 INLINE 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>
361 INLINE 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>
374 INLINE 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>
387 INLINE 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>
400 INLINE 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>
411 INLINE 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>
423 INLINE 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>
435 INLINE 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>
455 INLINE 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>
472 INLINE 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>
483 INLINE 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>
494 INLINE 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>
505 INLINE 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>
516 INLINE 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>
527 INLINE 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>
537 INLINE 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>
549 INLINE 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>
560 INLINE 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>
571 INLINE 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>
586 INLINE 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>
601 INLINE 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>
613 INLINE 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>
625 INLINE 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>
635 INLINE 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>
646 INLINE 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>
657 INLINE 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>
669 INLINE 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>
679 INLINE 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>
691 INLINE 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>
701 INLINE 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>
721 INLINE 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>
730 INLINE 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>
739 INLINE 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>
748 INLINE 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>
758 INLINE 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>
778 INLINE 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>
787 INLINE 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>
796 INLINE 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