dsa::ForwardList< T > Class Template Reference

Implements ForwardList using Node with pointer to next element as internal base. More...

#include <forward_list.h>

Classes
class	ForwardListIterator
	Implements ForwardListIterator. More...
class	Node
	Implements Node class with user data. More...
class	NodeBase
	Struct implements base pointer used by ForwardList. More...

Public Types
using	value_type = T
	Alias for data type used in class.
using	allocator_type = std::allocator<value_type>
	Alias for memory allocator.
using	size_type = std::size_t
	Alias for size type used in class.
using	difference_type = std::ptrdiff_t
	Alias for pointer difference type used in class.
using	pointer = value_type*
	Alias for pointer to data type used in class.
using	const_pointer = const value_type*
	Alias for const pointer to data type used in class.
using	reference = value_type&
	Alias for reference to data type used in class.
using	const_reference = const value_type&
	Alias for const reference to data type used in class.
using	const_iterator = ForwardListIterator<true>
	Alias for const iterator to data type used in class.
using	iterator = ForwardListIterator<false>
	Alias for iterator to data type used in class.

Public Member Functions
	ForwardList ()
	Construct a new ForwardList object.
	ForwardList (size_type count)
	Construct a new ForwardList object of size count, using default value of type T.
	ForwardList (size_type count, const T &value)
	Construct a new ForwardList object of size count, using provided value of type T.
template<typename InputIt> requires std::input_iterator<InputIt>
	ForwardList (InputIt first, InputIt last)
	Construct a new ForwardList object using elements from range [ first , last )
	ForwardList (const std::initializer_list< T > &init_list)
	Construct a new ForwardList object using initializer list.
	ForwardList (const ForwardList< T > &other)
	Construct a new ForwardList object using copy constructor.
auto	operator= (const ForwardList< T > &other) -> ForwardList &
	Constructs ForwardList using copy assignment.
	ForwardList (ForwardList< T > &&other) noexcept
	Construct a new ForwardList object using move constructor.
auto	operator= (ForwardList< T > &&other) noexcept -> ForwardList &
	Assign ForwardList object using move assignment.
	~ForwardList ()
	Destroy the ForwardList object.
void	assign (size_type count, const_reference value)
	Function assign values to the ForwardList.
template<typename InputIt> requires std::input_iterator<InputIt>
void	assign (InputIt first, InputIt last)
	Function assign elements from range [ first , last ) to ForwardList object.
void	assign (const std::initializer_list< T > &init_list)
	Function assign values to the ForwardList.
constexpr auto	get_allocator () const -> allocator_type
	Get the allocator object.
auto	front () -> reference
	Function returns reference to value stored in ForwardList first Node.
auto	front () const -> const_reference
	Function returns const reference value stored in ForwardList first Node.
auto	before_begin () noexcept -> iterator
	Function returns iterator just before ForwardList first Node.
auto	before_begin () const noexcept -> const_iterator
	Function returns const_iterator just before ForwardList first Node.
auto	cbefore_begin () const noexcept -> const_iterator
	Function returns const_iterator just before ForwardList first Node.
auto	begin () noexcept -> iterator
	Function returns pointer to ForwardList first Node.
auto	begin () const noexcept -> const_iterator
	Function returns const pointer to ForwardList first Node.
auto	cbegin () const noexcept -> const_iterator
	Function returns const pointer to ForwardList first Node.
auto	end () noexcept -> iterator
	Function returns pointer to ForwardList last Node.
auto	end () const noexcept -> const_iterator
	Function returns pointer to ForwardList last Node.
auto	cend () const noexcept -> const_iterator
	Function returns pointer to ForwardList last Node.
auto	empty () const -> bool
	Function checks if container has no elements.
auto	max_size () const noexcept -> size_type
	Function returns maximum number of elements container can hold.
void	clear ()
	Function removes all elements of ForwardList.
auto	insert_after (const const_iterator &pos, const_reference value) -> iterator
	Function inserts new Node after specified ForwardList iterator.
auto	insert_after (const const_iterator &pos, T &&value) -> iterator
	Function inserts new Node after specified ForwardList iterator.
auto	insert_after (const const_iterator &pos, size_type count, const_reference value) -> iterator
	Function inserts new Node after specified ForwardList const_iterator.
template<typename InputIt> requires std::input_iterator<InputIt>
auto	insert_after (const const_iterator &pos, InputIt first, InputIt last) -> iterator
	Function inserts new Node after specified ForwardList const_iterator.
auto	insert_after (const const_iterator &pos, std::initializer_list< T > init_list) -> iterator
	Function inserts new Node after specified ForwardList const_iterator.
template<typename... Args>
auto	emplace_after (const_iterator pos, Args &&... args) -> iterator
	Insert new element into the container after pos.
auto	erase_after (const const_iterator &pos) -> iterator
	Function erases Node after specified ForwardList const_iterator.
auto	erase_after (const const_iterator &first, const const_iterator &last) -> iterator
	Function erases Node between specified ForwardList const_iterators.
void	push_front (const_reference value)
	Function adds new Node at the beginning of ForwardList.
void	push_front (T &&value)
	Function adds new Node at the beginning of ForwardList.
template<typename... Args>
auto	emplace_front (Args &&... args) -> reference
	Inserts a new element to the beginning of the container.
