#include <list_map.h>
Inheritance diagram for eastl::list_map< Key, T, Compare, Allocator >:
Collaboration diagram for eastl::list_map< Key, T, Compare, Allocator >:
Public Types | |
| typedef rbtree< Key, eastl::list_map_data< eastl::pair< const Key, T > >, Compare, Allocator, eastl::use_value_first< eastl::list_map_data< eastl::pair< const Key, T > > >, true, true > | base_type |
| typedef list_map< Key, T, Compare, Allocator > | this_type |
| typedef base_type::size_type | size_type |
| typedef base_type::key_type | key_type |
| typedef T | mapped_type |
| typedef eastl::pair< const Key, T > | value_type |
| typedef value_type & | reference |
| typedef const value_type & | const_reference |
| typedef base_type::node_type | node_type |
| typedef eastl::list_map_iterator< value_type, value_type *, value_type & > | iterator |
| typedef eastl::list_map_iterator< value_type, const value_type *, const value_type & > | const_iterator |
| typedef eastl::reverse_iterator< iterator > | reverse_iterator |
| typedef eastl::reverse_iterator< const_iterator > | const_reverse_iterator |
| typedef base_type::allocator_type | allocator_type |
| typedef eastl::pair< iterator, bool > | insert_return_type |
| typedef eastl::use_first< value_type > | extract_key |
Public Member Functions | |
| list_map (const allocator_type &allocator=EASTL_LIST_MAP_DEFAULT_ALLOCATOR) | |
| list_map (const Compare &compare, const allocator_type &allocator=EASTL_MAP_DEFAULT_ALLOCATOR) | |
| iterator | begin () EA_NOEXCEPT |
| const_iterator | begin () const EA_NOEXCEPT |
| const_iterator | cbegin () const EA_NOEXCEPT |
| iterator | end () EA_NOEXCEPT |
| const_iterator | end () const EA_NOEXCEPT |
| const_iterator | cend () const EA_NOEXCEPT |
| reverse_iterator | rbegin () EA_NOEXCEPT |
| const_reverse_iterator | rbegin () const EA_NOEXCEPT |
| const_reverse_iterator | crbegin () const EA_NOEXCEPT |
| reverse_iterator | rend () EA_NOEXCEPT |
| const_reverse_iterator | rend () const EA_NOEXCEPT |
| const_reverse_iterator | crend () const EA_NOEXCEPT |
| reference | front () |
| const_reference | front () const |
| reference | back () |
| const_reference | back () const |
| bool | push_front (const value_type &value) |
| bool | push_back (const value_type &value) |
| bool | push_front (const key_type &key, const mapped_type &value) |
| bool | push_back (const key_type &key, const mapped_type &value) |
| void | pop_front () |
| void | pop_back () |
| iterator | find (const key_type &key) |
| const_iterator | find (const key_type &key) const |
| template<typename U , typename Compare2 > | |
| iterator | find_as (const U &u, Compare2 compare2) |
| template<typename U , typename Compare2 > | |
| const_iterator | find_as (const U &u, Compare2 compare2) const |
| size_type | count (const key_type &key) const |
| size_type | erase (const key_type &key) |
| iterator | erase (const_iterator position) |
| reverse_iterator | erase (const_reverse_iterator position) |
| void | clear () |
| void | reset_lose_memory () |
| bool | validate () const |
| int | validate_iterator (const_iterator i) const |
| template<typename InputIterator > | |
| list_map (InputIterator first, InputIterator last, const Compare &compare, const allocator_type &allocator=EASTL_RBTREE_DEFAULT_ALLOCATOR)=delete | |
| insert_return_type | insert (const value_type &value)=delete |
| iterator | insert (const_iterator position, const value_type &value)=delete |
| template<typename InputIterator > | |
| void | insert (InputIterator first, InputIterator last)=delete |
| insert_return_type | insert (const key_type &key)=delete |
| iterator | erase (const_iterator first, const_iterator last)=delete |
| reverse_iterator | erase (reverse_iterator first, reverse_iterator last)=delete |
| void | erase (const key_type *first, const key_type *last)=delete |
| iterator | lower_bound (const key_type &key)=delete |
| const_iterator | lower_bound (const key_type &key) const =delete |
| iterator | upper_bound (const key_type &key)=delete |
| const_iterator | upper_bound (const key_type &key) const =delete |
| eastl::pair< iterator, iterator > | equal_range (const key_type &key)=delete |
| eastl::pair< const_iterator, const_iterator > | equal_range (const key_type &key) const =delete |
| mapped_type & | operator[] (const key_type &key)=delete |
| const allocator_type & | get_allocator () const EA_NOEXCEPT |
| allocator_type & | get_allocator () EA_NOEXCEPT |
| void | set_allocator (const allocator_type &allocator) |
| const key_compare & | key_comp () const |
| key_compare & | key_comp () |
| bool | empty () const EA_NOEXCEPT |
| size_type | size () const EA_NOEXCEPT |
Protected Types | |
| typedef eastl::list_map_data< eastl::pair< const Key, T > > | internal_value_type |
 Protected Types inherited from eastl::rbtree< Key, eastl::list_map_data< eastl::pair< const Key, T > >, eastl::less< Key >, EASTLAllocatorType, eastl::use_value_first< eastl::list_map_data< eastl::pair< const Key, T > > >, true, true > | |
