This template class presents an interface similar to the STL set or multiset (and ov_set and ov_multiset are implemented specifically, below), but it is implemented using a vector that is kept always in sorted order. More...
#include "ordered_vector.h"
Public Member Functions | |
ordered_vector (TypeHandle type_handle=ov_set_type_handle) | |
ordered_vector (const Compare &compare, TypeHandle type_handle=ov_set_type_handle) | |
reference | back () |
Returns a reference to the first element. More... | |
const_reference | back () const |
Returns a const reference to the last element. More... | |
iterator_0 | begin () |
Returns the iterator that marks the first element in the ordered vector. More... | |
const_iterator_0 | begin () const |
Returns the iterator that marks the first element in the ordered vector. More... | |
const_iterator_0 | cbegin () const |
Returns the iterator that marks the first element in the ordered vector. More... | |
const_iterator_0 | cend () const |
Returns the iterator that marks the end of the ordered vector. More... | |
void | clear () |
Removes all elements from the ordered vector. More... | |
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. More... | |
const_reverse_iterator_0 | crbegin () const |
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order. More... | |
const_reverse_iterator_0 | crend () const |
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order. More... | |
bool | empty () const |
Returns true if the ordered vector is empty, false otherwise. More... | |
iterator_0 | end () |
Returns the iterator that marks the end of the ordered vector. More... | |
const_iterator_0 | end () const |
Returns the iterator that marks the end of the ordered vector. More... | |
std::pair< iterator_0, iterator_0 > | equal_range (const key_type_0 &key) |
std::pair< const_iterator_0, const_iterator_0 > | equal_range (const key_type_0 &key) const |
iterator_0 | erase (iterator_0 position) |
size_type_0 | erase (const key_type_0 &key) |
void | erase (iterator_0 first, iterator_0 last) |
iterator_0 | find (const key_type_0 &key) |
const_iterator_0 | find (const key_type_0 &key) const |
iterator_0 | find_particular (const key_type_0 &key) |
const_iterator_0 | find_particular (const key_type_0 &key) const |
reference | front () |
Returns a reference to the first element. More... | |
const_reference | front () const |
Returns a const reference to the first element. More... | |
iterator_0 | insert_nonunique (iterator_0 position, const value_type_0 &key) |
iterator_0 | insert_nonunique (const value_type_0 &key) |
iterator_0 | insert_unique (iterator_0 position, const value_type_0 &key) |
std::pair< iterator_0, bool > | insert_unique (const value_type_0 &key) |
iterator_0 | insert_unverified (iterator_0 position, const value_type_0 &key) |
Inserts the indicated key into the ordered vector at the indicated place. More... | |
iterator_0 | lower_bound (const key_type_0 &key) |
const_iterator_0 | lower_bound (const key_type_0 &key) const |
size_type_0 | max_size () const |
Returns the maximum number of elements that can possibly be stored in an ordered vector. More... | |
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. More... | |
bool | operator > (const ordered_vector< Key, Compare, Vector > &other) const |
Returns true if this ordered vector sorts lexicographically after the other one, false otherwise. More... | |
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, false otherwise. More... | |
reference | operator [] (size_type_0 n) |
const_reference | operator [] (size_type_0 n) const |
bool | operator< (const ordered_vector< Key, Compare, Vector > &other) const |
Returns true if this ordered vector sorts lexicographically before the other one, false otherwise. More... | |
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, false otherwise. More... | |
bool | operator== (const ordered_vector< Key, Compare, Vector > &other) const |
Returns true if the two ordered vectors are memberwise equivalent, false otherwise. More... | |
void | pop_back () |
Removes the last element at the end of the vector. More... | |
void | push_back (const value_type_0 &key) |
Adds the new element to the end of the vector without regard for proper sorting. More... | |
void | push_back (value_type_0 &&key) |
Adds the new element to the end of the vector without regard for proper sorting. More... | |
reverse_iterator_0 | rbegin () |
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order. More... | |
const_reverse_iterator_0 | rbegin () const |
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order. More... | |
reverse_iterator_0 | rend () |
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order. More... | |
const_reverse_iterator_0 | rend () const |
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order. More... | |
void | reserve (size_type_0 n) |
Informs the vector of a planned change in size; ensures that the capacity of the vector is greater than or equal to n. More... | |
void | resize (size_type_0 n) |
void | resize (size_type_0 n, const value_type_0 &value) |
size_type_0 | size () const |
Returns the number of elements in the ordered vector. More... | |
void | sort_nonunique () |
Ensures that the vector is properly sorted after a potentially damaging operation. More... | |
void | sort_unique () |
Ensures that the vector is properly sorted after a potentially damaging operation. More... | |
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). More... | |
iterator_0 | upper_bound (const key_type_0 &key) |
const_iterator_0 | upper_bound (const key_type_0 &key) const |
bool | verify_list_nonunique () const |
bool | verify_list_unique () const |
This template class presents an interface similar to the STL set or multiset (and ov_set and ov_multiset are implemented specifically, below), but it is implemented using a vector that is kept always in sorted order.
In most cases, an ov_set or ov_multiset may be dropped in transparently in place of a set or multiset, but the implementation difference has a few implications:
(1) The ov_multiset will maintain stability of order between elements that sort equally: they are stored in the order in which they were added, from back to front.
(2) Insert and erase operations into the middle of the set can be slow, just as inserting into the middle of a vector can be slow. In fact, building up an ov_set by inserting elements one at a time is an n^2 operation. On the other hand, building up an ov_set by adding elements to the end, one at time, is somewhat faster than building up a traditional set; and you can even add unsorted elements with push_back() and then call sort() when you're done, for a log(n) operation.
(3) Iterators may not be valid for the life of the ordered_vector. If the vector reallocates itself, all iterators are invalidated.
(4) Random access into the set is easy with the [] operator.
Definition at line 95 of file ordered_vector.h.
|
inline |
Returns a reference to the first element.
Definition at line 197 of file ordered_vector.I.
|
inline |
Returns a const reference to the last element.
Definition at line 209 of file ordered_vector.I.
|
inline |
Returns the iterator that marks the first element in the ordered vector.
Definition at line 41 of file ordered_vector.I.
Referenced by AnimPreloadTable::add_anims_from(), RenderEffects::adjust_transform(), SpeedTreeNode::apply_attribs_to_vertices(), MayaNodeTree::clear_egg(), CharacterJoint::clear_local_transforms(), CharacterJoint::clear_net_transforms(), TransformBlend::compare_to(), SpeedTreeNode::count_total_instances(), CPT(), AttribNodeRegistry::find_node(), TextureAttrib::find_on_stage(), Multifile::find_subfile(), CharacterJoint::get_local_transforms(), CharacterJoint::get_net_transforms(), SparseArray::get_next_higher_different_bit(), SparseArray::get_num_bits(), SparseArray::get_num_off_bits(), SparseArray::get_num_on_bits(), TransformBlend::normalize_weights(), SpeedTreeNode::remove_all_trees(), InputDeviceSet::remove_devices_from(), GraphicsEngine::reset_all_windows(), MayaNodeTree::reset_sliders(), RenderEffects::safe_to_transform(), SpeedTreeNode::snap_to_terrain(), InputDeviceSet::write(), OccluderEffect::write_datagram(), AnimPreloadTable::write_datagram(), CharacterJoint::write_datagram(), TexMatrixAttrib::write_datagram(), TransformBlend::write_datagram(), ClipPlaneAttrib::write_datagram(), SparseArray::write_datagram(), TextureAttrib::write_datagram(), and SpeedTreeNode::write_datagram().
|
inline |
Returns the iterator that marks the first element in the ordered vector.
Definition at line 79 of file ordered_vector.I.
|
inline |
Returns the iterator that marks the first element in the ordered vector.
Definition at line 117 of file ordered_vector.I.
|
inline |
Returns the iterator that marks the end of the ordered vector.
Definition at line 126 of file ordered_vector.I.
|
inline |
Removes all elements from the ordered vector.
Definition at line 412 of file ordered_vector.I.
Referenced by InputDeviceSet::clear(), AttribNodeRegistry::clear(), SparseArray::clear(), AnimPreloadTable::clear_anims(), MouseWatcherBase::clear_regions(), TransformBlend::limit_transforms(), and SpeedTreeNode::remove_all_trees().
|
inline |
Returns the number of elements that sort equivalent to the key that are in the vector.
Definition at line 484 of file ordered_vector.I.
Referenced by CharacterJoint::has_local_transform(), and CharacterJoint::has_net_transform().
|
inline |
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order.
Definition at line 136 of file ordered_vector.I.
|
inline |
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
Definition at line 146 of file ordered_vector.I.
|
inline |
Returns true if the ordered vector is empty, false otherwise.
Definition at line 240 of file ordered_vector.I.
Referenced by AsyncTaskManager::cleanup(), SparseArray::get_highest_off_bit(), SparseArray::get_highest_on_bit(), SparseArray::get_lowest_off_bit(), SparseArray::get_lowest_on_bit(), SparseArray::get_num_bits(), TextureAttrib::get_texture(), LightAttrib::has_any_on_light(), SparseArray::is_all_on(), RenderEffects::is_empty(), GraphicsEngine::is_empty(), OccluderEffect::is_identity(), ClipPlaneAttrib::is_identity(), TextureAttrib::is_identity(), LightAttrib::is_identity(), TextureAttrib::is_off(), SparseArray::is_zero(), MouseWatcher::replace_group(), TransformBlend::transform_point(), and TransformBlend::transform_vector().
|
inline |
Returns the iterator that marks the end of the ordered vector.
Definition at line 50 of file ordered_vector.I.
Referenced by AnimPreloadTable::add_anims_from(), SpeedTreeNode::add_tree(), RenderEffects::adjust_transform(), SpeedTreeNode::apply_attribs_to_vertices(), MayaNodeTree::clear_egg(), CharacterJoint::clear_local_transforms(), CharacterJoint::clear_net_transforms(), TransformBlend::compare_to(), SpeedTreeNode::count_total_instances(), CPT(), AttribNodeRegistry::find_node(), TextureAttrib::find_on_stage(), Multifile::find_subfile(), CharacterJoint::get_local_transforms(), CharacterJoint::get_net_transforms(), SparseArray::get_next_higher_different_bit(), SparseArray::get_num_off_bits(), SparseArray::get_num_on_bits(), TextureAttrib::get_on_stage_override(), TexMatrixAttrib::get_override(), InputDeviceSet::has_device(), Multifile::has_directory(), SpeedTreeNode::has_instance_list(), LightAttrib::has_off_light(), ClipPlaneAttrib::has_off_plane(), TextureAttrib::has_off_stage(), LightAttrib::has_on_light(), OccluderEffect::has_on_occluder(), ClipPlaneAttrib::has_on_plane(), TransformBlend::normalize_weights(), SpeedTreeNode::remove_all_trees(), InputDeviceSet::remove_devices_from(), AsyncTaskManager::remove_task_chain(), SpeedTreeNode::remove_tree(), GraphicsEngine::reset_all_windows(), MayaNodeTree::reset_sliders(), RenderEffects::safe_to_transform(), Multifile::scan_directory(), SpeedTreeNode::snap_to_terrain(), InputDeviceSet::write(), OccluderEffect::write_datagram(), AnimPreloadTable::write_datagram(), CharacterJoint::write_datagram(), TexMatrixAttrib::write_datagram(), TransformBlend::write_datagram(), SparseArray::write_datagram(), ClipPlaneAttrib::write_datagram(), TextureAttrib::write_datagram(), and SpeedTreeNode::write_datagram().
|
inline |
Returns the iterator that marks the end of the ordered vector.
Definition at line 88 of file ordered_vector.I.
|
inline |
Returns a reference to the first element.
Definition at line 173 of file ordered_vector.I.
|
inline |
Returns a const reference to the first element.
Definition at line 185 of file ordered_vector.I.
|
inline |
Inserts the indicated key into the ordered vector at the indicated place.
The user is trusted to have already verified that this is the correct sorting position; no checks are made.
Definition at line 362 of file ordered_vector.I.
|
inline |
Returns the maximum number of elements that can possibly be stored in an ordered vector.
Definition at line 231 of file ordered_vector.I.
|
inline |
Returns true if the two ordered vectors are not memberwise equivalent, false if they are.
Definition at line 260 of file ordered_vector.I.
|
inline |
Returns true if this ordered vector sorts lexicographically after the other one, false otherwise.
Definition at line 280 of file ordered_vector.I.
|
inline |
Returns true if this ordered vector sorts lexicographically after the other one or is equivalent, false otherwise.
Definition at line 300 of file ordered_vector.I.
|
inline |
Returns true if this ordered vector sorts lexicographically before the other one, false otherwise.
Definition at line 270 of file ordered_vector.I.
|
inline |
Returns true if this ordered vector sorts lexicographically before the other one or is equivalent, false otherwise.
Definition at line 290 of file ordered_vector.I.
|
inline |
Returns true if the two ordered vectors are memberwise equivalent, false otherwise.
Definition at line 250 of file ordered_vector.I.
|
inline |
Removes the last element at the end of the vector.
Definition at line 636 of file ordered_vector.I.
Referenced by AsyncTaskManager::cleanup().
|
inline |
Adds the new element to the end of the vector without regard for proper sorting.
This is a bad idea to do except to populate the vector the first time; be sure to call sort() after you have added all the elements.
Definition at line 614 of file ordered_vector.I.
Referenced by AnimPreloadTable::add_anims_from(), SparseArray::lower_on(), GraphicsEngine::open_windows(), and InputDeviceSet::remove_devices_from().
|
inline |
Adds the new element to the end of the vector without regard for proper sorting.
This is a bad idea to do except to populate the vector the first time; be sure to call sort() after you have added all the elements.
Definition at line 626 of file ordered_vector.I.
|
inline |
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order.
Definition at line 60 of file ordered_vector.I.
Referenced by SparseArray::compare_to().
|
inline |
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order.
Definition at line 98 of file ordered_vector.I.
|
inline |
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
Definition at line 70 of file ordered_vector.I.
Referenced by SparseArray::compare_to().
|
inline |
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
Definition at line 108 of file ordered_vector.I.
|
inline |
Informs the vector of a planned change in size; ensures that the capacity of the vector is greater than or equal to n.
Definition at line 572 of file ordered_vector.I.
Referenced by AnimPreloadTable::add_anims_from(), CPT(), TransformBlend::fillin(), SparseArray::read_datagram(), and InputDeviceSet::reserve().
|
inline |
Returns the number of elements in the ordered vector.
Definition at line 221 of file ordered_vector.I.
Referenced by AnimPreloadTable::add_anims_from(), AsyncTaskManager::cleanup(), TransformBlend::compare_to(), SparseArray::get_highest_off_bit(), SparseArray::get_highest_on_bit(), AnimPreloadTable::get_num_anims(), SparseArray::get_num_bits(), MayaNodeTree::get_num_blend_descs(), RenderEffects::get_num_effects(), SparseArray::get_num_subranges(), TransformBlend::limit_transforms(), InputDeviceSet::output(), InputDeviceSet::size(), RenderEffects::size(), AnimPreloadTable::write_datagram(), CharacterJoint::write_datagram(), TexMatrixAttrib::write_datagram(), TransformBlend::write_datagram(), SparseArray::write_datagram(), RenderEffects::write_datagram(), and SpeedTreeNode::write_datagram().
|
inline |
Ensures that the vector is properly sorted after a potentially damaging operation.
This should not normally need to be called, unless the user has written to the vector using the non-const iterators or has called push_back().
Definition at line 602 of file ordered_vector.I.
Referenced by ov_multiset< Key, Compare, Vector >::sort().
|
inline |
Ensures that the vector is properly sorted after a potentially damaging operation.
This should not normally need to be called, unless the user has written to the vector using the non-const iterators or has called push_back().
This flavor of sort also eliminates repeated elements.
Definition at line 587 of file ordered_vector.I.
Referenced by ov_set< StageNode, CompareTextureStagePointer, epvector< StageNode > >::sort().
|
inline |
Exchanges the contents of this vector and the other vector, in constant time (e.g., with a pointer swap).
Definition at line 561 of file ordered_vector.I.
Referenced by GraphicsEngine::remove_all_windows(), InputDeviceSet::remove_devices_from(), and MouseWatcher::replace_group().