void	pop_front ()
	Function removes first Node of ForwardList.
void	resize (size_type count)
	Function resize ForwardList to specified number of elements.
void	resize (size_type count, const_reference value)
	Function resize ForwardList to specified number of elements.
void	swap (ForwardList< T > &other) noexcept(std::is_nothrow_swappable_v< T >)
	Function swaps content of two ForwardList objects.
void	merge (ForwardList< T > &other)
	Function combines two sorted ForwardLists into one sorted ForwardList.
void	merge (ForwardList< T > &&other)
	Function combines two sorted ForwardLists into one sorted ForwardList.
template<typename Compare>
void	merge (ForwardList< T > &other, Compare comp)
	Function combines two sorted ForwardLists into one sorted ForwardList.
template<typename Compare>
void	merge (ForwardList< T > &&other, Compare comp)
	Function combines two sorted ForwardLists into one sorted ForwardList.
void	splice_after (const const_iterator &pos, ForwardList< T > &other)
	Function moves elements from other ForwardList object.
void	splice_after (const_iterator pos, ForwardList< T > &&other)
	Function moves elements from other ForwardList object.
void	splice_after (const const_iterator &pos, ForwardList< T > &other, const const_iterator &iter)
	Function moves elements from other ForwardList object.
void	splice_after (const_iterator pos, ForwardList< T > &&other, const_iterator iter)
	Function moves elements from other ForwardList object.
void	splice_after (const const_iterator &pos, ForwardList< T > &other, const const_iterator &first, const const_iterator &last)
	Function moves elements from other ForwardList object.
void	splice_after (const_iterator pos, ForwardList< T > &&other, const_iterator first, const_iterator last)
	Function moves elements from other ForwardList object.
auto	remove (const_reference value) -> size_type
	Function removes all elements equal to value.
template<typename UnaryPred>
auto	remove_if (UnaryPred predicate) -> size_type
	Function removes all elements for which predicate returns true.
void	reverse ()
	Function reverts in place Nodes of ForwardList.
auto	unique () -> size_type
	Function removes consecutive duplicated elements.
template<typename BinaryPred>
auto	unique (BinaryPred predicate) -> size_type
	Function removes consecutive duplicated elements.
void	sort ()
	Function sorts the elements and preserves the order of equivalent elements.
template<typename Compare>
void	sort (Compare comp)
	Function sorts the elements and preserves the order of equivalent elements.
auto	size () const -> size_type
	Function returns ForwardList size.

Detailed Description

template<typename T>
class dsa::ForwardList< T >

Implements ForwardList using Node with pointer to next element as internal base.

Template Parameters

T	type of data stored in ForwardList Node

Definition at line 38 of file forward_list.h.

Member Typedef Documentation

allocator_type

template<typename T>

using dsa::ForwardList< T >::allocator_type = std::allocator<value_type>

Alias for memory allocator.

Definition at line 355 of file forward_list.h.

const_iterator

template<typename T>

using dsa::ForwardList< T >::const_iterator = ForwardListIterator<true>

Alias for const iterator to data type used in class.

Definition at line 402 of file forward_list.h.

const_pointer

template<typename T>

using dsa::ForwardList< T >::const_pointer = const value_type*

Alias for const pointer to data type used in class.

Template Parameters

T*	pointer to data type

Definition at line 383 of file forward_list.h.

const_reference

template<typename T>

using dsa::ForwardList< T >::const_reference = const value_type&

Alias for const reference to data type used in class.

Template Parameters

T&	const reference to data type

Definition at line 397 of file forward_list.h.

difference_type

template<typename T>

using dsa::ForwardList< T >::difference_type = std::ptrdiff_t

Alias for pointer difference type used in class.

Template Parameters

T	pointer size type

Definition at line 369 of file forward_list.h.

iterator

template<typename T>

using dsa::ForwardList< T >::iterator = ForwardListIterator<false>

Alias for iterator to data type used in class.

Definition at line 407 of file forward_list.h.

pointer

template<typename T>

using dsa::ForwardList< T >::pointer = value_type*

Alias for pointer to data type used in class.

Template Parameters

T*	pointer to data type

Definition at line 376 of file forward_list.h.

reference

template<typename T>

using dsa::ForwardList< T >::reference = value_type&

Alias for reference to data type used in class.

Template Parameters

T&	reference to data type

Definition at line 390 of file forward_list.h.

size_type

template<typename T>

using dsa::ForwardList< T >::size_type = std::size_t

Alias for size type used in class.

Template Parameters

T

size type

Definition at line 362 of file forward_list.h.

value_type

template<typename T>

using dsa::ForwardList< T >::value_type = T

Alias for data type used in class.

Template Parameters

T

data type

Definition at line 350 of file forward_list.h.

Constructor & Destructor Documentation

ForwardList() [1/7]

template<typename T>

dsa::ForwardList< T >::ForwardList

(

)

Construct a new ForwardList object.

Definition at line 1129 of file forward_list.h.

    {
        init_node();
    }

ForwardList() [2/7]

template<typename T>

dsa::ForwardList< T >::ForwardList

(

size_type

count

)

Construct a new ForwardList object of size count, using default value of type T.

Parameters

[in]

count

element count

Definition at line 1135 of file forward_list.h.

        : ForwardList(count, T{})
    {}

