Panda3D
Classes | Public Types | Public Member Functions | List of all members
ordered_vector< Key, Compare, Vector > Class Template Reference

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"

Inheritance diagram for ordered_vector< Key, Compare, Vector >:
ov_multiset< Key, Compare, Vector > ov_set< Key, Compare, Vector >

Public Types

typedef const_iterator_0 const_iterator
 
typedef Vector::const_iterator const_iterator_0
 
typedef const_reference_0 const_reference
 
typedef const Key & const_reference_0
 
typedef const_reverse_iterator_0 const_reverse_iterator
 
typedef Vector::const_reverse_iterator const_reverse_iterator_0
 
typedef difference_type_0 difference_type
 
typedef Vector::difference_type difference_type_0
 
typedef iterator_0 iterator
 
typedef Vector::iterator iterator_0
 
typedef key_compare_0 key_compare
 
typedef Compare key_compare_0
 
typedef key_type_0 key_type
 
typedef Key key_type_0
 
typedef reference_0 reference
 
typedef Key & reference_0
 
typedef reverse_iterator_0 reverse_iterator
 
typedef Vector::reverse_iterator reverse_iterator_0
 
typedef size_type_0 size_type
 
typedef Vector::size_type size_type_0
 
typedef value_compare_0 value_compare
 
typedef Compare value_compare_0
 
typedef value_type_0 value_type
 
typedef Key value_type_0
 

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
 

Detailed Description

template<class Key, class Compare = std::less<Key>, class Vector = pvector<Key>>
class ordered_vector< Key, Compare, Vector >

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.

Member Function Documentation