| typedef ptrdiff_t | difference_type |
| typedef eastl_size_t | size_type |
| typedef Key | key_type |
| typedef eastl::list_map_data< eastl::pair< const Key, T > > | value_type |
| typedef rbtree_node< value_type > | node_type |
| typedef value_type & | reference |
| typedef const value_type & | const_reference |
| typedef value_type * | pointer |
| typedef const value_type * | const_pointer |
| typedef type_select< bMutableIterators, rbtree_iterator< value_type, value_type *, value_type & >, rbtree_iterator< value_type, const value_type *, const value_type & > >::type | iterator |
| typedef rbtree_iterator< value_type, const value_type *, const value_type & > | const_iterator |
| typedef eastl::reverse_iterator< iterator > | reverse_iterator |
| typedef eastl::reverse_iterator< const_iterator > | const_reverse_iterator |
| typedef EASTLAllocatorType | allocator_type |
| typedef eastl::less< Key > | key_compare |
| typedef type_select< bUniqueKeys, eastl::pair< iterator, bool >, iterator >::type | insert_return_type |
| typedef rbtree< Key, eastl::list_map_data< eastl::pair< const Key, T > >, eastl::less< Key >, EASTLAllocatorType, eastl::use_value_first< eastl::list_map_data< eastl::pair< const Key, T > > >, bMutableIterators, bUniqueKeys > | this_type |
| typedef rb_base< Key, eastl::list_map_data< eastl::pair< const Key, T > >, eastl::less< Key >, eastl::use_value_first< eastl::list_map_data< eastl::pair< const Key, T > > >, bUniqueKeys, this_type > | base_type |
| typedef integral_constant< bool, bUniqueKeys > | has_unique_keys_type |
| typedef base_type::extract_key | extract_key |
| Protected Types inherited from eastl::rb_base< Key, Value, Compare, ExtractKey, bUniqueKeys, RBTree > | |
| typedef ExtractKey | extract_key |
Protected Attributes | |
| list_map_data_base | mNode |
| Protected Attributes inherited from eastl::rbtree< Key, eastl::list_map_data< eastl::pair< const Key, T > >, eastl::less< Key >, EASTLAllocatorType, eastl::use_value_first< eastl::list_map_data< eastl::pair< const Key, T > > >, true, true > | |
| rbtree_node_base | mAnchor |
| size_type | mnSize |
| This node acts as end() and its mpLeft points to begin(), and mpRight points to rbegin() (the last node on the right). | |
| allocator_type | mAllocator |
| Stores the count of nodes in the tree (not counting the anchor node). | |
Additional Inherited Members | |
| Protected Member Functions inherited from eastl::rbtree< Key, eastl::list_map_data< eastl::pair< const Key, T > >, eastl::less< Key >, EASTLAllocatorType, eastl::use_value_first< eastl::list_map_data< eastl::pair< const Key, T > > >, true, true > | |
| node_type * | DoAllocateNode () |
| void | DoFreeNode (node_type *pNode) |
| node_type * | DoCreateNodeFromKey (const key_type &key) |
| node_type * | DoCreateNode (Args &&... args) |
| node_type * | DoCreateNode (const value_type &value) |
| node_type * | DoCreateNode (value_type &&value) |
| node_type * | DoCreateNode (const node_type *pNodeSource, node_type *pNodeParent) |
| node_type * | DoCopySubtree (const node_type *pNodeSource, node_type *pNodeDest) |
| void | DoNukeSubtree (node_type *pNode) |
| eastl::pair< iterator, bool > | DoInsertValue (true_type, Args &&... args) |
| iterator | DoInsertValue (false_type, Args &&... args) |
| eastl::pair< iterator, bool > | DoInsertValue (true_type, value_type &&value) |
| iterator | DoInsertValue (false_type, value_type &&value) |
| iterator | DoInsertValueImpl (node_type *pNodeParent, bool bForceToLeft, const key_type &key, Args &&... args) |
| iterator | DoInsertValueImpl (node_type *pNodeParent, bool bForceToLeft, const key_type &key, node_type *pNodeNew) |
| eastl::pair< iterator, bool > | DoInsertKey (true_type, const key_type &key) |
| iterator | DoInsertKey (false_type, const key_type &key) |
| iterator | DoInsertKey (true_type, const_iterator position, const key_type &key) |
| iterator | DoInsertKey (false_type, const_iterator position, const key_type &key) |
| iterator | DoInsertValueHint (true_type, const_iterator position, Args &&... args) |
| iterator | DoInsertValueHint (false_type, const_iterator position, Args &&... args) |
| iterator | DoInsertValueHint (true_type, const_iterator position, value_type &&value) |
| iterator | DoInsertValueHint (false_type, const_iterator position, value_type &&value) |
| iterator | DoInsertKeyImpl (node_type *pNodeParent, bool bForceToLeft, const key_type &key) |
| node_type * | DoGetKeyInsertionPositionUniqueKeys (bool &canInsert, const key_type &key) |
| node_type * | DoGetKeyInsertionPositionNonuniqueKeys (const key_type &key) |
| node_type * | DoGetKeyInsertionPositionUniqueKeysHint (const_iterator position, bool &bForceToLeft, const key_type &key) |
| node_type * | DoGetKeyInsertionPositionNonuniqueKeysHint (const_iterator position, bool &bForceToLeft, const key_type &key) |
| rbtree (const allocator_type &allocator) | |
| rbtree (const eastl::less< Key > &compare, const allocator_type &allocator=EASTL_RBTREE_DEFAULT_ALLOCATOR) | |
| rbtree (const this_type &x) | |
| rbtree (this_type &&x) | |
| rbtree (this_type &&x, const allocator_type &allocator) | |
| rbtree (InputIterator first, InputIterator last, const eastl::less< Key > &compare, const allocator_type &allocator=EASTL_RBTREE_DEFAULT_ALLOCATOR) | |
| rbtree (InputIterator first, InputIterator last, const C &compare, const allocator_type &allocator) | |
| const allocator_type & | get_allocator () const EA_NOEXCEPT |
| allocator_type & | get_allocator () EA_NOEXCEPT |
| void | set_allocator (const allocator_type &allocator) |
| const key_compare & | key_comp () const |
| key_compare & | key_comp () |
| this_type & | operator= (const this_type &x) |
| this_type & | operator= (std::initializer_list< value_type > ilist) |
| this_type & | operator= (this_type &&x) |
| void | swap (this_type &x) |
| iterator | begin () EA_NOEXCEPT |
| const_iterator | begin () const EA_NOEXCEPT |
| const_iterator | cbegin () const EA_NOEXCEPT |
| iterator | end () EA_NOEXCEPT |
| const_iterator | end () const EA_NOEXCEPT |
| const_iterator | cend () const EA_NOEXCEPT |
| reverse_iterator | rbegin () EA_NOEXCEPT |
| const_reverse_iterator | rbegin () const EA_NOEXCEPT |
| const_reverse_iterator | crbegin () const EA_NOEXCEPT |
| reverse_iterator | rend () EA_NOEXCEPT |
| const_reverse_iterator | rend () const EA_NOEXCEPT |
| const_reverse_iterator | crend () const EA_NOEXCEPT |
| bool | empty () const EA_NOEXCEPT |
| size_type | size () const EA_NOEXCEPT |
| insert_return_type | emplace (Args &&... args) |
| iterator | emplace_hint (const_iterator position, Args &&... args) |
| eastl::pair< iterator, bool > | try_emplace (const key_type &k, Args &&... args) |
| eastl::pair< iterator, bool > | try_emplace (key_type &&k, Args &&... args) |
| iterator | try_emplace (const_iterator position, const key_type &k, Args &&... args) |
| iterator | try_emplace (const_iterator position, key_type &&k, Args &&... args) |
| eastl::pair< typename rbtree< K, V, C, A, E, bM, bU >::iterator, bool > | try_emplace (const key_type &key, Args &&... args) |
| eastl::pair< typename rbtree< K, V, C, A, E, bM, bU >::iterator, bool > | try_emplace (key_type &&key, Args &&... args) |
| insert_return_type | insert (P &&otherValue) |
| iterator | insert (const_iterator hint, value_type &&value) |
| insert_return_type | insert (const value_type &value) |
| iterator | insert (const_iterator position, const value_type &value) |
| void | insert (std::initializer_list< value_type > ilist) |
| void | insert (InputIterator first, InputIterator last) |
| pair< iterator, bool > | insert_or_assign (const key_type &k, M &&obj) |
| pair< iterator, bool > | insert_or_assign (key_type &&k, M &&obj) |
| iterator | insert_or_assign (const_iterator hint, const key_type &k, M &&obj) |
| iterator | insert_or_assign (const_iterator hint, key_type &&k, M &&obj) |
| eastl::pair< typename rbtree< K, V, C, A, E, bM, bU >::iterator, bool > | insert_or_assign (const key_type &k, M &&obj) |
| eastl::pair< typename rbtree< K, V, C, A, E, bM, bU >::iterator, bool > | insert_or_assign (key_type &&k, M &&obj) |
| iterator | erase (const_iterator position) |
| iterator | erase (const_iterator first, const_iterator last) |
| reverse_iterator | erase (const_reverse_iterator position) |
| reverse_iterator | erase (const_reverse_iterator first, const_reverse_iterator last) |
| void | erase (const key_type *first, const key_type *last) |
| void | clear () |
| void | reset_lose_memory () |
| iterator | find (const key_type &key) |
| const_iterator | find (const key_type &key) const |
| iterator | find_as (const U &u, Compare2 compare2) |
| const_iterator | find_as (const U &u, Compare2 compare2) const |
| iterator | lower_bound (const key_type &key) |
| const_iterator | lower_bound (const key_type &key) const |
| iterator | upper_bound (const key_type &key) |
| const_iterator | upper_bound (const key_type &key) const |
| bool | validate () const |
| int | validate_iterator (const_iterator i) const |
| eastl::pair< typename rbtree< K, V, C, A, E, bM, bU >::iterator, bool > | DoInsertValue (true_type, Args &&... args) |
| Protected Member Functions inherited from eastl::rb_base< Key, Value, Compare, ExtractKey, bUniqueKeys, RBTree > | |
| rb_base (const Compare &compare) | |
| Protected Member Functions inherited from eastl::rb_base_compare_ebo< Compare, bool > | |
| rb_base_compare_ebo (const Compare &compare) | |
| Compare & | get_compare () |
| const Compare & | get_compare () const |
| template<typename T > | |
| bool | compare (const T &lhs, const T &rhs) |
| template<typename T > | |
| bool | compare (const T &lhs, const T &rhs) const |
Detailed Description
template<typename Key, typename T, typename Compare = eastl::less<Key>, typename Allocator = EASTLAllocatorType>
class eastl::list_map< Key, T, Compare, Allocator >
Implements a map like container, which also provides functionality similar to a list.
Note: Like a map, keys must still be unique. As such, push_back() and push_front() operations return a bool indicating success, or failure if the entry's key is already in use.
list_map is designed to improve performance for situations commonly implemented as: A map, which must be iterated over to find the oldest entry, or purge expired entries. A list, which must be iterated over to remove a player's record when they sign off.
list_map requires a little more memory per node than either a list or map alone, and many of list_map's functions have a higher operational cost (CPU time) than their counterparts in list and map. However, as the node count increases, list_map quickly outperforms either a list or a map when find [by-index] and front/back type operations are required.
In essence, list_map avoids O(n) iterations at the expense of additional costs to quick (O(1) and O(log n) operations: push_front(), push_back(), pop_front() and pop_back() have O(log n) operation time, similar to map::insert(), rather than O(1) time like a list, however, front() and back() maintain O(1) operation time.
As a canonical example, consider a large backlog of player group invites, which are removed when either: The invitation times out - in main loop: while( !listMap.empty() && listMap.front().IsExpired() ) { listMap.pop_front(); } The player rejects the outstanding invitation - on rejection: iter = listMap.find(playerId); if (iter != listMap.end()) { listMap.erase(iter); }
For a similar example, consider a high volume pending request container which must: Time out old requests (similar to invites timing out above) Remove requests once they've been handled (similar to rejecting invites above)
For such usage patterns, the performance benefits of list_map become dramatic with common O(n) operations once the node count rises to hundreds or more.
When high performance is a priority, Containers with thousands of nodes or more can quickly result in unacceptable performance when executing even infrequenty O(n) operations.
In order to maintain strong performance, avoid iterating over list_map whenever possible.
find_as In order to support the ability to have a tree of strings but be able to do efficiently lookups via char pointers (i.e. so they aren't converted to string objects), we provide the find_as function. This function allows you to do a find with a key of a type other than the tree's key type. See the find_as function for more documentation on this.
Pool allocation If you want to make a custom memory pool for a list_map container, your pool needs to contain items of type list_map::node_type. So if you have a memory pool that has a constructor that takes the size of pool items and the count of pool items, you would do this (assuming that MemoryPool implements the Allocator interface): typedef list_map<Widget, int, less<Widget>, MemoryPool> WidgetMap; // Delare your WidgetMap type. MemoryPool myPool(sizeof(WidgetMap::node_type), 100); // Make a pool of 100 Widget nodes. WidgetMap myMap(&myPool); // Create a map that uses the pool.
The documentation for this class was generated from the following file:
- third_party/EASTL/include/EASTL/bonus/list_map.h