ForwardList() [3/7]

template<typename T>

dsa::ForwardList< T >::ForwardList	(	size_type	count,
		const T &	value )

Construct a new ForwardList object of size count, using provided value of type T.

Parameters

[in]	count	element count
[in]	value	value for all nodes

Definition at line 1140 of file forward_list.h.

    {
        init_node();
 
        for (size_type i = 0; i < count; i++)
        {
            push_front(value);
        }
    }

ForwardList() [4/7]

template<typename T>
requires std::input_iterator<InputIt>

template<typename InputIt>
requires std::input_iterator<InputIt>

dsa::ForwardList< T >::ForwardList	(	InputIt	first,
		InputIt	last )

Construct a new ForwardList object using elements from range [ first , last )

Template Parameters

InputIt

Parameters

[in]	first	element defining range of elements to insert
[in]	last	element definig range of elements to insert

Definition at line 1153 of file forward_list.h.

    {
        init_node();
 
        assign(first, last);
    }

ForwardList() [5/7]

template<typename T>

dsa::ForwardList< T >::ForwardList

(

const std::initializer_list< T > &

init_list

)

Construct a new ForwardList object using initializer list.

Parameters

[in]

init_list

initializer list of values of type T

Definition at line 1161 of file forward_list.h.

    {
        init_node();
 
        auto iter = before_begin();
        for (const auto& item : init_list)
        {
            iter = insert_after(iter, item);
        }
    }

ForwardList() [6/7]

template<typename T>

dsa::ForwardList< T >::ForwardList

(

const ForwardList< T > &

other

)

Construct a new ForwardList object using copy constructor.

Parameters

[in]

other

ForwardList object of type T

Definition at line 1173 of file forward_list.h.

    {
        init_node();
 
        auto iter = before_begin();
        for (const auto& item : other)
        {
            iter = insert_after(iter, item);
        }
    }

ForwardList() [7/7]

template<typename T>

dsa::ForwardList< T >::ForwardList ( ForwardList< T > && other )

noexcept

Construct a new ForwardList object using move constructor.

Content of other object will be taken by constructed object

Parameters

[in,out]

other

ForwardList object of type T

Definition at line 1207 of file forward_list.h.

    {
        operator=(std::move(other));
    }

~ForwardList()

template<typename T>

dsa::ForwardList< T >::~ForwardList

(

)

Destroy the ForwardList object.

Definition at line 1231 of file forward_list.h.

    {
        clear();
        delete m_head;
    }

Member Function Documentation

assign() [1/3]

template<typename T>

void dsa::ForwardList< T >::assign

(

const std::initializer_list< T > &

init_list

)

Function assign values to the ForwardList.

Parameters

[in]

init_list

values to replace ForwardList with

Definition at line 1268 of file forward_list.h.

    {
        while (m_head->m_next)
        {
            pop_front();
        }
 
        auto iter = before_begin();
        for (const auto& item : init_list)
        {
            iter = insert_after(iter, item);
        }
    }

assign() [2/3]

template<typename T>
requires std::input_iterator<InputIt>

template<typename InputIt>
requires std::input_iterator<InputIt>

void dsa::ForwardList< T >::assign	(	InputIt	first,
		InputIt	last )

Function assign elements from range [ first , last ) to ForwardList object.

Template Parameters

InputIt

Parameters

[in]	first	element defining range of elements to insert
[in]	last	element definig range of elements to insert

Definition at line 1255 of file forward_list.h.

    {
        clear();
 
        auto iter = before_begin();
        while (first != last)
        {
            iter = insert_after(iter, *first);
            first++;
        }
    }

assign() [3/3]

template<typename T>

void dsa::ForwardList< T >::assign	(	size_type	count,
		const_reference	value )

Function assign values to the ForwardList.

Parameters

[in]	count	new size of the container
[in]	value	value to initialize elements of the container with

Definition at line 1238 of file forward_list.h.

    {
        while (m_head->m_next)
        {
            pop_front();
        }
 
        auto iter = before_begin();
        for (size_type i = 0; i < count; i++)
        {
            iter = insert_after(iter, value);
        }
    }

before_begin() [1/2]

template<typename T>

auto dsa::ForwardList< T >::before_begin ( ) const -> const_iterator

nodiscardnoexcept

Function returns const_iterator just before ForwardList first Node.

Returns

const_iterator iterator just before ForwardList first Node

Definition at line 1307 of file forward_list.h.

    {
        return const_iterator(m_head);
    }

before_begin() [2/2]

template<typename T>

auto dsa::ForwardList< T >::before_begin ( ) -> iterator

nodiscardnoexcept

Function returns iterator just before ForwardList first Node.

Returns

iterator iterator just before ForwardList first Node

Definition at line 1301 of file forward_list.h.

    {
        return iterator(m_head);
    }

begin() [1/2]

template<typename T>

auto dsa::ForwardList< T >::begin ( ) const -> const_iterator

nodiscardnoexcept

Function returns const pointer to ForwardList first Node.

Returns

const_iterator const iterator to ForwardList first Node

Definition at line 1325 of file forward_list.h.

    {
        return const_iterator(m_head->m_next);
    }

begin() [2/2]

template<typename T>

auto dsa::ForwardList< T >::begin ( ) -> iterator

nodiscardnoexcept