◆ back() [1/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::REFERENCE ordered_vector< Key, Compare, Vector >::back ( )
inline

Returns a reference to the first element.

Definition at line 197 of file ordered_vector.I.

◆ back() [2/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::CONST_REFERENCE ordered_vector< Key, Compare, Vector >::back ( ) const
inline

Returns a const reference to the last element.

Definition at line 209 of file ordered_vector.I.

◆ begin() [1/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::ITERATOR ordered_vector< Key, Compare, Vector >::begin ( )
inline

◆ begin() [2/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::CONST_ITERATOR ordered_vector< Key, Compare, Vector >::begin ( ) const
inline

Returns the iterator that marks the first element in the ordered vector.

Definition at line 79 of file ordered_vector.I.

◆ cbegin()

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::CONST_ITERATOR ordered_vector< Key, Compare, Vector >::cbegin ( ) const
inline

Returns the iterator that marks the first element in the ordered vector.

Definition at line 117 of file ordered_vector.I.

◆ cend()

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::CONST_ITERATOR ordered_vector< Key, Compare, Vector >::cend ( ) const
inline

Returns the iterator that marks the end of the ordered vector.

Definition at line 126 of file ordered_vector.I.

◆ clear()

template<class Key , class Compare , class Vector >
void ordered_vector< Key, Compare, Vector >::clear ( )
inline

◆ count()

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::SIZE_TYPE ordered_vector< Key, Compare, Vector >::count ( const key_type_0 &  key) const
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().

◆ crbegin()

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::CONST_REVERSE_ITERATOR ordered_vector< Key, Compare, Vector >::crbegin ( ) const
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.

◆ crend()

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::CONST_REVERSE_ITERATOR ordered_vector< Key, Compare, Vector >::crend ( ) const
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.

◆ empty()

template<class Key , class Compare , class Vector >
bool ordered_vector< Key, Compare, Vector >::empty ( ) const
inline

◆ end() [1/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::ITERATOR ordered_vector< Key, Compare, Vector >::end ( )
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().

◆ end() [2/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::CONST_ITERATOR ordered_vector< Key, Compare, Vector >::end ( ) const
inline

Returns the iterator that marks the end of the ordered vector.

Definition at line 88 of file ordered_vector.I.

◆ front() [1/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::REFERENCE ordered_vector< Key, Compare, Vector >::front ( )
inline

Returns a reference to the first element.

Definition at line 173 of file ordered_vector.I.

◆ front() [2/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::CONST_REFERENCE ordered_vector< Key, Compare, Vector >::front ( ) const
inline

Returns a const reference to the first element.

Definition at line 185 of file ordered_vector.I.

◆ insert_unverified()

template<class Key, class Compare = std::less<Key>, class Vector = pvector<Key>>
ordered_vector< Key, Compare, Vector >::ITERATOR ordered_vector< Key, Compare, Vector >::insert_unverified ( iterator_0  position,
const value_type_0 &  key 
)
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.

◆ max_size()

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::SIZE_TYPE ordered_vector< Key, Compare, Vector >::max_size ( ) const
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.

◆ operator !=()

template<class Key, class Compare, class Vector>
bool ordered_vector< Key, Compare, Vector >::operator != ( const ordered_vector< Key, Compare, Vector > &  other) const
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.

◆ operator >()

template<class Key, class Compare, class Vector>
bool ordered_vector< Key, Compare, Vector >::operator > ( const ordered_vector< Key, Compare, Vector > &  other) const
inline

Returns true if this ordered vector sorts lexicographically after the other one, false otherwise.

Definition at line 280 of file ordered_vector.I.

◆ operator >=()

template<class Key, class Compare, class Vector>
bool ordered_vector< Key, Compare, Vector >::operator >= ( const ordered_vector< Key, Compare, Vector > &  other) const
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.

◆ operator<()

template<class Key, class Compare, class Vector>
bool ordered_vector< Key, Compare, Vector >::operator< ( const ordered_vector< Key, Compare, Vector > &  other) const
inline

Returns true if this ordered vector sorts lexicographically before the other one, false otherwise.

Definition at line 270 of file ordered_vector.I.

◆ operator<=()

template<class Key, class Compare, class Vector>
bool ordered_vector< Key, Compare, Vector >::operator<= ( const ordered_vector< Key, Compare, Vector > &  other) const
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.

◆ operator==()

template<class Key, class Compare, class Vector>
bool ordered_vector< Key, Compare, Vector >::operator== ( const ordered_vector< Key, Compare, Vector > &  other) const
inline

Returns true if the two ordered vectors are memberwise equivalent, false otherwise.

Definition at line 250 of file ordered_vector.I.

◆ pop_back()

template<class Key , class Compare , class Vector >
void ordered_vector< Key, Compare, Vector >::pop_back ( )
inline

Removes the last element at the end of the vector.

Definition at line 636 of file ordered_vector.I.

Referenced by AsyncTaskManager::cleanup().

◆ push_back() [1/2]

template<class Key , class Compare , class Vector >
void ordered_vector< Key, Compare, Vector >::push_back ( const value_type_0 &  key)
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().

◆ push_back() [2/2]

template<class Key , class Compare , class Vector >
void ordered_vector< Key, Compare, Vector >::push_back ( value_type_0 &&  key)
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.

◆ rbegin() [1/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::REVERSE_ITERATOR ordered_vector< Key, Compare, Vector >::rbegin ( )
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().

◆ rbegin() [2/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::CONST_REVERSE_ITERATOR ordered_vector< Key, Compare, Vector >::rbegin ( ) const
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.

◆ rend() [1/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::REVERSE_ITERATOR ordered_vector< Key, Compare, Vector >::rend ( )
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().

◆ rend() [2/2]

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::CONST_REVERSE_ITERATOR ordered_vector< Key, Compare, Vector >::rend ( ) const
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.

◆ reserve()

template<class Key, class Compare = std::less<Key>, class Vector = pvector<Key>>
void ordered_vector< Key, Compare, Vector >::reserve ( size_type_0  n)
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().

◆ size()

template<class Key , class Compare , class Vector >
ordered_vector< Key, Compare, Vector >::SIZE_TYPE ordered_vector< Key, Compare, Vector >::size ( ) const
inline

◆ sort_nonunique()

template<class Key , class Compare , class Vector >
void ordered_vector< Key, Compare, Vector >::sort_nonunique ( )
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().

◆ sort_unique()

template<class Key , class Compare , class Vector >
void ordered_vector< Key, Compare, Vector >::sort_unique ( )
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().

◆ swap()

template<class Key, class Compare, class Vector>
void ordered_vector< Key, Compare, Vector >::swap ( ordered_vector< Key, Compare, Vector > &  other)
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().


The documentation for this class was generated from the following files: