class implementing a tiny::set, tiny::multiset, and tiny::multimap. More...

#include <tpie/tiny.h>

Classes
struct	value_compare

Public Types
typedef T	value_type

typedef Key	key_type

typedef Inner::iterator	iterator

typedef Inner::const_iterator	const_iterator

typedef Inner::reverse_iterator	reverse_iterator

typedef Inner::const_reverse_iterator	const_reverse_iterator

typedef Comp	key_compare

typedef Alloc	allocator_type

typedef IH::result	insert_result

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...

template<typename K >
iterator	lower_bound (const K &key) noexcept
	Returns an iterator pointing to the first element that is not less than key. More...

template<typename K >
const_iterator	lower_bound (const K &key) const noexcept
	Returns an iterator pointing to the first element that is not less than key. More...

template<typename K >
iterator	upper_bound (const K &key) noexcept
	Returns an iterator pointing to the first element that is greater than key. More...

template<typename K >
const_iterator	upper_bound (const K &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...

Detailed Description

template<typename T, typename Key, typename KeyExtract, typename Comp, typename Alloc, typename InsertHelp>
class tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >

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.

Definition at line 137 of file tiny.h.

Constructor & Destructor Documentation

◆ set_impl() [1/9]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::set_impl ( )

inline

Default constructor.

Constructs empty container.

Definition at line 165 of file tiny.h.

165 : comp(Comp()) {}

◆ set_impl() [2/9]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::set_impl	(	const Comp &	comp,
		const Alloc &	alloc = `Alloc()`
	)

inlineexplicit

Default constructor.

Constructs empty container.

Definition at line 170 of file tiny.h.

170 : comp(comp), inner(alloc) {}

◆ set_impl() [3/9]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::set_impl ( const Alloc & alloc )

inlineexplicit

Default constructor.

Constructs empty container.

Definition at line 175 of file tiny.h.

175 : inner(alloc) {}

◆ set_impl() [4/9]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::set_impl ( const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > & other )

inline

Copy constructor.

Constructs the container with the copy of the contents of other.

Definition at line 180 of file tiny.h.

180 : comp(other.comp), inner(other.inner) {}

◆ set_impl() [5/9]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::set_impl	(	const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	other,
		const Alloc &	alloc
	)

inline

Copy constructor.

Constructs the container with the copy of the contents of other.

Definition at line 185 of file tiny.h.

185 : comp(other.comp), inner(other.inner, alloc) {}

◆ set_impl() [6/9]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::set_impl ( set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > && other )

inline

Move constructor.

Constructs the container with the contents of other using move semantics.

Definition at line 190 of file tiny.h.

190 : comp(std::move(other.comp)), inner(std::move(other.inner)) {}

◆ set_impl() [7/9]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::set_impl	(	set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &&	other,
		const Alloc &	alloc
	)

inline

Move constructor.

Constructs the container with the contents of other using move semantics.

Definition at line 195 of file tiny.h.

195 : comp(std::move(other.comp)), inner(std::move(other.inner), alloc) {}

◆ set_impl() [8/9]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

template<class InputIterator >

tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::set_impl	(	InputIterator	first,
		InputIterator	last,
		const Comp &	comp = `Comp()`,
		const Alloc &	alloc = `Alloc()`
	)

inline

Constructs the container with the contents of the range [first, last).

Definition at line 201 of file tiny.h.

                                           : comp(comp), inner(alloc) {
         insert(first, last);
     }

◆ set_impl() [9/9]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::set_impl	(	std::initializer_list< value_type >	init,
		const Comp &	comp = `Comp()`,
		const Alloc &	alloc = `Alloc()`
	)

inline

Constructs the container with the contents of the initializer list init.

Definition at line 210 of file tiny.h.

                                                   : comp(comp), inner(alloc) {
         insert(init);
     }

Member Function Documentation

◆ begin() [1/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::begin ( ) const

inlinenoexcept

Returns an iterator to the first element of the container.

Definition at line 224 of file tiny.h.

224 {return inner.cbegin();}

◆ begin() [2/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::begin ( )

inlinenoexcept

Returns an iterator to the first element of the container.

Definition at line 219 of file tiny.h.

219 {return inner.begin();}

Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::erase().

◆ capacity()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

size_t tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::capacity ( ) const

inlinenoexcept

Returns the number of elements that the container has currently allocated space for.

Definition at line 675 of file tiny.h.

675 {return inner.capacity();}

◆ cbegin()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::cbegin ( ) const

inlinenoexcept

Returns an iterator to the first element of the container.

Definition at line 229 of file tiny.h.

229 {return inner.cbegin();}

◆ cend()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::cend ( ) const

inlinenoexcept

Returns an iterator to the element following the last element of the container.

Definition at line 259 of file tiny.h.

259 {return inner.cend();}

◆ clear()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

void tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::clear ( )

inline

Removes all elements from the container.

Definition at line 300 of file tiny.h.

300 {inner.clear(); }

Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::operator=().

◆ count()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

size_t tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::count ( const Key k ) const

inlinenoexcept

Returns the number of elements with key k.

Definition at line 563 of file tiny.h.

                                              {
         if (IH::multi) {
             auto x=equal_range(k);
             return x.second - x.first;
         } else {
             auto x=lower_bound(k);
             if (x == end() || comp(k, *x)) return 0;
             return 1;
         }
     }

◆ crbegin()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_reverse_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::crbegin ( ) const

inlinenoexcept

Returns a reverse iterator to the first element of the reversed container.

Definition at line 244 of file tiny.h.

244 {return inner.rbegin();}

◆ crend()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_reverse_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::crend ( ) const

inlinenoexcept

Returns a reverse iterator to the element following the last element of the reversed container.

Definition at line 277 of file tiny.h.

277 {return inner.rend();}

◆ emplace()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

template<class... Args>

insert_result tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::emplace ( Args &&... args )

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.

Returns: Returns a pair consisting of an iterator to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place.

Definition at line 645 of file tiny.h.

                                            {
         inner.emplace_back(std::forward<Args>(args)...);
         return IH::handle(inner, comp);
     }

Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::emplace_hint(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::insert().

◆ emplace_hint()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

template<class... Args>

insert_result tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::emplace_hint	(	const_iterator	,
		Args &&...	args
	)

inline

Do the same as emplace, and ignore the hint.

Definition at line 654 of file tiny.h.

                                                                   {
         return emplace(std::forward<Args>(args)...);
     }

◆ empty()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

bool tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::empty ( ) const

inlinenoexcept

Checks if the container has no elements, i.e.

whether begin() == end().

Definition at line 283 of file tiny.h.

283 {return inner.empty();}

◆ end() [1/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::end ( ) const

inlinenoexcept

Returns an iterator to the element following the last element of the container.

Definition at line 254 of file tiny.h.

254 {return inner.cend();}

◆ end() [2/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::end ( )

inlinenoexcept

Returns an iterator to the element following the last element of the container.

Definition at line 249 of file tiny.h.

249 {return inner.end();}

Referenced by tpie::tiny::map< Key, T, Comp, Alloc >::at(), tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::count(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::find().

◆ equal_range() [1/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

std::pair<const_iterator, const_iterator> tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::equal_range ( const Key & key ) const

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 380 of file tiny.h.

                                                                                         {
         return std::equal_range(inner.begin(), inner.end(), key, comp);
     }

◆ equal_range() [2/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

std::pair<iterator, iterator> tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::equal_range ( const Key & key )

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 370 of file tiny.h.

                                                                       {
         return std::equal_range(inner.begin(), inner.end(), key, comp);
     }

Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::count(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::erase().

◆ erase() [1/3]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

size_t tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::erase ( const Key & key )

inline

Removes all elements with the key value key.

Returns: Number of elements removed.

Definition at line 327 of file tiny.h.

                                   {
         auto x=equal_range(key);
         auto res = x.second - x.first;
         erase(x.first, x.second);
         return res;
     }

◆ erase() [2/3]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::erase	(	iterator	first,
		iterator	last
	)

inline

Removes the elements in the range [first; last), which must be a valid range in *this.

Returns: Iterator following the last removed element.

Definition at line 317 of file tiny.h.

                                                   {
         std::rotate(first, last, inner.end());
         inner.resize(size() - (last-first));
         return begin();
     }

◆ erase() [3/3]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::erase ( iterator pos )

inline

Removes the element at pos.

Returns: Iterator following the last removed element.

Definition at line 306 of file tiny.h.

                                  {
         std::rotate(pos, std::next(pos), inner.end());
         inner.pop_back();
         return pos;
     }

Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::erase().

◆ find() [1/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::find ( const Key & key ) const

inlinenoexcept

Finds an element with key equivalent to key.

If no such element is found, past-the-end iterator is returned.

Definition at line 358 of file tiny.h.

                                                         {
         const_iterator x=lower_bound(key);
         if (x == end() || comp(key, *x)) return end();
         return x;
     }

◆ find() [2/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::find ( const Key & key )

inlinenoexcept

Finds an element with key equivalent to key.

If no such element is found, past-the-end iterator is returned.

Definition at line 348 of file tiny.h.

                                             {
         iterator x=lower_bound(key);
         if (x == end() || comp(key, *x)) return end();
         return x;
     }

◆ get_allocator()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

allocator_type tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::get_allocator ( ) const

inline

Returns the allocator associated with the container.

Definition at line 473 of file tiny.h.

                                          {
         return inner.get_allocator();
     }

◆ insert() [1/6]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

insert_result tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::insert ( const T & t )

inline

Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.

Returns: Returns a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

Definition at line 583 of file tiny.h.

                                       {
         inner.push_back(t);
         return IH::handle(inner, comp);
     }

Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::insert(), tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::operator=(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::set_impl().

◆ insert() [2/6]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

insert_result tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::insert	(	const_iterator	,
		const T &	t
	)

inline

Does the same as normal insert, we ignore the hint.

Definition at line 605 of file tiny.h.

                                                         {
         return insert(t);
     }

◆ insert() [3/6]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

template<typename TT >

insert_result tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::insert	(	const_iterator	,
		TT &&	t
	)

inline

Does the same as normal insert, we ignore the hint.

Definition at line 613 of file tiny.h.

                                                     {
         return insert(std::forward<TT>(t));
     }

◆ insert() [4/6]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

template<class InputIt >

void tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::insert	(	InputIt	first,
		InputIt	last
	)

inline

Inserts elements from range [first, last).

Definition at line 621 of file tiny.h.

                                              {
         inner.reserve(size() + last-first);
         for (InputIt i=first; i != last; ++i)
             insert(*i);
     }

◆ insert() [5/6]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

void tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::insert ( std::initializer_list< value_type > list )

inline

Inserts elements from initializer list ilist.

Definition at line 630 of file tiny.h.

                                                       {
         insert(list.begin(), list.end());
     }

◆ insert() [6/6]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

template<typename TT >

insert_result tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::insert ( TT && t )

inline

Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.

Returns: Returns a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

Definition at line 598 of file tiny.h.

                                   {
         return emplace(std::forward<TT>(t));
     }

◆ key_comp()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

key_compare tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::key_comp ( ) const

inlinenoexcept

Returns the function object that compares the keys, which is a copy of this container's constructor argument comp.

Definition at line 457 of file tiny.h.

                                           {
         return comp.comp;
     }

◆ lower_bound() [1/4]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

template<typename K >

const_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::lower_bound ( const K & key ) const

inlinenoexcept

Returns an iterator pointing to the first element that is not less than key.

Definition at line 430 of file tiny.h.

                                                              {
         return std::lower_bound(inner.begin(), inner.end(), key, comp);
     }

◆ lower_bound() [2/4]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

template<typename K >

iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::lower_bound ( const K & key )

inlinenoexcept

Returns an iterator pointing to the first element that is not less than key.

Definition at line 421 of file tiny.h.

                                                  {
         return std::lower_bound(inner.begin(), inner.end(), key, comp);
     }

◆ lower_bound() [3/4]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::lower_bound ( const Key & key ) const

inlinenoexcept

Returns an iterator pointing to the first element that is not less than key.

Definition at line 396 of file tiny.h.

                                                                {
         return std::lower_bound(inner.begin(), inner.end(), key, comp);
     }

◆ lower_bound() [4/4]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::lower_bound ( const Key & key )

inlinenoexcept

Returns an iterator pointing to the first element that is not less than key.

Definition at line 388 of file tiny.h.

                                                    {
         return std::lower_bound(inner.begin(), inner.end(), key, comp);
     }

Referenced by tpie::tiny::map< Key, T, Comp, Alloc >::at(), tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::count(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::find().

◆ max_size()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

size_t tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::max_size ( ) const

inlinenoexcept

Returns the maximum number of elements the container is able to hold due to system or library implementation limitations.

Definition at line 295 of file tiny.h.

295 {return inner.max_size();}

◆ operator=() [1/3]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

set_impl& tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::operator= ( const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > & other )

inline

Copy assignment operator.

Replaces the contents with a copy of the contents of other.

Definition at line 480 of file tiny.h.

                                                  {
         inner = other.inner;
         comp = other.comp;
         return *this;
     }

◆ operator=() [2/3]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

set_impl& tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::operator= ( set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > && other )

inline

Move assignment operator.

Replaces the contents with those of other using move semantics (i.e. the data in other is moved from other into this container)

Definition at line 491 of file tiny.h.

                                             {
         inner = std::move(other.inner);
         comp = std::move(other.comp);
         return *this;
     }

◆ operator=() [3/3]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

set_impl& tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::operator= ( std::initializer_list< value_type > ilist )

inline

Replaces the contents with those identified by initializer list ilist.

Definition at line 500 of file tiny.h.

                                                                {
         clear();
         insert(ilist);
         return *this;
     }

◆ rbegin() [1/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_reverse_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::rbegin ( ) const

inlinenoexcept

Returns a reverse iterator to the first element of the reversed container.

Definition at line 239 of file tiny.h.

239 {return inner.rbegin();}

◆ rbegin() [2/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

reverse_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::rbegin ( )

inlinenoexcept

Returns a reverse iterator to the first element of the reversed container.

Definition at line 234 of file tiny.h.

234 {return inner.rbegin();}

◆ rend() [1/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_reverse_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::rend ( ) const

inlinenoexcept

Returns a reverse iterator to the element following the last element of the reversed container.

Definition at line 271 of file tiny.h.

271 {return inner.rend();}

◆ rend() [2/2]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

reverse_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::rend ( )

inlinenoexcept

Returns a reverse iterator to the element following the last element of the reversed container.

Definition at line 265 of file tiny.h.

265 {return inner.rend();}

◆ reserve()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

void tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::reserve ( size_t new_cap )

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.

Definition at line 664 of file tiny.h.

664 {inner.reserve(new_cap);}

◆ shrink_to_fit()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

void tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::shrink_to_fit ( )

inline

Requests the removal of unused capacity.

Definition at line 669 of file tiny.h.

669 {inner.shrink_to_fit();}

◆ size()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

size_t tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::size ( ) const

inlinenoexcept

Returns the number of elements in the container, i.e.

std::distance(begin(), end())

Definition at line 288 of file tiny.h.

288 {return inner.size();}

Referenced by tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::erase(), and tpie::tiny::set_impl< std::pair< Key, T >, T, bits::PairExtract< Key, T >, std::less< Key >, std::allocator< std::pair< Key, T > >, bits::SingleInsertHelp >::insert().

◆ swap()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

void tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::swap ( set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > & o )

inline

Exchanges the contents of the container with those of other.

Does not invoke any move, copy, or swap operations on individual elements.

Definition at line 339 of file tiny.h.

                             {
         std::swap(comp, o.comp);
         std::swap(inner, o.inner);
     }

◆ upper_bound() [1/4]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

template<typename K >

const_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::upper_bound ( const K & key ) const

inlinenoexcept

Returns an iterator pointing to the first element that is greater than key.

Definition at line 448 of file tiny.h.

                                                              {
         return std::upper_bound(inner.begin(), inner.end(), key, comp);
     }

◆ upper_bound() [2/4]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

template<typename K >

iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::upper_bound ( const K & key )

inlinenoexcept

Returns an iterator pointing to the first element that is greater than key.

Definition at line 439 of file tiny.h.

                                                  {
         return std::upper_bound(inner.begin(), inner.end(), key, comp);
     }

◆ upper_bound() [3/4]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

const_iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::upper_bound ( const Key & key ) const

inlinenoexcept

Returns an iterator pointing to the first element that is greater than key.

Definition at line 412 of file tiny.h.

                                                                {
         return std::upper_bound(inner.begin(), inner.end(), key, comp);
     }

◆ upper_bound() [4/4]

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

iterator tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::upper_bound ( const Key & key )

inlinenoexcept

Returns an iterator pointing to the first element that is greater than key.

Definition at line 404 of file tiny.h.

                                                    {
         return std::upper_bound(inner.begin(), inner.end(), key, comp);
     }

◆ value_comp()

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

value_compare tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >::value_comp ( ) const

inlinenoexcept

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.

Definition at line 466 of file tiny.h.

                                               {
         return comp;
     }

Friends And Related Function Documentation

◆ operator!=

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

bool operator!=	(	const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	lhs,
		const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	rhs
	)

friend

true if the contents of the containers are not equal, false otherwise.

Definition at line 516 of file tiny.h.

                                                                        {
         return lhs.inner != rhs.inner;
     }

◆ operator<

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

bool operator<	(	const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	lhs,
		const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	rhs
	)

friend

true if the contents of the lhs are lexicographically less than the contents of rhs, false otherwise.

Definition at line 524 of file tiny.h.

                                                                       {
         return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), lhs.comp);
     }

◆ operator<=

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

bool operator<=	(	const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	lhs,
		const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	rhs
	)

friend

true if the contents of the lhs are lexicographically less than or equal the contents of rhs, false otherwise.

Definition at line 532 of file tiny.h.

                                                                        {
         return !std::lexicographical_compare(rhs.begin(), rhs.end(), lhs.begin(), lhs.end());
         
     }

◆ operator==

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

bool operator==	(	const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	lhs,
		const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	rhs
	)

friend

true if the contents of the containers are equal, false otherwise.

Definition at line 509 of file tiny.h.

                                                                        {
         return lhs.inner == rhs.inner;
     }

◆ operator>

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

bool operator>	(	const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	lhs,
		const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	rhs
	)

friend

true if the contents of the lhs are lexicographically greater than the contents of rhs, false otherwise.

Definition at line 541 of file tiny.h.

                                                                       {
         return std::lexicographical_compare(rhs.begin(), rhs.end(), lhs.begin(), lhs.end());
     }

◆ operator>=

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

bool operator>=	(	const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	lhs,
		const set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	rhs
	)

friend

true if the contents of the lhs are lexicographically greater than or equal the contents of rhs, false otherwise.

Definition at line 549 of file tiny.h.

                                                                        {
         return !std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), lhs.comp);
     }

◆ swap

template<typename T , typename Key , typename KeyExtract , typename Comp , typename Alloc , typename InsertHelp >

void swap	(	set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	lhs,
		set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp > &	rhs
	)

friend

Specializes the std::swap algorithm using adl.

Swaps the contents of lhs and rhs. Calls lhs.swap(rhs).

Definition at line 557 of file tiny.h.

557 {lhs.swap(rhs);}

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

tiny.h

TPIE

Classes

Public Types

Public Member Functions

Protected Types

Protected Attributes

Friends

Detailed Description

template<typename T, typename Key, typename KeyExtract, typename Comp, typename Alloc, typename InsertHelp> class tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >

Constructor & Destructor Documentation

◆ set_impl() [1/9]

◆ set_impl() [2/9]

◆ set_impl() [3/9]

◆ set_impl() [4/9]

◆ set_impl() [5/9]

◆ set_impl() [6/9]

◆ set_impl() [7/9]

◆ set_impl() [8/9]

◆ set_impl() [9/9]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ capacity()

◆ cbegin()

◆ cend()

◆ clear()

◆ count()

◆ crbegin()

◆ crend()

◆ emplace()

◆ emplace_hint()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equal_range() [1/2]

◆ equal_range() [2/2]

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find() [1/2]

◆ find() [2/2]

◆ get_allocator()

◆ insert() [1/6]

◆ insert() [2/6]

◆ insert() [3/6]

◆ insert() [4/6]

◆ insert() [5/6]

◆ insert() [6/6]

◆ key_comp()

◆ lower_bound() [1/4]

◆ lower_bound() [2/4]

◆ lower_bound() [3/4]

◆ lower_bound() [4/4]

◆ max_size()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ reserve()

◆ shrink_to_fit()

◆ size()

◆ swap()

◆ upper_bound() [1/4]

◆ upper_bound() [2/4]

◆ upper_bound() [3/4]

◆ upper_bound() [4/4]

◆ value_comp()

Friends And Related Function Documentation

◆ operator!=

◆ operator<

◆ operator<=

◆ operator==

◆ operator>

◆ operator>=

◆ swap

template<typename T, typename Key, typename KeyExtract, typename Comp, typename Alloc, typename InsertHelp>
class tpie::tiny::set_impl< T, Key, KeyExtract, Comp, Alloc, InsertHelp >