Aim: Represents a map label -> data, where the label is an integer between 0 and a constant L-1. It is based on a binary coding of labels and a mixed list/array structure. The assumption is that the number of used labels is much less than L. The objective is to minimize the memory usage. More...

#include <DGtal/base/LabelledMap.h>

Data Structures
struct	__AnyBlock

struct	__FirstBlock

class	BlockConstIterator

class	BlockIterator

union	BlockPointer
	Forward declaration. More...

class	ConstIterator

union	DataOrBlockPointer
	Used in first block to finish it or to point to the next block. More...

class	KeyCompare
	Key comparator class. Always natural ordering. More...

class	ValueCompare
	Value comparator class. Always natural ordering between keys. More...

Public Types
typedef LabelledMap< TData, L, TWord, N, M >	Self

typedef TData	Data

typedef TWord	Word

typedef Labels< L, Word >	LabelsType

typedef LabelsType::Label	Label

typedef Label	Key

typedef std::pair< const Key, Data >	Value

typedef LabelsType::ConstIterator	LabelsConstIterator

typedef std::ptrdiff_t	DifferenceType

typedef std::size_t	SizeType

typedef Value &	Reference

typedef Value *	Pointer

typedef const Value &	ConstReference

typedef const Value *	ConstPointer

typedef Key	key_type
	Forward declaration. More...

typedef Value	value_type

typedef Data	data_type

typedef Data	mapped_type

typedef DifferenceType	difference_type

typedef Reference	reference

typedef Pointer	pointer

typedef ConstReference	const_reference

typedef ConstPointer	const_pointer

typedef SizeType	size_type

typedef ConstIterator	iterator

typedef ConstIterator	const_iterator

typedef KeyCompare	key_compare

typedef ValueCompare	value_compare

typedef ConstIterator	Iterator
	non-mutable class via iterators. More...

Public Member Functions
	LabelledMap ()

	LabelledMap (const LabelledMap &other)

template<typename InputIterator >
	LabelledMap (InputIterator first, InputIterator last)

LabelledMap &	operator= (const LabelledMap &other)

	~LabelledMap ()

const LabelsType &	labels () const

SizeType	size () const

bool	empty () const

SizeType	max_size () const

SizeType	capacity () const

KeyCompare	key_comp () const

ValueCompare	value_comp () const

void	swap (Self &other)

void	clear ()

SizeType	count (const Key &key) const

Data &	operator[] (const Key &key)

const Data &	operator[] (const Key &key) const

Data &	fastAt (const Key &key)

const Data &	fastAt (const Key &key) const

std::pair< Iterator, bool >	insert (const Value &val)

Iterator	insert (Iterator position, const Value &val)

template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)

void	erase (Iterator position)

SizeType	erase (Key key)

void	erase (Iterator first, Iterator last)

ConstIterator	begin () const

ConstIterator	end () const

Iterator	begin ()

Iterator	end ()

std::pair< Iterator, Iterator >	equal_range (const Key &x)

std::pair< ConstIterator, ConstIterator >	equal_range (const Key &x) const

Iterator	find (const Key &x)

ConstIterator	find (const Key &x) const

Iterator	lower_bound (const Key &x)

ConstIterator	lower_bound (const Key &x) const

Iterator	upper_bound (const Key &x)

ConstIterator	upper_bound (const Key &x) const

void	blockClear (size_t size)

Data &	blockAt (size_t idx)

const Data &	blockAt (size_t idx) const

Data &	blockInsert (size_t idx, size_t block_size, const Data &data)

void	blockErase (size_t idx)

BlockIterator	blockBegin ()

BlockIterator	blockEnd ()

BlockConstIterator	blockBegin () const

BlockConstIterator	blockEnd () const

void	selfDisplay (std::ostream &out) const

bool	isValid () const

Private Member Functions
	BOOST_STATIC_ASSERT (L >=1)

	BOOST_STATIC_ASSERT (N >=0)

	BOOST_STATIC_ASSERT (M >=2)

Private Attributes
LabelsType	myLabels
	Stores the labels for this sequence of datas. More...

__FirstBlock	myFirstBlock

Detailed Description