Function returns pointer to ForwardList first Node.

Returns

iterator iterator to ForwardList first Node

Definition at line 1319 of file forward_list.h.

    {
        return iterator(m_head->m_next);
    }

cbefore_begin()

template<typename T>

auto dsa::ForwardList< T >::cbefore_begin ( ) const -> const_iterator

nodiscardnoexcept

Function returns const_iterator just before ForwardList first Node.

Returns

const_iterator iterator just before ForwardList first Node

Definition at line 1313 of file forward_list.h.

    {
        return before_begin();
    }

cbegin()

template<typename T>

auto dsa::ForwardList< T >::cbegin ( ) const -> const_iterator

nodiscardnoexcept

Function returns const pointer to ForwardList first Node.

Returns

const_iterator const iterator to ForwardList first Node

Definition at line 1331 of file forward_list.h.

    {
        return begin();
    }

cend()

template<typename T>

auto dsa::ForwardList< T >::cend ( ) const -> const_iterator

nodiscardnoexcept

Function returns pointer to ForwardList last Node.

Returns

const_iterator const iterator to ForwardList last Node

Definition at line 1349 of file forward_list.h.

    {
        return end();
    }

clear()

template<typename T>

void dsa::ForwardList< T >::clear

(

)

Function removes all elements of ForwardList.

Definition at line 1368 of file forward_list.h.

    {
        if (m_head)
        {
            NodeBase* temp{ m_head->m_next };
            while (temp)
            {
                m_head->m_next = temp->m_next;
                destroy_node(temp);
                temp = m_head->m_next;
            }
 
            m_size = 0;
            m_head->m_next = nullptr;
        }
    }

emplace_after()

template<typename T>

template<typename... Args>

auto dsa::ForwardList< T >::emplace_after	(	const_iterator	pos,
		Args &&...	args ) -> iterator

Insert new element into the container after pos.

Template Parameters

...Args

Parameters

[in]	pos	iterator before which new element will be inserted
[in]	...args	args arguments to forward to the constructor of the element

Returns

iterator pointing to the emplaced element

Note

no iterators or references are invalidated, if construction of new element fails or an exception is thrown for any reason state of the object does not change and this function has no effect

Definition at line 1466 of file forward_list.h.

    {
        const iterator current{ pos.m_current_node };
 
        Node* newNode{ construct_node(current.m_current_node->m_next, std::forward<Args>(args)...) };
        current.m_current_node->m_next = newNode;
        ++m_size;
 
        return iterator(newNode);
    }

emplace_front()

template<typename T>

template<typename... Args>

auto dsa::ForwardList< T >::emplace_front

(

Args &&...

args

)

-> reference

Inserts a new element to the beginning of the container.

Template Parameters

...Args

Parameters

[in]

...args

arguments to forward to the constructor of the element

Returns

reference to emplaced element

Note

no iterators or references are invalidated, if construction of new element fails or an exception is thrown for any reason state of the object does not change and this function has no effect

Definition at line 1524 of file forward_list.h.

    {
        emplace_after(before_begin(), std::forward<Args>(args)...);
        return front();
    }

empty()

template<typename T>

auto dsa::ForwardList< T >::empty ( ) const -> bool

nodiscard

Function checks if container has no elements.

Return values

true	if container is empty
false	if container is not empty

Definition at line 1356 of file forward_list.h.

    {
        return m_size == 0;
    }

end() [1/2]

template<typename T>

auto dsa::ForwardList< T >::end ( ) const -> const_iterator

nodiscardnoexcept

Function returns pointer to ForwardList last Node.

Returns

const_iterator const iterator to ForwardList last Node

Definition at line 1343 of file forward_list.h.

    {
        return const_iterator(nullptr);
    }

end() [2/2]

template<typename T>

auto dsa::ForwardList< T >::end ( ) -> iterator

nodiscardnoexcept

Function returns pointer to ForwardList last Node.

Returns

iterator iterator to ForwardList last Node

Definition at line 1337 of file forward_list.h.

    {
        return iterator(nullptr);
    }

erase_after() [1/2]

template<typename T>

auto dsa::ForwardList< T >::erase_after	(	const const_iterator &	first,
		const const_iterator &	last ) -> iterator

Function erases Node between specified ForwardList const_iterators.

Parameters

[in]	first	element after which element will be erased
[in]	last	element after last erased element

Returns

pointer to element after last deleted element

Return values

iterator	to element after last deleted element
nullptr	if invalid iterator

Definition at line 1492 of file forward_list.h.

    {
        if (!if_valid_iterator(first) || !if_valid_iterator(last))
        {
            return nullptr;
        }
 
        const iterator iter(first.m_current_node);
        const size_type dist = distance(first, last);
        for (size_type i = 0; i < dist - 1; i++)
        {
            erase_element_after(iter);
        }
 
        return first.m_current_node->m_next;
    }

erase_after() [2/2]

template<typename T>

auto dsa::ForwardList< T >::erase_after

(

const const_iterator &

pos

)

-> iterator

Function erases Node after specified ForwardList const_iterator.

Parameters

[in]

pos

const_iterator after which element will be erased

Returns

pointer to element after deleted iterator

Return values

iterator	element after deleted element
nullptr	if invalid iterator

Definition at line 1478 of file forward_list.h.

    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        iterator iter{ pos.m_current_node };
        iter = erase_element_after(iter);
 
        return iter;
    }

front() [1/2]

template<typename T>

auto dsa::ForwardList< T >::front ( ) -> reference

nodiscard

Function returns reference to value stored in ForwardList first Node.

Returns

reference to data stored in ForwardList first Node

Definition at line 1289 of file forward_list.h.

    {
        return *begin();
    }

front() [2/2]

template<typename T>

auto dsa::ForwardList< T >::front ( ) const -> const_reference

nodiscard

Function returns const reference value stored in ForwardList first Node.

Returns

const reference to data stored in ForwardList first Node

Definition at line 1295 of file forward_list.h.

    {
        return *cbegin();
    }

get_allocator()

template<typename T>

auto dsa::ForwardList< T >::get_allocator ( ) const -> allocator_type

nodiscardconstexpr

Get the allocator object.

Returns

allocator_type type of memory allocator

Definition at line 1283 of file forward_list.h.

    {
        return m_allocator;
    }

insert_after() [1/5]

template<typename T>

auto dsa::ForwardList< T >::insert_after	(	const const_iterator &	pos,
		const_reference	value ) -> iterator

Function inserts new Node after specified ForwardList iterator.

Parameters

[in]	pos	const_iterator to insert element after
[in]	value	element of type T to be inserted after pos

Returns

pointer to ForwardList element

Return values

iterator	to inserted value
pos	if no element was inserted

Definition at line 1386 of file forward_list.h.

    {
        return insert_after(pos, 1, value);
    }

insert_after() [2/5]

template<typename T>
requires std::input_iterator<InputIt>

template<typename InputIt>
requires std::input_iterator<InputIt>

auto dsa::ForwardList< T >::insert_after	(	const const_iterator &	pos,
		InputIt	first,
		InputIt	last ) -> iterator

Function inserts new Node after specified ForwardList const_iterator.

Parameters

[in]	pos	const_iterator to insert element after
[in]	first	element defining range of elements to insert
[in]	last	element definig range of elements to insert

Returns

pointer to ForwardList element

Return values

iterator	pointer to last inserted element
pos	if no element was inserted

Definition at line 1428 of file forward_list.h.

    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        iterator iter{ pos.m_current_node };
        while (first != last)
        {
            iter = insert_after(iter, *first);
            first++;
        }
 
        return iter;
    }

insert_after() [3/5]

template<typename T>

auto dsa::ForwardList< T >::insert_after	(	const const_iterator &	pos,
		size_type	count,
		const_reference	value ) -> iterator

Function inserts new Node after specified ForwardList const_iterator.

Parameters

[in]	pos	const_iterator to insert element after
[in]	count	number of elements to insert after pos
[in]	value	element of type T to be inserted

Returns

pointer to ForwardList element

Return values

iterator	pointer to last inserted element
pos	if no element was inserted

Definition at line 1408 of file forward_list.h.

    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        iterator iter{ pos.m_current_node };
        for (size_type i = 0; i < count; i++)
        {
            iter = emplace_after(iter, value);
        }
 
        return iter;
    }

insert_after() [4/5]

template<typename T>

auto dsa::ForwardList< T >::insert_after	(	const const_iterator &	pos,
		std::initializer_list< T >	init_list ) -> iterator

Function inserts new Node after specified ForwardList const_iterator.

Parameters

[in]	pos	const_iterator to insert element after
[in]	init_list	initializer_list with elements to insert after pos

Returns

pointer to the last inserted element

Return values

iterator	to last inserted element
pos	if no element was inserted

Definition at line 1447 of file forward_list.h.

    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        iterator iter{ pos.m_current_node };
        for (const auto val : init_list)
        {
            iter = emplace_after(iter, val);
        }
 
        return iter;
    }

insert_after() [5/5]

template<typename T>

auto dsa::ForwardList< T >::insert_after	(	const const_iterator &	pos,
		T &&	value ) -> iterator

Function inserts new Node after specified ForwardList iterator.

Parameters

[in]	pos	const_iterator to insert element after
[in]	value	element of type T to be inserted after pos

Returns

pointer to ForwardList element

Return values

iterator	to inserted value
pos	if no element was inserted

Definition at line 1393 of file forward_list.h.

    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        iterator iter{ pos.m_current_node };
        iter = emplace_after(iter, std::move(value));
 
        return iter;
    }

max_size()

template<typename T>

auto dsa::ForwardList< T >::max_size ( ) const -> size_type

nodiscardnoexcept

Function returns maximum number of elements container can hold.

Returns

size_type maximum number of elements

Definition at line 1362 of file forward_list.h.

    {
        return std::numeric_limits<size_type>::max();
    }

merge() [1/4]

template<typename T>

void dsa::ForwardList< T >::merge

(

ForwardList< T > &&

other

)

Function combines two sorted ForwardLists into one sorted ForwardList.

Parameters

[in,out]

other

container to take elements from

Content of other object will be taken by constructed object

Note

no iterators or references become invalidated, iterators or references of objects moved from other will refer to the same elements of this

Definition at line 1611 of file forward_list.h.

    {
        merge(std::move(other), std::less<>());
    }

merge() [2/4]

template<typename T>

template<typename Compare>

void dsa::ForwardList< T >::merge	(	ForwardList< T > &&	other,
		Compare	comp )

