Source code repo: http://github.com/khizmax/libcds/
Download: http://sourceforge.net/projects/libcds/files/
-
+
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
Usually, ordered single-linked list is used as a building block for the hash table implementation.
Iterable list is suitable for almost append-only hash table because the list doesn't delete
its internal node when erasing a key but it is marked them as empty to be reused in the future.
- However, plenty of empty nodes degrades performance.
-
+ However, plenty of empty nodes degrades performance.
+
The complexity of searching is <tt>O(N)</tt>.
Template arguments:
this code
\code
if ( it1 == it2 )
- assert( &(*it1) == &(*it2) );
+ assert( &(*it1) == &(*it2));
\endcode
can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
If the item \p key is not found in the list, then \p key is inserted
iff \p bInsert is \p true.
- Otherwise, the current element is changed to <tt> value_type( key, val )</tt>,
+ Otherwise, the current element is changed to <tt> value_type( key, val )</tt>,
the old element will be retired later.
Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
bool erase_with( K const& key, Less pred )
{
CDS_UNUSED( pred );
- return base_class::erase_with( key, less_wrapper<Less>() );
+ return base_class::erase_with( key, less_wrapper<Less>());
}
/// Deletes \p key from the list
guarded_ptr extract_with( K const& key, Less pred )
{
CDS_UNUSED( pred );
- return base_class::extract_with( key, less_wrapper<Less>() );
+ return base_class::extract_with( key, less_wrapper<Less>());
}
/// Checks whether the list contains \p key
bool contains( Q const& key, Less pred ) const
{
CDS_UNUSED( pred );
- return base_class::contains( key, less_wrapper<Less>() );
+ return base_class::contains( key, less_wrapper<Less>());
}
/// Finds the key \p key and performs an action with it
guarded_ptr get_with( K const& key, Less pred ) const
{
CDS_UNUSED( pred );
- return base_class::get_with( key, less_wrapper<Less>() );
+ return base_class::get_with( key, less_wrapper<Less>());
}
/// Checks if the list is empty
template <typename K>
bool insert_at( head_type& refHead, K&& key )
{
- return base_class::insert_at( refHead, value_type( key_type( std::forward<K>( key )), mapped_type() ));
+ return base_class::insert_at( refHead, value_type( key_type( std::forward<K>( key )), mapped_type()));
}
template <typename K, typename V>