template<typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
class DGtal::LabelledMap< TData, L, TWord, N, M >

Aim: Represents a map label -> data, where the label is an integer between 0 and a constant L-1. It is based on a binary coding of labels and a mixed list/array structure. The assumption is that the number of used labels is much less than L. The objective is to minimize the memory usage.

Description of template class 'LabelledMap'

Model of boost::AssociativeContainer, boost::PairAssociativeContainer, boost::UniqueAssociativeContainer. As such, it is refinement of boost::ForwardContainer and boost::Container. It is also a model of boost::Assignable, boost::CopyConstructible.

V[ 0 ] is the data of the first set label.
V[ 1 ] is the data of the second set label.
...

if less than 4 datas and N = 3
+------+------+------+------+------+
|labels| V[0] | V[1] | ...  |  0   |
+------+------+------+------+------+

if only 4 datas and N = 3
+------+------+------+------+------+
|labels| V[0] | V[1] | V[2] | V[3] |
+------+------+------+------+------+

if more than 4 datas and N = 3, M = 4
+------+------+------+------+------+        +------+------+------+------+------+
|labels| V[0] | V[1] | V[2] | ptr --------> | V[3] | V[4] | V[5] | V[6] | ptr --------> ...
+------+------+------+------+------+        +------+------+------+------+------+

This structure is related to the IndexedListWithBlocks, except that it stores the mapping label -> index. The (maximum) number of possible labels is fixed at instantiation for optimisation purposes.

Such a structure is useful when:

the expected size of this container is small, but may sometimes increase.
the user wishes sometimes to insert a new data or erase another data.
the user wishes to have an access to the datas that is as fast as possible given a valid label.
one wishes to limit as possible the memory usage.
generally this structure is embedded as the data of a big array.

Model of boost::PairAssociativeContainer and boost::SimpleAssociativeContainer.

Template Parameters

TData	the type for the datas stored in the list.
L	the maximum number of labels.
TWord	the integer used to store the labels (if L >= log_2( digits( TWord ) ) then several consecutive words are stored.), e.g. DGtal::uint8_t.
N	the number of data stored in the first block.
M	the number of data stored in the further blocks.

NB: In the following, we use the notations

n is the size of the container
b is the number of blocks ( b = 1 + (size()-N) / M ).

Definition at line 119 of file LabelledMap.h.

Member Typedef Documentation

◆ const_iterator

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef ConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::const_iterator

Definition at line 159 of file LabelledMap.h.

◆ const_pointer

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef ConstPointer DGtal::LabelledMap< TData, L, TWord, N, M >::const_pointer

Definition at line 156 of file LabelledMap.h.

◆ const_reference

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef ConstReference DGtal::LabelledMap< TData, L, TWord, N, M >::const_reference

Definition at line 155 of file LabelledMap.h.

◆ ConstPointer

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef const Value* DGtal::LabelledMap< TData, L, TWord, N, M >::ConstPointer

Definition at line 141 of file LabelledMap.h.

◆ ConstReference

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef const Value& DGtal::LabelledMap< TData, L, TWord, N, M >::ConstReference

Definition at line 140 of file LabelledMap.h.

◆ Data

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef TData DGtal::LabelledMap< TData, L, TWord, N, M >::Data

Definition at line 127 of file LabelledMap.h.

◆ data_type

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef Data DGtal::LabelledMap< TData, L, TWord, N, M >::data_type

Definition at line 150 of file LabelledMap.h.

◆ difference_type

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef DifferenceType DGtal::LabelledMap< TData, L, TWord, N, M >::difference_type

Definition at line 152 of file LabelledMap.h.

◆ DifferenceType

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef std::ptrdiff_t DGtal::LabelledMap< TData, L, TWord, N, M >::DifferenceType

Definition at line 136 of file LabelledMap.h.

◆ iterator

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef ConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::iterator

Definition at line 158 of file LabelledMap.h.

◆ Iterator

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef ConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::Iterator

non-mutable class via iterators.

Definition at line 730 of file LabelledMap.h.

◆ Key

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef Label DGtal::LabelledMap< TData, L, TWord, N, M >::Key

Definition at line 131 of file LabelledMap.h.

◆ key_compare

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef KeyCompare DGtal::LabelledMap< TData, L, TWord, N, M >::key_compare

Definition at line 160 of file LabelledMap.h.

◆ key_type

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef Key DGtal::LabelledMap< TData, L, TWord, N, M >::key_type

Forward declaration.

Definition at line 148 of file LabelledMap.h.

◆ Label

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef LabelsType::Label DGtal::LabelledMap< TData, L, TWord, N, M >::Label

Definition at line 130 of file LabelledMap.h.

◆ LabelsConstIterator

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef LabelsType::ConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::LabelsConstIterator

Definition at line 135 of file LabelledMap.h.

◆ LabelsType

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef Labels<L, Word> DGtal::LabelledMap< TData, L, TWord, N, M >::LabelsType

Definition at line 129 of file LabelledMap.h.

◆ mapped_type

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef Data DGtal::LabelledMap< TData, L, TWord, N, M >::mapped_type

Definition at line 151 of file LabelledMap.h.

◆ Pointer

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef Value* DGtal::LabelledMap< TData, L, TWord, N, M >::Pointer

Definition at line 139 of file LabelledMap.h.

◆ pointer

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef Pointer DGtal::LabelledMap< TData, L, TWord, N, M >::pointer

Definition at line 154 of file LabelledMap.h.

◆ Reference

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef Value& DGtal::LabelledMap< TData, L, TWord, N, M >::Reference

Definition at line 138 of file LabelledMap.h.

◆ reference

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef Reference DGtal::LabelledMap< TData, L, TWord, N, M >::reference

Definition at line 153 of file LabelledMap.h.

◆ Self

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef LabelledMap<TData, L, TWord, N, M> DGtal::LabelledMap< TData, L, TWord, N, M >::Self

Definition at line 126 of file LabelledMap.h.

◆ size_type

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef SizeType DGtal::LabelledMap< TData, L, TWord, N, M >::size_type

Definition at line 157 of file LabelledMap.h.

◆ SizeType

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef std::size_t DGtal::LabelledMap< TData, L, TWord, N, M >::SizeType

Definition at line 137 of file LabelledMap.h.

◆ Value

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef std::pair<const Key, Data> DGtal::LabelledMap< TData, L, TWord, N, M >::Value

Definition at line 132 of file LabelledMap.h.

◆ value_compare

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef ValueCompare DGtal::LabelledMap< TData, L, TWord, N, M >::value_compare

Definition at line 161 of file LabelledMap.h.

◆ value_type

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef Value DGtal::LabelledMap< TData, L, TWord, N, M >::value_type

Definition at line 149 of file LabelledMap.h.

◆ Word

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

typedef TWord DGtal::LabelledMap< TData, L, TWord, N, M >::Word

Definition at line 128 of file LabelledMap.h.

Constructor & Destructor Documentation

◆ LabelledMap() [1/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

DGtal::LabelledMap< TData, L, TWord, N, M >::LabelledMap ( )

Constructor.

◆ LabelledMap() [2/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

DGtal::LabelledMap< TData, L, TWord, N, M >::LabelledMap ( const LabelledMap< TData, L, TWord, N, M > & other )

Copy constructor.

Parameters

other the object to clone.

◆ LabelledMap() [3/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

template<typename InputIterator >

DGtal::LabelledMap< TData, L, TWord, N, M >::LabelledMap	(	InputIterator	first,
		InputIterator	last
	)

Constructor from range.

Template Parameters

InputIterator model of boost::InputIterator whose value type is convertible to Value.

Parameters

first	an iterator on the first value of the range.
last	an iterator after the last value of the range.

◆ ~LabelledMap()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

DGtal::LabelledMap< TData, L, TWord, N, M >::~LabelledMap ( )

Destructor.

Member Function Documentation

◆ begin() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

Iterator DGtal::LabelledMap< TData, L, TWord, N, M >::begin ( )

Returns: an iterator pointing on the first element in the container.

◆ begin() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

ConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::begin ( ) const

Returns: an iterator pointing on the first element in the container.

◆ blockAt() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

Data & DGtal::LabelledMap< TData, L, TWord, N, M >::blockAt ( size_t idx )

Random unprotected read-write access to data at position idx

Parameters

idx	the index of the data in the container.

Returns: a reference on the data.

Precondition: idx < size() NB: O( b ), E = O( 1 + ceil( ( idx - N ) / M ) )

◆ blockAt() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

const Data & DGtal::LabelledMap< TData, L, TWord, N, M >::blockAt ( size_t idx ) const

Random unprotected read access to data at position idx

Parameters

idx	the index of the data in the container.

Returns: a const reference on the data.

Precondition: idx < size() NB: O( b ), E = O( 1 + ceil( ( idx - N ) / M ) )

◆ blockBegin() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

BlockIterator DGtal::LabelledMap< TData, L, TWord, N, M >::blockBegin ( )

Returns: an iterator pointing on the first element in the container.

◆ blockBegin() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

BlockConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::blockBegin ( ) const

Returns: an iterator pointing on the first element in the container.

◆ blockClear()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

void DGtal::LabelledMap< TData, L, TWord, N, M >::blockClear ( size_t size )

Removes all the datas stored in the block structure.

Parameters

size	must be the current size of the block structure.

◆ blockEnd() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

BlockIterator DGtal::LabelledMap< TData, L, TWord, N, M >::blockEnd ( )

Returns: an iterator pointing after the last element in the container.

◆ blockEnd() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

BlockConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::blockEnd ( ) const

Returns: an iterator pointing after the last element in the container.

◆ blockErase()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

void DGtal::LabelledMap< TData, L, TWord, N, M >::blockErase ( size_t idx )

Removal of a data at a given position. Following datas are shifted.

Parameters

idx	the index of the data in the container.

Precondition: idx < size() NB: O( n ), E = O( n - idx )

◆ blockInsert()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

Data & DGtal::LabelledMap< TData, L, TWord, N, M >::blockInsert	(	size_t	idx,
		size_t	block_size,
		const Data &	data
	)

Insertion of a new data at given position. The former data at this position and the next ones are shifted.

Parameters

idx	the index of the data in the container.

Precondition: idx <= size() (if size(), inserts at the end.

Parameters

block_size	the block size.
data	the data to insert. NB: O( n ), E = O( n - idx )

◆ BOOST_STATIC_ASSERT() [1/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

DGtal::LabelledMap< TData, L, TWord, N, M >::BOOST_STATIC_ASSERT ( L >= 1 )

private

◆ BOOST_STATIC_ASSERT() [2/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

DGtal::LabelledMap< TData, L, TWord, N, M >::BOOST_STATIC_ASSERT ( M >= 2 )

private

◆ BOOST_STATIC_ASSERT() [3/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

DGtal::LabelledMap< TData, L, TWord, N, M >::BOOST_STATIC_ASSERT ( N >= 0 )

private

◆ capacity()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

SizeType DGtal::LabelledMap< TData, L, TWord, N, M >::capacity ( ) const

The number of datas currently allocated in the structure.

◆ clear()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

void DGtal::LabelledMap< TData, L, TWord, N, M >::clear ( )

Removes all the datas stored in the structure.

◆ count()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

SizeType DGtal::LabelledMap< TData, L, TWord, N, M >::count ( const Key & key ) const

Follows std::count.

Parameters

key any label

Returns: 0 if the key is not present in container, 1 otherwise.

◆ empty()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

bool DGtal::LabelledMap< TData, L, TWord, N, M >::empty ( ) const

Returns: 'true' if and only if the container is empty. O(1)

◆ end() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

Iterator DGtal::LabelledMap< TData, L, TWord, N, M >::end ( )

Returns: an iterator pointing after the last element in the container.

◆ end() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

ConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::end ( ) const

Returns: an iterator pointing after the last element in the container.

◆ equal_range() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

std::pair< Iterator, Iterator > DGtal::LabelledMap< TData, L, TWord, N, M >::equal_range ( const Key & x )

Get range of equal elements.

Returns the bounds of a range that includes all the elements in the container with a key that compares equal to x. Here, the range will include one element at most.

If x does not match any key in the container, the range returned has a length of zero, with both iterators pointing to the element with nearest key greater than x, if any, or to map::end if x is greater than all the elements in the container.

Parameters

x	any key in 0..L-1

Returns: a pair, where its member pair::first is an iterator to the lower bound of the range with the same value as the one that would be returned by lower_bound(x), and pair::second is an iterator to the upper bound of the range with the same value as the one that would be returned by upper_bound(x).

◆ equal_range() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

std::pair< ConstIterator, ConstIterator > DGtal::LabelledMap< TData, L, TWord, N, M >::equal_range ( const Key & x ) const

Get range of equal elements.

Returns the bounds of a range that includes all the elements in the container with a key that compares equal to x. Here, the range will include one element at most.

If x does not match any key in the container, the range returned has a length of zero, with both iterators pointing to the element with nearest key greater than x, if any, or to map::end if x is greater than all the elements in the container.

Parameters

x	any key in 0..L-1

Returns: a pair, where its member pair::first is an iterator to the lower bound of the range with the same value as the one that would be returned by lower_bound(x), and pair::second is an iterator to the upper bound of the range with the same value as the one that would be returned by upper_bound(x).

◆ erase() [1/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

void DGtal::LabelledMap< TData, L, TWord, N, M >::erase	(	Iterator	first,
		Iterator	last
	)

Erases the elements in the range [first,last).

Parameters

first	a valid iterator.
last	a valid iterator.

NB: to clear the container, prefer clear() instead of erase( begin(), end() ).

See also: clear

◆ erase() [2/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

void DGtal::LabelledMap< TData, L, TWord, N, M >::erase ( Iterator position )

Erases the pair (key,data) pointed by iterator.

Parameters

position any valid iterator in the container.

◆ erase() [3/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

SizeType DGtal::LabelledMap< TData, L, TWord, N, M >::erase ( Key key )

Erases the element of key key.

Parameters

key	any key (in 0..L-1)

Returns: the number of elements deleted (0 or 1).

◆ fastAt() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

Data & DGtal::LabelledMap< TData, L, TWord, N, M >::fastAt ( const Key & key )

A read-write accessor to the data associated to an existing key.

Parameters

key	any label (such that count(key)==1)

Returns: a reference to the associated data.

◆ fastAt() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

const Data & DGtal::LabelledMap< TData, L, TWord, N, M >::fastAt ( const Key & key ) const

A read-only accessor to the data associated to an existing key.

Parameters

key	any label (such that count(key)==1)

Returns: a const reference to the associated data.

◆ find() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

Iterator DGtal::LabelledMap< TData, L, TWord, N, M >::find ( const Key & x )

Get iterator to element.

Searches the container for an element with x as key and returns an iterator to it if found, otherwise it returns an iterator to end() (the element past the end of the container).

NB: Another member function, count(), can be used to just check whether a particular key exists. 'count( x ) == 1' is faster than 'find( x ) != end()'.

Parameters

x	Key to be searched for (in 0..L-1)

Returns: An iterator to the element, if the specified key value is found, end() if the specified key is not found in the container.

◆ find() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

ConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::find ( const Key & x ) const

Get iterator to element.

Searches the container for an element with x as key and returns an iterator to it if found, otherwise it returns an iterator to end() (the element past the end of the container).

NB: Another member function, count(), can be used to just check whether a particular key exists. 'count( x ) == 1' is faster than 'find( x ) != end()'.

Parameters

x	Key to be searched for (in 0..L-1)

Returns: An iterator to the element, if the specified key value is found, end() if the specified key is not found in the container.

◆ insert() [1/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

std::pair< Iterator, bool > DGtal::LabelledMap< TData, L, TWord, N, M >::insert ( const Value & val )

Insertion of a new data at given label. Follows std::insert return a pair<iterator,bool>). Note that the data is associated to key only if key was not present in the container.

Parameters

val	a pair<key,data>.

Returns: a pair <iterator,bool> where iterator points on the pair (key,data) while the boolean is true if a new element was indeed created.

NB: This method is provided to follow the std::AssociativeContainer concept. You are discourage to use this functions since the correct iterator must be recomputed at each insert. Prefer operator[] or fastAt.

◆ insert() [2/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

template<typename InputIterator >

void DGtal::LabelledMap< TData, L, TWord, N, M >::insert	(	InputIterator	first,
		InputIterator	last
	)

Insertion from range. Insert all values in the range. Be careful that if a value in the container has the same key as a value in the range, then the mapped data is not changed.

Template Parameters

InputIterator model of boost::InputIterator whose value type is convertible to Value.

Parameters

first	an iterator on the first value of the range.
last	an iterator after the last value of the range.

◆ insert() [3/3]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

Iterator DGtal::LabelledMap< TData, L, TWord, N, M >::insert	(	Iterator	position,
		const Value &	val
	)

Inserts the pair val (key,data) in the container, where position is a hint

Parameters

position	an iterator used as a hint to find the good place. Unused here.
val	a pair (key,data)

Returns: an iterator on the inserted element.

NB: This method is provided to follow the std::AssociativeContainer concept. You are discourage to use this functions since the correct iterator must be recomputed at each insert. Prefer operator[] or fastAt.

◆ isValid()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

bool DGtal::LabelledMap< TData, L, TWord, N, M >::isValid ( ) const

Checks the validity/consistency of the object.

Returns: 'true' if the object is valid, 'false' otherwise.

◆ key_comp()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

KeyCompare DGtal::LabelledMap< TData, L, TWord, N, M >::key_comp ( ) const

Returns: a comparator object for two keys. Corresponds to k1 < k2.

◆ labels()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

const LabelsType & DGtal::LabelledMap< TData, L, TWord, N, M >::labels ( ) const

Returns: a reference to the labels.

◆ lower_bound() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

Iterator DGtal::LabelledMap< TData, L, TWord, N, M >::lower_bound ( const Key & x )

Return iterator to lower bound.

Returns an iterator pointing to the first element in the container whose key does not compare less than x (using the container's comparison object), i.e. it is either equal or greater.

Unlike upper_bound(), this member function returns an iterator to the element also if it compares equal to x and not only if it compares greater.

Notice that, internally, all the elements in this container are always ordered by their keys, therefore all the elements that follow the one returned by this function will have a key that compares greater than x.

Parameters

x	Key to be searched for (in 0..L-1)

Returns: an iterator to the the first element in the container whose key does not compare less than x.

◆ lower_bound() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

ConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::lower_bound ( const Key & x ) const

Return iterator to lower bound.

Returns an iterator pointing to the first element in the container whose key does not compare less than x, i.e. it is either equal or greater.

Unlike upper_bound(), this member function returns an iterator to the element also if it compares equal to x and not only if it compares greater.

Notice that, internally, all the elements in this container are always ordered by their keys, therefore all the elements that follow the one returned by this function will have a key that compares greater than x.

Parameters

x	Key to be searched for (in 0..L-1)

Returns: an iterator to the the first element in the container whose key does not compare less than x.

◆ max_size()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

SizeType DGtal::LabelledMap< TData, L, TWord, N, M >::max_size ( ) const

The maximum number of datas storable in the structure.

◆ operator=()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

LabelledMap & DGtal::LabelledMap< TData, L, TWord, N, M >::operator= ( const LabelledMap< TData, L, TWord, N, M > & other )

Assignment.

Parameters

other the object to copy.

Returns: a reference on 'this'.

◆ operator[]() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

Data & DGtal::LabelledMap< TData, L, TWord, N, M >::operator[] ( const Key & key )

Follows std::operator[]. Given a key key, returns a reference to the associated data.

Parameters

key any label

Returns: a reference to the associated data.

◆ operator[]() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

const Data & DGtal::LabelledMap< TData, L, TWord, N, M >::operator[] ( const Key & key ) const

Read-only version. Follows std::operator[]. Given a key key, returns a reference to the associated data.

Parameters

key any label

Returns: a const reference to the associated data.

◆ selfDisplay()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

void DGtal::LabelledMap< TData, L, TWord, N, M >::selfDisplay ( std::ostream & out ) const

Writes/Displays the object on an output stream.

Parameters

out	the output stream where the object is written.

◆ size()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

SizeType DGtal::LabelledMap< TData, L, TWord, N, M >::size ( ) const

The number of datas stored in the structure. O(1) complexity.

◆ swap()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

void DGtal::LabelledMap< TData, L, TWord, N, M >::swap ( Self & other )

Swap content. Exchanges the content of the container with the content of mp, which is another map object containing elements of the same type. Sizes may differ.

After the call to this member function, the elements in this container are those which were in mp before the call, and the elements of mp are those which were in this.

NB: not exactly standard ! The iterators pointing on the first block change roles ! The other references and pointers remain valid for the swapped objects.

◆ upper_bound() [1/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

Iterator DGtal::LabelledMap< TData, L, TWord, N, M >::upper_bound ( const Key & x )

Return iterator to upper bound.

Returns an iterator pointing to the first element in the container whose key compares greater than x. (>x)

Unlike lower_bound(), this member function does not return an iterator to the element if its key compares equal to x, but only if it compares strictly greater.

Notice that, internally, all the elements in this container are always ordered by their keys, therefore all the elements that follow the one returned by this function will have a key that compares greater than x.

Parameters

x	Key to be searched for (in 0..L-1)

Returns: an iterator to the the first element in the container whose key compares greater than x.

◆ upper_bound() [2/2]

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

ConstIterator DGtal::LabelledMap< TData, L, TWord, N, M >::upper_bound ( const Key & x ) const

Return iterator to upper bound.

Returns an iterator pointing to the first element in the container whose key compares greater than x. (>x)

Unlike lower_bound(), this member function does not return an iterator to the element if its key compares equal to x, but only if it compares strictly greater.

Notice that, internally, all the elements in this container are always ordered by their keys, therefore all the elements that follow the one returned by this function will have a key that compares greater than x.

Parameters

x	Key to be searched for (in 0..L-1)

Returns: an iterator to the the first element in the container whose key compares greater than x.

◆ value_comp()

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

ValueCompare DGtal::LabelledMap< TData, L, TWord, N, M >::value_comp ( ) const

Returns: a comparator object for two values. Corresponds to v1.first < v2.first.

Field Documentation

◆ myFirstBlock

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

__FirstBlock DGtal::LabelledMap< TData, L, TWord, N, M >::myFirstBlock

private

Stores the first block of datas.

Definition at line 1234 of file LabelledMap.h.

◆ myLabels

template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>

LabelsType DGtal::LabelledMap< TData, L, TWord, N, M >::myLabels

private

Stores the labels for this sequence of datas.

Definition at line 1229 of file LabelledMap.h.

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

LabelledMap.h

Data Structures

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ ConstPointer

◆ ConstReference

◆ Data

◆ data_type

◆ difference_type

◆ DifferenceType

◆ iterator

◆ Iterator

◆ Key

◆ key_compare

◆ key_type

◆ Label

◆ LabelsConstIterator

◆ LabelsType

◆ mapped_type

◆ Pointer

◆ pointer

◆ Reference

◆ reference

◆ Self

◆ size_type

◆ SizeType

◆ Value

◆ value_compare

◆ value_type

◆ Word

Constructor & Destructor Documentation

◆ LabelledMap() [1/3]

◆ LabelledMap() [2/3]

◆ LabelledMap() [3/3]

◆ ~LabelledMap()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ blockAt() [1/2]

◆ blockAt() [2/2]

◆ blockBegin() [1/2]

◆ blockBegin() [2/2]

◆ blockClear()

◆ blockEnd() [1/2]

◆ blockEnd() [2/2]

◆ blockErase()

◆ blockInsert()

◆ BOOST_STATIC_ASSERT() [1/3]

◆ BOOST_STATIC_ASSERT() [2/3]

◆ BOOST_STATIC_ASSERT() [3/3]

◆ capacity()

◆ clear()

◆ count()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equal_range() [1/2]

◆ equal_range() [2/2]

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ fastAt() [1/2]

◆ fastAt() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ isValid()

◆ key_comp()

◆ labels()

◆ lower_bound() [1/2]

◆ lower_bound() [2/2]

◆ max_size()