Function combines two sorted ForwardLists into one sorted ForwardList.

Parameters

[in,out]	other	container to take elements from
[in]	comp	comparison function object

Content of other object will be taken by constructed object

Note

no iterators or references become invalidated, iterators or references of objects moved from other will refer to the same elements of this

Definition at line 1627 of file forward_list.h.

    {
        if (&other == this)
        {
            return;
        }
 
        if (m_size != 0)
        {
            Node* temp_head{ construct_node(nullptr, T{}) };
            NodeBase* temp_tail{ temp_head };
 
            NodeBase* to_move{};
            NodeBase* to_return{};
 
            while (m_head->m_next && other.m_head->m_next)
            {
                Node* node_this = dynamic_cast<Node*>(m_head->m_next);
                Node* node_other = dynamic_cast<Node*>(other.m_head->m_next);
 
                if (node_this && node_other)
                {
                    if (comp(node_this->value(), node_other->value()))
                    {
                        to_move = m_head->m_next;
                        to_return = to_move->m_next;
                        temp_tail->m_next = to_move;
                        m_head->m_next = to_return;
                    }
                    else
                    {
                        to_move = other.m_head->m_next;
                        to_return = to_move->m_next;
                        temp_tail->m_next = to_move;
                        other.m_head->m_next = to_return;
                    }
 
                    temp_tail = temp_tail->m_next;
                }
            }
 
            if (m_head->m_next == nullptr)
            {
                temp_tail->m_next = other.m_head->m_next;
                other.m_head->m_next = nullptr;
            }
            else
            {
                temp_tail->m_next = m_head->m_next;
                m_head->m_next = nullptr;
            }
 
            m_head->m_next = temp_head->m_next;
            destroy_node(temp_head);
 
            m_size += other.m_size;
            other.m_size = 0;
        }
        else
        {
            swap(other);
        }
    }

merge() [3/4]

template<typename T>

void dsa::ForwardList< T >::merge

(

ForwardList< T > &

other

)

Function combines two sorted ForwardLists into one sorted ForwardList.

Parameters

[in,out]

other

container to take elements from

Content of other object will be taken by constructed object

Note

no iterators or references become invalidated, iterators or references of objects moved from other will refer to the same elements of this

Definition at line 1605 of file forward_list.h.

    {
        merge(std::move(other));
    }

merge() [4/4]

template<typename T>

template<typename Compare>

void dsa::ForwardList< T >::merge	(	ForwardList< T > &	other,
		Compare	comp )

Function combines two sorted ForwardLists into one sorted ForwardList.

Parameters

[in,out]	other	container to take elements from
[in]	comp	comparison function object

Content of other object will be taken by constructed object

Note

no iterators or references become invalidated, iterators or references of objects moved from other will refer to the same elements of this

Definition at line 1618 of file forward_list.h.

    {
        merge(std::move(other), comp);
    }

operator=() [1/2]

template<typename T>

auto dsa::ForwardList< T >::operator=

(

const ForwardList< T > &

other

)

-> ForwardList&

Constructs ForwardList using copy assignment.

Parameters

[in]

other

ForwardList object of type T

Returns

ForwardList& reference to ForwardList object

Definition at line 1185 of file forward_list.h.

    {
        init_node();
 
        if (&other != this)
        {
            while (m_head->m_next)
            {
                pop_front();
            }
 
            auto iter = before_begin();
            for (const auto& item : other)
            {
                iter = insert_after(iter, item);
            }
        }
 
        return *this;
    }

operator=() [2/2]

template<typename T>

auto dsa::ForwardList< T >::operator= ( ForwardList< T > && other ) -> ForwardList&

noexcept

Assign ForwardList object using move assignment.

Content of other object will be taken by constructed object

Parameters

[in,out]

other

ForwardList object of type T

Returns

ForwardList& reference to ForwardList object

Definition at line 1213 of file forward_list.h.

    {
        if (&other != this)
        {
            clear();
            init_node();
 
            m_head->m_next = other.m_head->m_next;
            m_size = other.m_size;
 
            other.m_head->m_next = nullptr;
            other.m_size = 0;
        }
 
        return *this;
    }

pop_front()

template<typename T>

void dsa::ForwardList< T >::pop_front

(

)

Function removes first Node of ForwardList.

Definition at line 1531 of file forward_list.h.

    {
        if (!m_head->m_next)
        {
            return;
        }
 
        NodeBase* temp{ m_head->m_next };
        if (m_size == 1)
        {
            m_head->m_next = nullptr;
        }
        else
        {
            m_head->m_next = temp->m_next;
        }
        destroy_node(temp);
 
        m_size--;
    }

push_front() [1/2]

template<typename T>

void dsa::ForwardList< T >::push_front

(

const_reference

value

)

Function adds new Node at the beginning of ForwardList.

Parameters

[in]

value

element of type T

Note

no iterators or references are invalidated, if construction of new element fails or an exception is thrown for any reason state of the object does not change and this function has no effect

Definition at line 1511 of file forward_list.h.

    {
        emplace_after(before_begin(), value);
    }

push_front() [2/2]

template<typename T>

void dsa::ForwardList< T >::push_front

(

T &&

value

)

Function adds new Node at the beginning of ForwardList.

Parameters

