class implementing a tiny::set, tiny::multiset, and tiny::multimap. More...
#include <tpie/tiny.h>
Classes | |
struct | value_compare |
Public Member Functions | |
set_impl () | |
Default constructor. More... | |
set_impl (const Comp &comp, const Alloc &alloc=Alloc()) | |
Default constructor. More... | |
set_impl (const Alloc &alloc) | |
Default constructor. More... | |
set_impl (const set_impl &other) | |
Copy constructor. More... | |
set_impl (const set_impl &other, const Alloc &alloc) | |
Copy constructor. More... | |
set_impl (set_impl &&other) | |
Move constructor. More... | |
set_impl (set_impl &&other, const Alloc &alloc) | |
Move constructor. More... | |
template<class InputIterator > | |
set_impl (InputIterator first, InputIterator last, const Comp &comp=Comp(), const Alloc &alloc=Alloc()) | |
Constructs the container with the contents of the range [first, last). More... | |
set_impl (std::initializer_list< value_type > init, const Comp &comp=Comp(), const Alloc &alloc=Alloc()) | |
Constructs the container with the contents of the initializer list init. More... | |
iterator | begin () noexcept |
Returns an iterator to the first element of the container. More... | |
const_iterator | begin () const noexcept |
Returns an iterator to the first element of the container. More... | |
const_iterator | cbegin () const noexcept |
Returns an iterator to the first element of the container. More... | |
reverse_iterator | rbegin () noexcept |
Returns a reverse iterator to the first element of the reversed container. More... | |
const_reverse_iterator | rbegin () const noexcept |
Returns a reverse iterator to the first element of the reversed container. More... | |
const_reverse_iterator | crbegin () const noexcept |
Returns a reverse iterator to the first element of the reversed container. More... | |
iterator | end () noexcept |
Returns an iterator to the element following the last element of the container. More... | |
const_iterator | end () const noexcept |
Returns an iterator to the element following the last element of the container. More... | |
const_iterator | cend () const noexcept |
Returns an iterator to the element following the last element of the container. More... | |
reverse_iterator | rend () noexcept |
Returns a reverse iterator to the element following the last element of the reversed container. More... | |
const_reverse_iterator | rend () const noexcept |
Returns a reverse iterator to the element following the last element of the reversed container. More... | |
const_reverse_iterator | crend () const noexcept |
Returns a reverse iterator to the element following the last element of the reversed container. More... | |
bool | empty () const noexcept |
Checks if the container has no elements, i.e. More... | |
size_t | size () const noexcept |
Returns the number of elements in the container, i.e. More... | |
size_t | max_size () const noexcept |
Returns the maximum number of elements the container is able to hold due to system or library implementation limitations. More... | |
void | clear () |
Removes all elements from the container. More... | |
iterator | erase (iterator pos) |
Removes the element at pos. More... | |
iterator | erase (iterator first, iterator last) |
Removes the elements in the range [first; last), which must be a valid range in *this. More... | |
size_t | erase (const Key &key) |
Removes all elements with the key value key. More... | |
void | swap (set_impl &o) |
Exchanges the contents of the container with those of other. More... | |
iterator | find (const Key &key) noexcept |
Finds an element with key equivalent to key. More... | |
const_iterator | find (const Key &key) const noexcept |
Finds an element with key equivalent to key. More... | |
std::pair< iterator, iterator > | equal_range (const Key &key) noexcept |
Returns a range containing all elements with the given key in the container. More... | |
std::pair< const_iterator, const_iterator > | equal_range (const Key &key) const noexcept |
Returns a range containing all elements with the given key in the container. More... | |
iterator | lower_bound (const Key &key) noexcept |
Returns an iterator pointing to the first element that is not less than key. More... | |
const_iterator | lower_bound (const Key &key) const noexcept |
Returns an iterator pointing to the first element that is not less than key. More... | |
iterator | upper_bound (const Key &key) noexcept |
Returns an iterator pointing to the first element that is greater than key. More... | |
const_iterator | upper_bound (const Key &key) const noexcept |
Returns an iterator pointing to the first element that is greater than key. More... | |
key_compare | key_comp () const noexcept |
Returns the function object that compares the keys, which is a copy of this container's constructor argument comp. More... | |
value_compare | value_comp () const noexcept |
Returns a function object that compares objects of type std::map::value_type (key-value pairs) by using key_comp to compare the first components of the pairs. More... | |
allocator_type | get_allocator () const |
Returns the allocator associated with the container. More... | |
set_impl & | operator= (const set_impl &other) |
Copy assignment operator. More... | |
set_impl & | operator= (set_impl &&other) |
Move assignment operator. More... | |
set_impl & | operator= (std::initializer_list< value_type > ilist) |
Replaces the contents with those identified by initializer list ilist. More... | |
size_t | count (const Key k) const noexcept |
Returns the number of elements with key k. More... | |
insert_result | insert (const T &t) |
Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key. More... | |
template<typename TT > | |
insert_result | insert (TT &&t) |
Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key. More... | |
insert_result | insert (const_iterator, const T &t) |
Does the same as normal insert, we ignore the hint. More... | |
template<typename TT > | |
insert_result | insert (const_iterator, TT &&t) |
Does the same as normal insert, we ignore the hint. More... | |
template<class InputIt > | |
void | insert (InputIt first, InputIt last) |
Inserts elements from range [first, last). More... | |
void | insert (std::initializer_list< value_type > list) |
Inserts elements from initializer list ilist. More... | |
template<class... Args> | |
insert_result | emplace (Args &&...args) |
Inserts a new element into the container by constructing it in-place with the given args if there is no element with the key in the container. More... | |
template<class... Args> | |
insert_result | emplace_hint (const_iterator, Args &&...args) |
Do the same as emplace, and ignore the hint. More... | |
void | reserve (size_t new_cap) |
Increase the capacity of the container to a value that's greater or equal to new_cap. More... | |
void | shrink_to_fit () |
Requests the removal of unused capacity. More... | |
size_t | capacity () const noexcept |
Returns the number of elements that the container has currently allocated space for. More... | |
Protected Types | |
typedef std::vector< T, Alloc > | Inner |
typedef InsertHelp::template type< Inner > | IH |
Protected Attributes | |
value_compare | comp |
std::vector< value_type, Alloc > | inner |
Friends | |
bool | operator== (const set_impl &lhs, const set_impl &rhs) |
true if the contents of the containers are equal, false otherwise. More... | |
bool | operator!= (const set_impl &lhs, const set_impl &rhs) |
true if the contents of the containers are not equal, false otherwise. More... | |
bool | operator< (const set_impl &lhs, const set_impl &rhs) |
true if the contents of the lhs are lexicographically less than the contents of rhs, false otherwise. More... | |
bool | operator<= (const set_impl &lhs, const set_impl &rhs) |
true if the contents of the lhs are lexicographically less than or equal the contents of rhs, false otherwise. More... | |
bool | operator> (const set_impl &lhs, const set_impl &rhs) |
true if the contents of the lhs are lexicographically greater than the contents of rhs, false otherwise. More... | |
bool | operator>= (const set_impl &lhs, const set_impl &rhs) |
true if the contents of the lhs are lexicographically greater than or equal the contents of rhs, false otherwise. More... | |
void | swap (set_impl &lhs, set_impl &rhs) |
Specializes the std::swap algorithm using adl. More... | |
class implementing a tiny::set, tiny::multiset, and tiny::multimap.
Also serve as a base class for the tiny::map.
A tiny container is just a sorted vector of elements. When you have less then 512 elements in a std::set using a tiny::set will often be faster. Also much less code will be generated, so compiletime will improve.
Note that unlike in containers based on a red black tree, iterators may be invalidated by insert. To avoid this use reserve, and check the capacity.
|
inline |
|
inlineexplicit |
|
inlineexplicit |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Constructs the container with the contents of the range [first, last).
Definition at line 201 of file tiny.h.
|
inline |
Constructs the container with the contents of the initializer list init.
Definition at line 210 of file tiny.h.
|
inlinenoexcept |
Returns an iterator to the first element of the container.
Definition at line 219 of file tiny.h.
Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::erase().
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
|
inline |
Removes all elements from the container.
Definition at line 300 of file tiny.h.
Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::operator=().
|
inlinenoexcept |
Returns the number of elements with key k.
Definition at line 525 of file tiny.h.
|
inlinenoexcept |
|
inlinenoexcept |
|
inline |
Inserts a new element into the container by constructing it in-place with the given args if there is no element with the key in the container.
Definition at line 607 of file tiny.h.
Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::emplace_hint(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::insert().
|
inline |
Do the same as emplace, and ignore the hint.
Definition at line 616 of file tiny.h.
|
inlinenoexcept |
|
inlinenoexcept |
Returns an iterator to the element following the last element of the container.
Definition at line 249 of file tiny.h.
Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::count(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::find().
|
inlinenoexcept |
|
inlinenoexcept |
Returns a range containing all elements with the given key in the container.
The range is defined by two iterators, one pointing to the first element that is not less than key and another pointing to the first element greater than key.
Definition at line 369 of file tiny.h.
Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::count(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::erase().
|
inlinenoexcept |
Returns a range containing all elements with the given key in the container.
The range is defined by two iterators, one pointing to the first element that is not less than key and another pointing to the first element greater than key.
|
inline |
Removes the element at pos.
Definition at line 306 of file tiny.h.
Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::erase().
|
inline |
Removes the elements in the range [first; last), which must be a valid range in *this.
Definition at line 317 of file tiny.h.
|
inline |
Removes all elements with the key value key.
Definition at line 327 of file tiny.h.
|
inlinenoexcept |
Finds an element with key equivalent to key.
If no such element is found, past-the-end iterator is returned.
Definition at line 347 of file tiny.h.
|
inlinenoexcept |
Finds an element with key equivalent to key.
If no such element is found, past-the-end iterator is returned.
Definition at line 357 of file tiny.h.
|
inline |
|
inline |
Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.
Definition at line 545 of file tiny.h.
Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::insert(), tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::operator=(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::set_impl().
|
inline |
Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.
Definition at line 560 of file tiny.h.
|
inline |
Does the same as normal insert, we ignore the hint.
Definition at line 567 of file tiny.h.
|
inline |
Does the same as normal insert, we ignore the hint.
Definition at line 575 of file tiny.h.
|
inline |
Inserts elements from range [first, last).
Definition at line 583 of file tiny.h.
|
inline |
Inserts elements from initializer list ilist.
Definition at line 592 of file tiny.h.
|
inlinenoexcept |
|
inlinenoexcept |
Returns an iterator pointing to the first element that is not less than key.
Definition at line 387 of file tiny.h.
Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::count(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::find().
|
inlinenoexcept |
|
inlinenoexcept |
|
inline |
|
inline |
|
inline |
Replaces the contents with those identified by initializer list ilist.
Definition at line 462 of file tiny.h.
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
|
inline |
Increase the capacity of the container to a value that's greater or equal to new_cap.
If new_cap is greater than the current capacity(), new storage is allocated, otherwise the method does nothing.
|
inline |
|
inlinenoexcept |
Returns the number of elements in the container, i.e.
Definition at line 288 of file tiny.h.
Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::erase(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, Comp, Alloc, bits::SingleInsertHelp >::insert().
|
inline |
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |