Internal container for custom multilist derived from XBidiCompositeSkipList. More...
#include <CSCompositeSkipList.h>
Public Types | |
| typedef size_t | size_type |
| An unsigned integral type that can represent any nonnegative value of the container's distance type. (Container) | |
| typedef ptrdiff_t | difference_type |
| A signed integral type used to represent the distance between two of the container's iterators. (Container) | |
| typedef XIndexedSkipList< X, CT > | container_type |
| Type that represents this internal container. | |
|
typedef XIterator0< X, container_type > | T0 |
| iterator | |
|
typedef XIterator1< X, container_type > | T1 |
| const_iterator | |
| typedef T0 | iterator |
| The type of iterator used to iterate through a container's elements. (Container) | |
| typedef T1 | const_iterator |
| A type of iterator that may be used to examine, but not to modify, a container's elements. (Container) | |
| typedef CT::value_type | value_type |
| The type of the object stored in a container. (Container) | |
| typedef value_type | T |
| typedef value_type | mapped_type |
| A type identical to value_type. | |
| typedef value_type & | mapped_type_reference |
| A type identical to reference. | |
| typedef const value_type | const_mapped_type |
| A type identical to const value_type. | |
| typedef const value_type & | const_mapped_type_reference |
| A type identical to const_reference. | |
| typedef CT::node_type | node_type |
| Internal node type. | |
| typedef value_type * | pointer |
| A type that behaves as a pointer to the container's value type. (Container) | |
| typedef value_type & | reference |
| A type that behaves as a reference to the container's value type. (Container) | |
| typedef const value_type & | const_reference |
| A type that behaves as a const reference to the container's value type. (Container) | |
| typedef std::reverse_iterator < iterator > | reverse_iterator |
| A Reverse Iterator adaptor whose base iterator type is the container's iterator type. (Reversible Container) | |
|
typedef std::reverse_iterator < const_iterator > | const_reverse_iterator |
| A Reverse Iterator adaptor whose base iterator type is the container's const iterator type. (Reversible Container) | |
| typedef CT::data_type | data_type |
| Internal shared data type. | |
|
typedef XTmpContainer < size_type, node_type > | tmp_container_type |
| Temporary container type for cut and splice. | |
Public Member Functions | |
| XIndexedSkipList () | |
| Default Constructor O(1) (Container) | |
| ~XIndexedSkipList () | |
| Destructor O(1) (Container) | |
| void | setData (void *data) |
| Set shared data. (Never call this) O(1) | |
| data_type * | getData () |
| Returns shared data used by this internal container. O(1) | |
| container_type & | operator= (const container_type &source) |
| Assignment Operator O(m*n*logn) (Container) | |
| iterator | begin () |
| Returns an iterator pointing to the beginning of the list. O(1) (Container) | |
| iterator | end () |
| Returns an iterator pointing to the end of the list. O(1) (Container) | |
| const_iterator | begin () const |
| Returns a const_iterator pointing to the beginning of the list. O(1) (Container) | |
| const_iterator | end () const |
| Returns a const_iterator pointing to the end of the list. O(1) (Container) | |
| reverse_iterator | rbegin () |
| Returns a reverse_iterator pointing to the beginning of the reversed list. O(1) (Reversible Container) | |
| reverse_iterator | rend () |
| Returns a reverse_iterator pointing to the end of the reversed list. O(1) (Reversible Container) | |
| const_reverse_iterator | rbegin () const |
| Returns a const_reverse_iterator pointing to the beginning of the reversed list. O(1) (Reversible Container) | |
| const_reverse_iterator | rend () const |
| Returns a reverse_iterator pointing to the end of the reversed list. O(1) (Reversible Container) | |
| size_type | size () const |
| Returns the size of the list. O(1) (Container) | |
| bool | empty () const |
| Returns true if the list's size is 0. O(1) (Container) | |
| reference | front () |
| Returns the first element. O(1) (Front Insertion Sequence) | |
| const_reference | front () const |
| Returns the first element. O(1) (Front Insertion Sequence) | |
| reference | back () |
| Returns the last element. O(1) (Back Insertion Sequence) | |
| const_reference | back () const |
| Returns the last element. O(1) (Back Insertion Sequence) | |
| void | push_front (const value_type &val) |
| Inserts a new element at the beginning. O(m*logn) (Front Insertion Sequence) | |
| void | pop_front () |
| Removes the first element. O(m*logn) (Front Insertion Sequence) | |
| void | destroy_front () |
| Deletes the first pointer element. O(m*logn) (Front Access Container) | |
| void | push_back (const value_type &val) |
| Inserts a new element at the end. O(m*logn) (Back Insertion Sequence) | |
| void | pop_back () |
| Removes the last element. O(m*logn) (Back Insertion Sequence) | |
| void | destroy_back () |
| Deletes the last pointer element. O(m*logn) (Back Access Container) | |
| template<class InIt > | |
| void | assign (InIt first, InIt last) |
| Clear list and copy element in iterator range [first,last) O(m*n*logn). | |
| void | assign (size_type count, const T &val) |
| Clear list and copy count elements of val. O(m*n*logn). | |
| void | insert (node_type *node) |
| Adds node to end of list. O(1C) | |
| void | erase (node_type *node) |
| Erases the specified node. O(logn) (Sequence) | |
| iterator | insert (const T &val) |
| Inserts element to end of list. O(m*logn) | |
| iterator | erase (const iterator &where) |
| Erases the element pointed to by where. O(m*logn) (Sequence) | |
| iterator | destroy (const iterator &where) |
| Deletes and erases the pointer element pointed to by where. O(m*logn) | |
| iterator | erase (const iterator &first, const iterator &last) |
| Erases all elements in a range. O(m*n*logn) (Sequence) | |
| iterator | destroy (const iterator &first, const iterator &last) |
| Deletes and erases all pointer elements in a range. O(m*n*logn) | |
| iterator | erase_index (size_type index) |
| Erases the element at the specified index. O(m*logn) | |
| iterator | destroy_index (size_type index) |
| Deletes and erases the element at the specified index. O(m*logn) | |
| void | clear () |
| Erases all of the elements. O(m+n) (Sequence) | |
| void | destroy () |
| Deletes and erases all of the pointer elements. O(m+n) | |
| void | swap (container_type &right) |
| Swaps the contents of two lists. NOT IMPLEMENTED YET!!! O(m*n*logn) (Container) | |
| mapped_type_reference | value (reference value) const |
| Returns mapped_type from within the value. O(1) | |
| const_mapped_type_reference | value (const_reference value) const |
| Returns const_mapped_type from within the value. O(1) | |
| mapped_type_reference | operator[] (size_type index) |
| Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN) | |
| const_mapped_type_reference | operator[] (size_type index) const |
| Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN) | |
| mapped_type_reference | at (size_type off) |
| Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN) | |
| const_mapped_type_reference | at (size_type off) const |
| Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN) | |
| size_type | max_size () const |
| Returns the largest possible size of the list. O(1) (Container) | |
| void | resize (size_type newsize) |
| Inserts or erases elements at the end such that the size becomes newsize. O(m*n) (Sequence) | |
| void | resize (size_type newsize, const value_type &val) |
| Inserts or erases elements at the end such that the size becomes newsize. O(m*n) (Sequence) | |
| iterator | insert (const iterator &where, const value_type &val) |
| Inserts a copy of val before where. O(m*logn). (Sequence) | |
| void | insert (const iterator &where, size_type count, const T &val) |
| Inserts count copies of val before where. O(m*n*logn). (Sequence) | |
| template<class InIt > | |
| void | insert (const iterator &where, InIt first, InIt last) |
| Inserts values from the range [first,last) before specified iterator. O(m*n*logn). (Sequence) | |
| void | reverse () |
| Reverse list. O(n) | |
| void | unique () |
| Removes all but the first element in every consecutive group of equal elements. O(m*n*logn) | |
| template<class Pr2 > | |
| void | unique (Pr2 pred) |
| Removes all but the first element in every consecutive group of equivalent elements. O(m*n*logn) | |
| void | sort () |
| Sorts *this according to operator<. O(n*logn) | |
| template<class Pr3 > | |
| void | sort (Pr3 pred) |
| Sorts *this according to predicate. O(n*logn) | |
| void | stable_sort () |
| Sorts *this according to operator<. O(n*logn) | |
| template<class Pr3 > | |
| void | stable_sort (Pr3 pred) |
| Sorts *this according to predicate. O(n*logn) | |
| void | erase_value (const value_type &val) |
| Erases all elements that compare equal to val. O(m*n*logn) | |
| template<class Pr1 > | |
| void | erase_if (Pr1 pred) |
| Erases all elements where pred(*where) is true. O(m*n*logn) | |
| template<class Pr4 > | |
| void | destroy_if (Pr4 pred) |
| Destroys all elements where pred(*where) is true. O(m*n*logn) | |
| void | move (const iterator &dest, const iterator &source) |
| Moves an element to another location. O(logn) | |
| void | move (const iterator &dest, const iterator &first, const iterator &last) |
| Moves a range of elements to another location. O(logn) | |
| void | swap (const iterator &left, const iterator &right) |
| Swap nodes of two elements. O(logn) | |
| void | swap (const iterator &first1, const iterator &last1, const iterator &first2, const iterator &last2) |
| Swap nodes of two ranges. O(logn) | |
| void | cut (const iterator &first, const iterator &last, tmp_container_type &right) |
| Internal method to extract nodes from the current internal containter. O(logn) | |
| void | cut (const iterator &where, tmp_container_type &right) |
| Internal method to extract a single node from the current internal containter. O(logn) | |
| void | splice (const iterator &where, tmp_container_type &right) |
| Internal method to insert nodes into the current internal containter. O(logn) | |
Private Types | |
|
typedef std::pair< size_type, node_type * > * | pair_t |
| Type for cache entry. | |
Private Member Functions | |
| void | scan (size_type index) const |
| Scan by index current internal container. O(logn) | |
| void | scanAll (size_type index) const |
| Scan by index current internal container and update ALL caches. O(m*logn) | |
| void | scan (const iterator &where) const |
| Scan by iterator current internal container. O(logn) | |
| void | scanAll (const iterator &where) const |
| Scan by iterator current internal container and update ALL caches. O(m*logn) | |
| void | scan (node_type *nodex) |
| Scan by node current internal container. O(logn) | |
| void | scanAll (node_type *nodex) |
| Scan by node current internal container and update ALL caches. O(m*logn) | |
| size_type & | getItems () |
| Returns reference to number of elements in container. | |
| void | setItems (const size_type sz) |
| Updates the number of elements in container. | |
|
std::pair< size_type, node_type * > * | getUpdate () |
| Returns current cache array for this internal container. | |
| size_type | getScanIndex () const |
| Returns cache index for this internal container. | |
| void | setScanIndex (const size_type sz) |
| Sets current cache index for this internal container. | |
Private Attributes | |
| data_type * | data |
Friends | |
| class | XIterator0< X, container_type > |
| class | XIterator1< X, container_type > |
Internal container for custom multilist derived from XBidiCompositeSkipList.
Almost identical to IndexedSkipList in functionality. Only default constructors available. Added methods for moving nodes around which is preferred over erase and insert.
| X | Index of the internal container within data_type for this iterator. |
| CT | Type of custom composite container. |
| typedef ptrdiff_t XIndexedSkipList< X, CT >::difference_type |
A signed integral type used to represent the distance between two of the container's iterators. (Container)
This type must be the same as the iterator's distance type.
| typedef T0 XIndexedSkipList< X, CT >::iterator |
The type of iterator used to iterate through a container's elements. (Container)
The iterator's value type is expected to be the container's value type. A conversion from the iterator type to the const iterator type must exist. The iterator type must be an input iterator.
| typedef CT::value_type XIndexedSkipList< X, CT >::value_type |
The type of the object stored in a container. (Container)
The value type must be Assignable, but need not be DefaultConstructible.
| typedef std::reverse_iterator<iterator> XIndexedSkipList< X, CT >::reverse_iterator |
A Reverse Iterator adaptor whose base iterator type is the container's iterator type. (Reversible Container)
Incrementing an object of type reverse_iterator moves backwards through the container: the Reverse Iterator adaptor maps operator++ to operator--.
| void XIndexedSkipList< X, CT >::scan | ( | size_type | index | ) | const [inline, private] |
Scan by index current internal container. O(logn)
This will update the cache so that all levels point to the item just before index. This allows the list to be updated.
Only the current internal container is scanned.
| index | Index to search. |
| void XIndexedSkipList< X, CT >::scanAll | ( | size_type | index | ) | const [inline, private] |
Scan by index current internal container and update ALL caches. O(m*logn)
This will update the cache so that all levels point to the item just before index. This allows the list to be updated.
Cache for ALL internal containers are updated.
| index | Index to search. |
| void XIndexedSkipList< X, CT >::scan | ( | const iterator & | where | ) | const [inline, private] |
Scan by iterator current internal container. O(logn)
This will update the cache so that all levels point to the item just before where. This allows the list to be updated. This will invoke a scan by index.
Only the current internal container is scanned.
| where | Iterator location to search. |
| void XIndexedSkipList< X, CT >::scanAll | ( | const iterator & | where | ) | const [inline, private] |
Scan by iterator current internal container and update ALL caches. O(m*logn)
This will update the cache so that all levels point to the item just before where. This allows the list to be updated. This will invoke a scan by index.
Cache for ALL internal containers are updated.
| where | Iterator location to search. |
| void XIndexedSkipList< X, CT >::scan | ( | node_type * | nodex | ) | [inline, private] |
Scan by node current internal container. O(logn)
This will update the cache so that all levels point to the item just before nodex. This allows the list to be updated.
Only the current internal container is scanned.
| nodex | Node to search. |
| void XIndexedSkipList< X, CT >::scanAll | ( | node_type * | nodex | ) | [inline, private] |
Scan by node current internal container and update ALL caches. O(m*logn)
This will update the cache so that all levels point to the item just before nodex. This allows the list to be updated.
Cache for ALL internal containers are updated.
| nodex | Node to search. |
| void XIndexedSkipList< X, CT >::setItems | ( | const size_type | sz | ) | [inline, private] |
Updates the number of elements in container.
| sz | New size of list. |
| void XIndexedSkipList< X, CT >::setScanIndex | ( | const size_type | sz | ) | [inline, private] |
Sets current cache index for this internal container.
| sz | New cache index. |
| void XIndexedSkipList< X, CT >::setData | ( | void * | data | ) | [inline, virtual] |
Set shared data. (Never call this) O(1)
This is for internal use only to set the shared data. The multilist constructor should invoke data->InitData() instead. The data parameter is void* to allow different shared types.
| data | Shared data usually of type XData. |
Implements XList< CT::value_type, CT::node_type >.
| container_type& XIndexedSkipList< X, CT >::operator= | ( | const container_type & | source | ) | [inline] |
Assignment Operator O(m*n*logn) (Container)
Clears current list and copies source elements to current list.
| source | list to copy from. |
| iterator XIndexedSkipList< X, CT >::begin | ( | ) | [inline] |
Returns an iterator pointing to the beginning of the list. O(1) (Container)
| iterator XIndexedSkipList< X, CT >::end | ( | ) | [inline] |
Returns an iterator pointing to the end of the list. O(1) (Container)
| const_iterator XIndexedSkipList< X, CT >::begin | ( | ) | const [inline] |
Returns a const_iterator pointing to the beginning of the list. O(1) (Container)
| const_iterator XIndexedSkipList< X, CT >::end | ( | ) | const [inline] |
Returns a const_iterator pointing to the end of the list. O(1) (Container)
| reverse_iterator XIndexedSkipList< X, CT >::rbegin | ( | ) | [inline] |
Returns a reverse_iterator pointing to the beginning of the reversed list. O(1) (Reversible Container)
| reverse_iterator XIndexedSkipList< X, CT >::rend | ( | ) | [inline] |
Returns a reverse_iterator pointing to the end of the reversed list. O(1) (Reversible Container)
| const_reverse_iterator XIndexedSkipList< X, CT >::rbegin | ( | ) | const [inline] |
Returns a const_reverse_iterator pointing to the beginning of the reversed list. O(1) (Reversible Container)
| const_reverse_iterator XIndexedSkipList< X, CT >::rend | ( | ) | const [inline] |
Returns a reverse_iterator pointing to the end of the reversed list. O(1) (Reversible Container)
| size_type XIndexedSkipList< X, CT >::size | ( | ) | const [inline] |
Returns the size of the list. O(1) (Container)
| bool XIndexedSkipList< X, CT >::empty | ( | ) | const [inline] |
Returns true if the list's size is 0. O(1) (Container)
| reference XIndexedSkipList< X, CT >::front | ( | ) | [inline] |
Returns the first element. O(1) (Front Insertion Sequence)
| const_reference XIndexedSkipList< X, CT >::front | ( | ) | const [inline] |
Returns the first element. O(1) (Front Insertion Sequence)
| reference XIndexedSkipList< X, CT >::back | ( | ) | [inline] |
Returns the last element. O(1) (Back Insertion Sequence)
| const_reference XIndexedSkipList< X, CT >::back | ( | ) | const [inline] |
Returns the last element. O(1) (Back Insertion Sequence)
| void XIndexedSkipList< X, CT >::push_front | ( | const value_type & | val | ) | [inline] |
Inserts a new element at the beginning. O(m*logn) (Front Insertion Sequence)
For non-sorted, indexed internal containers, the element is inserted at the front of the list. For sorted internal containers, the element is inserted at the proper location.
| val | Copy of object to be inserted into the container. |
| void XIndexedSkipList< X, CT >::push_back | ( | const value_type & | val | ) | [inline] |
Inserts a new element at the end. O(m*logn) (Back Insertion Sequence)
For non-sorted, indexed internal containers, the element is inserted at the end of the list. For sorted internal containers, the element is inserted at the proper location.
| val | Copy of object to be inserted into the container. |
| void XIndexedSkipList< X, CT >::assign | ( | InIt | first, |
| InIt | last | ||
| ) | [inline] |
Clear list and copy element in iterator range [first,last) O(m*n*logn).
For non-sorted, indexed internal containers, the elements are inserted at the end of the list. For sorted internal containers, the elements are inserted at the proper location.
| first | iterator at beginning of copy range. |
| last | iterator just beyond the end of copy range. |
| void XIndexedSkipList< X, CT >::assign | ( | size_type | count, |
| const T & | val | ||
| ) | [inline] |
Clear list and copy count elements of val. O(m*n*logn).
| count | Creates list with count elements. |
| val | Value to copy for each element created. |
| void XIndexedSkipList< X, CT >::insert | ( | node_type * | node | ) | [inline, virtual] |
Adds node to end of list. O(1C)
Required virtual function from XList
| node | Node to insert at the end of the current internal container only. |
Implements XList< CT::value_type, CT::node_type >.
| void XIndexedSkipList< X, CT >::erase | ( | node_type * | node | ) | [inline, virtual] |
Erases the specified node. O(logn) (Sequence)
Required virtual function from XList. Does not affect other lists. Node must not be deleted unless erased from all delegate containers.
| node | Node to erase. |
Implements XList< CT::value_type, CT::node_type >.
| iterator XIndexedSkipList< X, CT >::insert | ( | const T & | val | ) | [inline] |
Inserts element to end of list. O(m*logn)
This method is required for all internal containers. However, since the return value is different for different containers, it is not found in XList.
| val | Element to insert at the end of the list. |
| iterator XIndexedSkipList< X, CT >::erase | ( | const iterator & | where | ) | [inline] |
Erases the element pointed to by where. O(m*logn) (Sequence)
| where | Iterator that points to element to erase. |
| iterator XIndexedSkipList< X, CT >::destroy | ( | const iterator & | where | ) | [inline] |
Deletes and erases the pointer element pointed to by where. O(m*logn)
| where | Iterator that points to element to destroy. |
| iterator XIndexedSkipList< X, CT >::erase | ( | const iterator & | first, |
| const iterator & | last | ||
| ) | [inline] |
Erases all elements in a range. O(m*n*logn) (Sequence)
iterator last will remain valid after the call.
| first | iterator to first element to erase. |
| last | iterator just beyond last element to erase. |
| iterator XIndexedSkipList< X, CT >::destroy | ( | const iterator & | first, |
| const iterator & | last | ||
| ) | [inline] |
Deletes and erases all pointer elements in a range. O(m*n*logn)
iterator last will remain valid after the call.
| first | iterator to first pointer element to destroy. |
| last | iterator just beyond last pointer element to destroy. |
| iterator XIndexedSkipList< X, CT >::erase_index | ( | size_type | index | ) |
Erases the element at the specified index. O(m*logn)
| index | index of element to erase. |
| iterator XIndexedSkipList< X, CT >::destroy_index | ( | size_type | index | ) |
Deletes and erases the element at the specified index. O(m*logn)
| index | index of element to destroy. |
| void XIndexedSkipList< X, CT >::swap | ( | container_type & | right | ) | [inline] |
Swaps the contents of two lists. NOT IMPLEMENTED YET!!! O(m*n*logn) (Container)
| right | list with which to swap contents. |
| mapped_type_reference XIndexedSkipList< X, CT >::value | ( | reference | value | ) | const [inline] |
Returns mapped_type from within the value. O(1)
For SkipLists that act like a set, the key, value and mapped_type are all the same. For SkipLists that act like a map, the value is a pair. The key is value.first and the mapped_type is value.second. For indexed SkipLists, the mapped_type is the value.
| value | value to extract the mapped_type from. |
| const_mapped_type_reference XIndexedSkipList< X, CT >::value | ( | const_reference | value | ) | const [inline] |
Returns const_mapped_type from within the value. O(1)
For SkipLists that act like a set, the key, value and mapped_type are all the same. For SkipLists that act like a map, the value is a pair. The key is value.first and the mapped_type is value.second. For indexed SkipLists, the mapped_type is the value.
| value | value to extract the mapped_type from. |
| mapped_type_reference XIndexedSkipList< X, CT >::operator[] | ( | size_type | index | ) | [inline] |
Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)
If index is invalid, behaviour is undefined.
| index | index of element to retrieve. |
| const_mapped_type_reference XIndexedSkipList< X, CT >::operator[] | ( | size_type | index | ) | const [inline] |
Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)
If index is invalid, behaviour is undefined.
| index | index of element to retrieve. |
| mapped_type_reference XIndexedSkipList< X, CT >::at | ( | size_type | off | ) | [inline] |
Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)
If index is invalid, out_of_range exception is thrown.
| off | index of element to retrieve. |
| const_mapped_type_reference XIndexedSkipList< X, CT >::at | ( | size_type | off | ) | const [inline] |
Returns a reference to the element located at the specified index. O(logn) (Random Access Container LOGN)
If index is invalid, out_of_range exception is thrown.
| off | index of element to retrieve. |
| iterator XIndexedSkipList< X, CT >::insert | ( | const iterator & | where, |
| const value_type & | val | ||
| ) | [inline] |
Inserts a copy of val before where. O(m*logn). (Sequence)
| where | value gets inserted before where iterator. |
| val | value to insert. |
| void XIndexedSkipList< X, CT >::insert | ( | const iterator & | where, |
| size_type | count, | ||
| const T & | val | ||
| ) | [inline] |
Inserts count copies of val before where. O(m*n*logn). (Sequence)
| where | values gets inserted before where iterator. |
| count | number of copies to insert. |
| val | value to insert. |
| void XIndexedSkipList< X, CT >::insert | ( | const iterator & | where, |
| InIt | first, | ||
| InIt | last | ||
| ) | [inline] |
Inserts values from the range [first,last) before specified iterator. O(m*n*logn). (Sequence)
| where | values get inserted before where iterator. |
| first | iterator to first element to copy. |
| last | iterator just beyond last element to copy. |
| void XIndexedSkipList< X, CT >::reverse | ( | ) | [inline] |
Reverse list. O(n)
Existing iterators are partially invalidated and a refresh() must be done.
| void XIndexedSkipList< X, CT >::unique | ( | ) | [inline] |
Removes all but the first element in every consecutive group of equal elements. O(m*n*logn)
The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() - 1 comparisons for equality. Existing iterators are partially invalidated and a refresh() must be done.
| void XIndexedSkipList< X, CT >::unique | ( | Pr2 | pred | ) | [inline] |
Removes all but the first element in every consecutive group of equivalent elements. O(m*n*logn)
Two elements *i and *j are considered equivalent if pred(*i, *j) is true. The relative order of elements that are not removed remain valid. it performs exactly size() - 1 comparisons for equality. Existing iterators are partially invalidated and a refresh() must be done.
| pred | Comparison predicate. |
| void XIndexedSkipList< X, CT >::sort | ( | ) | [inline] |
Sorts *this according to operator<. O(n*logn)
The sort is not stable, that is, the relative order of equivalent elements is not preserved. All iterators remain valid and continue to point to the same elements. The number of comparisons is approximately N log N, where N is the list's size.
Existing iterators are partially invalidated and a refresh() must be done.
| void XIndexedSkipList< X, CT >::sort | ( | Pr3 | pred | ) | [inline] |
Sorts *this according to predicate. O(n*logn)
Pred must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements on objects of type T. This function sorts the list *this according to pred. The sort is not stable, that is, the relative order of equivalent elements is not preserved. All iterators remain valid and continue to point to the same elements. The number of comparisons is approximately N log N, where N is the list's size.
Existing iterators are partially invalidated and a refresh() must be done.
| pred | Comparison predicate. |
| void XIndexedSkipList< X, CT >::stable_sort | ( | ) | [inline] |
Sorts *this according to operator<. O(n*logn)
The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. The number of comparisons is approximately N log N, where N is the list's size.
Existing iterators are partially invalidated and a refresh() must be done.
| void XIndexedSkipList< X, CT >::stable_sort | ( | Pr3 | pred | ) | [inline] |
Sorts *this according to predicate. O(n*logn)
Pred must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements on objects of type T. This function sorts the list *this according to pred. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. The number of comparisons is approximately N log N, where N is the list's size.
Existing iterators are partially invalidated and a refresh() must be done.
| pred | Comparison predicate. |
| void XIndexedSkipList< X, CT >::erase_value | ( | const value_type & | val | ) | [inline] |
Erases all elements that compare equal to val. O(m*n*logn)
The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain partially valid.
| val | Value to remove. |
| void XIndexedSkipList< X, CT >::erase_if | ( | Pr1 | pred | ) |
Erases all elements where pred(*where) is true. O(m*n*logn)
The relative order of elements that are not removed is unchanged, and iterators to elements that are not erased remain partially valid.
| pred | Predicate |
| void XIndexedSkipList< X, CT >::destroy_if | ( | Pr4 | pred | ) |
Destroys all elements where pred(*where) is true. O(m*n*logn)
The relative order of elements that are not removed is unchanged, and iterators to elements that are not erased remain partially valid.
| pred | Predicate |
| void XIndexedSkipList< X, CT >::move | ( | const iterator & | dest, |
| const iterator & | source | ||
| ) | [inline] |
Moves an element to another location. O(logn)
It is recommended to use move and swap methods instead of erase and insert. A move only affects the current internal container and is therefore much faster.
Moves the node of source to immediately before dest.
All iterators between source and dest inclusive prior the move are partially invalidated. Call refresh() to revalidate. Iterators used in the call remain validated.
| dest | Destination iterator before which source node will be moved. |
| source | Iterator that points to the node to be moved. |
| void XIndexedSkipList< X, CT >::move | ( | const iterator & | dest, |
| const iterator & | first, | ||
| const iterator & | last | ||
| ) | [inline] |
Moves a range of elements to another location. O(logn)
It is recommended to use move and swap methods instead of erase and insert. A move only affects the current internal container and is therefore much faster.
Moves the nodes in the range [first,last) to immediately before dest.
After the calle, [first,dest) is the new range.
All iterators within the range and between dest and the range inclusive prior to the move are partially invalidated. Call refresh() to revalidate. Iterators used in the call remain validated.
| dest | Destination iterator before which range will be moved. |
| first | Iterator that points to the beginning node of the range to be moved. |
| last | Iterator that points to the one element past then end of the range to be moved. |
| void XIndexedSkipList< X, CT >::swap | ( | const iterator & | left, |
| const iterator & | right | ||
| ) | [inline] |
Swap nodes of two elements. O(logn)
It is recommended to use move and swap methods instead of erase and insert. A move only affects the current internal container and is therefore much faster.
All existing iterators remain valid unless they point to the same elements as left and right. Those iterators will be partially invalidated. All iterators always continue to point to their original elements.
TODO: Optimization if left.node->level==right.node->level, just swap the pointers and set scan_index=-1.
| left | Iterator of first node to swap. |
| right | Iterator of second node to swap. |
| void XIndexedSkipList< X, CT >::swap | ( | const iterator & | first1, |
| const iterator & | last1, | ||
| const iterator & | first2, | ||
| const iterator & | last2 | ||
| ) | [inline] |
Swap nodes of two ranges. O(logn)
It is recommended to use move and swap methods instead of erase and insert. A move only affects the current internal container and is therefore much faster.
Swap the position of the ranges [first1,last1) with [first2,last2). New ranges will be [first2,last1) and [first1,last2) unless last1==first2 or last2==first1. Remember that iterators always point to same elements. Only their index changes. If last1==first2, new ranges will be [first2,first1) and [first1,last2). If last2==first1, new ranges will be [first1,first2) and [first2,last1). If both ranges have the same number of elements, all iterators outside of both ranges remain valid. Iterators pointing to 'last1' or 'last2' also remain valid. For inequal size ranges, all existing iterators between or within the ranges are partially invalidated. All iterators always continue to point to their original elements.
| first1 | Iterator pointing to beginning of first range. |
| last1 | Iterator pointing to one element past the end of first range. |
| first2 | Iterator pointing to beginning of second range. |
| last2 | Iterator pointing to one element past the end of second range. |
| void XIndexedSkipList< X, CT >::cut | ( | const iterator & | first, |
| const iterator & | last, | ||
| tmp_container_type & | right | ||
| ) | [inline] |
Internal method to extract nodes from the current internal containter. O(logn)
Extracts a range of nodes [first, last) and inserts it into right.
A user may use this internal method as long as the range is put back into the current internal container with splice(). Use move() and swap() methods when possible. For this method, it is the user's responsability to know which iterators are invalidated and which are not.
This method will continue to be supported in future versions.
| first | Iterator for beginning of range to extract. |
| last | Iterator one element past the end of the range to extract. |
| right | Temporary container to insert the range into. |
| void XIndexedSkipList< X, CT >::cut | ( | const iterator & | where, |
| tmp_container_type & | right | ||
| ) | [inline] |
Internal method to extract a single node from the current internal containter. O(logn)
Extracts the node pointed to by where and inserts it into right.
A user may use this internal method as long as the node is put back into the current internal container with splice(). Use move() and swap() methods when possible. For this method, it is the user's responsability to know which iterators are invalidated and which are not.
This method will continue to be supported in future versions.
| where | Iterator that points to the node to extract. |
| right | Temporary container to insert the range into. |
| void XIndexedSkipList< X, CT >::splice | ( | const iterator & | where, |
| tmp_container_type & | right | ||
| ) | [inline] |
Internal method to insert nodes into the current internal containter. O(logn)
Inserts the nodes in right to the position immediately before where. The temporary container will now be empty.
A user may use this internal method in conjunction with cut(). Use move() and swap() methods when possible. For this method, it is the user's responsability to know which iterators are invalidated and which are not.
This method will continue to be supported in future versions.
| where | Nodes get inserted before where iterator in current internal container. |
| right | Temporary container that contains the nodes to insert. |
data_type* XIndexedSkipList< X, CT >::data [private] |
Internal shared data.
1.7.3