[in]

value

element of type T

Note

no iterators or references are invalidated, if construction of new element fails or an exception is thrown for any reason state of the object does not change and this function has no effect

Definition at line 1517 of file forward_list.h.

    {
        emplace_after(before_begin(), std::move(value));
    }

remove()

template<typename T>

auto dsa::ForwardList< T >::remove

(

const_reference

value

)

-> size_type

Function removes all elements equal to value.

Parameters

[in]

value

value of elements to remove

Returns

size_type number of elements removed

Note

invalidates only the iterators and references to the removed elements

Definition at line 1729 of file forward_list.h.

    {
        return remove_if([value](T node_val) { return node_val == value; });
    }

remove_if()

template<typename T>

template<typename UnaryPred>

auto dsa::ForwardList< T >::remove_if

(

UnaryPred

predicate

)

-> size_type

Function removes all elements for which predicate returns true.

Template Parameters

UnaryPred

Parameters

[in]

predicate

to remove elements

Returns

size_type number of elements removed

Note

invalidates only the iterators and references to the removed elements

Definition at line 1736 of file forward_list.h.

    {
        NodeBase* temp{ m_head };
        NodeBase* next{};
 
        size_type removed_count{};
 
        while (temp)
        {
            next = temp->m_next;
 
            if (Node* node = dynamic_cast<Node*>(next))
            {
                if (predicate(node->value()))
                {
                    NodeBase* to_remove = temp->m_next;
                    temp->m_next = to_remove->m_next;
                    destroy_node(to_remove);
 
                    removed_count++;
                    m_size--;
                    continue;
                }
            }
 
            temp = temp->m_next;
        }
 
        return removed_count;
    }

resize() [1/2]

template<typename T>

void dsa::ForwardList< T >::resize

(

size_type

count

)

Function resize ForwardList to specified number of elements.

Parameters

[in]

count

new size of container

Definition at line 1553 of file forward_list.h.

    {
        resize(count, T{});
    }

resize() [2/2]

template<typename T>

void dsa::ForwardList< T >::resize	(	size_type	count,
		const_reference	value )

Function resize ForwardList to specified number of elements.

Parameters

[in]	count	count new size of container
[in]	value	value to initialize new elements

Definition at line 1559 of file forward_list.h.

    {
        init_node();
 
        if (count == m_size)
        {
            return;
        }
 
        if (m_size > count)
        {
            auto iter = begin();
            for (size_type i = 0; i < count - 1; i++)
            {
                ++iter;
            }
 
            while (m_size > count)
            {
                erase_after(iter);
            }
        }
 
        if (m_size < count)
        {
            auto iter = find_iter_before_last();
            if (iter != before_begin())
            {
                ++iter;
            }
 
            while (m_size < count)
            {
                iter = insert_after(iter, value);
            }
        }
    }

reverse()

template<typename T>

void dsa::ForwardList< T >::reverse

(

)

Function reverts in place Nodes of ForwardList.

Definition at line 1768 of file forward_list.h.

    {
        NodeBase* temp{ m_head->m_next };
 
        auto iter = find_iter_before_last();
        NodeBase* last{ iter.m_current_node->m_next };
 
        m_head->m_next = last;
        last = temp;
 
        NodeBase* prev{};
        NodeBase* next{};
 
        for (size_type i = 0; i < m_size; i++)
        {
            next = temp->m_next;
            temp->m_next = prev;
 
            prev = temp;
            temp = next;
        }
 
        m_head->m_next = std::move(prev);
    }

size()

template<typename T>

auto dsa::ForwardList< T >::size ( ) const -> size_type

inlinenodiscard

Function returns ForwardList size.

Returns

size_type number of elements in container

Definition at line 988 of file forward_list.h.

        {
            return m_size;
        }

sort() [1/2]

template<typename T>

void dsa::ForwardList< T >::sort

(

)

Function sorts the elements and preserves the order of equivalent elements.

elements are compared using operator<

Note

no iterators or references are invalidated, if an exception is thrown, the order of elements is unspecified

Definition at line 1842 of file forward_list.h.

    {
        m_head->m_next = merge_sort(m_head->m_next, std::less<>());
    }

sort() [2/2]

template<typename T>

template<typename Compare>

void dsa::ForwardList< T >::sort

(

Compare

comp

)

Function sorts the elements and preserves the order of equivalent elements.

elements are compared using comp

Template Parameters

Compare

Parameters

[in]

comp

comparison function object, returns true if the first argument is less than second

Note

no iterators or references are invalidated, if an exception is thrown, the order of elements is unspecified

Definition at line 1849 of file forward_list.h.

    {
        m_head->m_next = merge_sort(m_head->m_next, comp);
    }

splice_after() [1/6]

template<typename T>

void dsa::ForwardList< T >::splice_after	(	const const_iterator &	pos,
		ForwardList< T > &	other )

Function moves elements from other ForwardList object.

Content of other object will be taken by constructed object

Parameters

[in]	pos	const_iterator after which content of other container will be inserted
[in,out]	other	container to take elements from

Note

no iterators or references become invalidated, iterators or references of objects moved from other will refer to the same elements of this

Definition at line 1692 of file forward_list.h.

    {
        transfer(pos, std::move(other), other.before_begin(), other.end());
    }

splice_after() [2/6]

template<typename T>

void dsa::ForwardList< T >::splice_after	(	const const_iterator &	pos,
		ForwardList< T > &	other,
		const const_iterator &	first,
		const const_iterator &	last )

Function moves elements from other ForwardList object.

Content of other object will be taken by constructed object

Parameters

[in]	pos	const_iterator after which content of other container will be inserted
[in,out]	other	container to take elements from
[in]	first	const_iterator after which elements of other will be taken
[in]	last	const_iterator until which elements of other will be taken

Note

no iterators or references become invalidated, iterators or references of objects moved from other will refer to the same elements of this

Definition at line 1716 of file forward_list.h.

    {
        transfer(pos, std::move(other), first, last);
    }

splice_after() [3/6]

template<typename T>

void dsa::ForwardList< T >::splice_after	(	const const_iterator &	pos,
		ForwardList< T > &	other,
		const const_iterator &	iter )

Function moves elements from other ForwardList object.

Content of other object will be taken by constructed object

Parameters

[in]	pos	const_iterator after which content of other container will be inserted
[in,out]	other	container to take elements from
[in]	iter	const_iterator after which elements of other will be taken

Note

no iterators or references become invalidated, iterators or references of objects moved from other will refer to the same elements of this

Definition at line 1704 of file forward_list.h.

    {
        transfer(pos, std::move(other), iter);
    }

splice_after() [4/6]

template<typename T>

void dsa::ForwardList< T >::splice_after	(	const_iterator	pos,
		ForwardList< T > &&	other )

Function moves elements from other ForwardList object.

Content of other object will be taken by constructed object

Parameters

[in]	pos	const_iterator after which content of other container will be inserted
[in,out]	other	container to take elements from

Note

no iterators or references become invalidated, iterators or references of objects moved from other will refer to the same elements of this

Definition at line 1698 of file forward_list.h.

    {
        transfer(pos, std::move(other), other.before_begin(), other.end());
    }

splice_after() [5/6]

template<typename T>

void dsa::ForwardList< T >::splice_after	(	const_iterator	pos,
		ForwardList< T > &&	other,
		const_iterator	first,
		const_iterator	last )

Function moves elements from other ForwardList object.

Content of other object will be taken by constructed object

Parameters

[in]	pos	const_iterator after which content of other container will be inserted
[in,out]	other	container to take elements from
[in]	first	const_iterator after which elements of other will be taken
[in]	last	const_iterator until which elements of other will be taken

Note

no iterators or references become invalidated, iterators or references of objects moved from other will refer to the same elements of this

Definition at line 1723 of file forward_list.h.

    {
        transfer(pos, std::move(other), first, last);
    }

splice_after() [6/6]

template<typename T>

void dsa::ForwardList< T >::splice_after	(	const_iterator	pos,
		ForwardList< T > &&	other,
		const_iterator	iter )

Function moves elements from other ForwardList object.

Content of other object will be taken by constructed object

Parameters

[in]	pos	const_iterator after which content of other container will be inserted
[in,out]	other	container to take elements from
[in]	iter	const_iterator after which elements of other will be taken

Note

no iterators or references become invalidated, iterators or references of objects moved from other will refer to the same elements of this

Definition at line 1710 of file forward_list.h.

    {
        transfer(pos, std::move(other), iter);
    }

swap()

template<typename T>

void dsa::ForwardList< T >::swap ( ForwardList< T > & other )

noexcept

Function swaps content of two ForwardList objects.

Parameters

[in,out]

other

object to swap content with

Definition at line 1598 of file forward_list.h.

    {
        std::swap(m_head->m_next, other.m_head->m_next);
        std::swap(m_size, other.m_size);
    }

unique() [1/2]

template<typename T>

auto dsa::ForwardList< T >::unique

(

)

-> size_type

Function removes consecutive duplicated elements.

Only the first occurrence of given element in each group is preserved

Returns

size_type number of elements removed

Definition at line 1794 of file forward_list.h.

    {
        return unique(std::equal_to<>());
    }

unique() [2/2]

template<typename T>

template<typename BinaryPred>

auto dsa::ForwardList< T >::unique

(

BinaryPred

predicate

)

-> size_type

Function removes consecutive duplicated elements.

Only the first occurrence of given element in each group is preserved

Template Parameters

BinaryPred

Parameters

[in]

predicate

binary predicate which returns true if the element should be treated as equal

Returns

size_type number of elements removed

Definition at line 1801 of file forward_list.h.

    {
        NodeBase* temp{ m_head };
        NodeBase* prev{};
        NodeBase* next{};
 
        size_type removed_count{};
 
        while (temp)
        {
            prev = temp;
 
            while (prev)
            {
                next = prev->m_next;
 
                Node* node_next = dynamic_cast<Node*>(next);
                Node* node_temp = dynamic_cast<Node*>(temp);
                if (node_next && node_temp)
                {
                    if (predicate(node_next->value(), node_temp->value()))
                    {
                        NodeBase* to_remove = next;
                        prev->m_next = to_remove->m_next;
                        destroy_node(to_remove);
 
                        removed_count++;
                        m_size--;
                        continue;
                    }
                }
 
                prev = prev->m_next;
                temp = temp->m_next;
            }
        }
 
        return removed_count;
    }

---

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

• include/dsa/forward_list.h