DSA - Data Structures and Algorithms
Loading...
Searching...
No Matches
dsa::List< T > Class Template Reference

Implements List using Node with pointer to adjacent elements as internal base. More...

#include <list.h>

Classes

class  ListIterator
 Implements ListIterator. More...
class  Node
 Implements Node template class with pointer to adjacent elements. More...
class  NodeBase
 Struct implements base pointer used by List. More...

Public Types

using value_type = T
 Alias for data type used in class.
using pointer = T*
 Alias for pointer to data type used in class.
using const_pointer = const T*
 Alias for const pointer to data type used in class.
using reference = T&
 Alias for reference to data type used in class.
using const_reference = const T&
 Alias for const reference to data type used in class.
using const_iterator = ListIterator<true>
 Alias for const iterator to data type used in class.
using iterator = ListIterator<false>
 Alias for iterator to data type used in class.

Public Member Functions

 List ()
 Construct a new List object.
 List (size_t count)
 Construct a new List object of size count, using default value of type T.
 List (size_t count, const T &value)
 Construct a new List object of size count, using provided value of type T.
 List (const std::initializer_list< T > &init_list)
 Construct a new List object using initializer list.
 List (const List< T > &other)
 Construct a new List object using copy constructor.
auto operator= (const List< T > &other) -> List &
 Constructs List using copy assignment.
 List (List< T > &&other) noexcept
 Construct a new List object using move constructor.
auto operator= (List< T > &&other) noexcept -> List &
 Assign List object using move assignment.
 ~List ()
 Destroy the List object.
void assign (size_t count, const_reference value)
 Function assign values to the List.
void assign (const std::initializer_list< T > &init_list)
 Function assign values to the List.
auto front () -> reference
 Function returns reference to value stored in List first Node.
auto front () const -> const_reference
 Function returns const reference value stored in List first Node.
auto back () -> reference
 Function returns reference to value stored in List last Node.
auto back () const -> const_reference
 Function returns const reference value stored in List last Node.
auto begin () -> iterator
 Function returns pointer to List first Node.
auto begin () const -> const_iterator
 Function returns const pointer to List first Node.
auto cbegin () const -> const_iterator
 Function returns const pointer to List first Node.
auto end () -> iterator
 Function returns pointer to List last Node.
auto end () const -> const_iterator
 Function returns pointer to List last Node.
auto cend () const -> const_iterator
 Function returns pointer to List last Node.
auto empty () const -> bool
 Function checks if container has no elements.
auto size () const -> size_t
 Function returns List size.
auto max_size () const -> size_t
 Function returns maximum number of elements container can hold.
void clear ()
 Function removes all elements of List.
auto insert (const const_iterator &pos, const_reference value) -> iterator
 Function inserts new Node before specified pos.
auto insert (const const_iterator &pos, size_t count, const_reference value) -> iterator
 Function inserts new Node before specified pos.
auto insert (const const_iterator &pos, std::initializer_list< T > init_list) -> iterator
 Function inserts new Node before specified pos.
auto erase (iterator pos) -> iterator
 Function erases Node object at specified pos.
auto erase (const_iterator pos) -> iterator
 Function erases Node object at specified pos.
auto erase (iterator first, iterator last) -> iterator
 Function erases Node objects in range [first, last)
auto erase (const_iterator first, const_iterator last) -> iterator
 Function erases Node objects in range [first, last)
void push_back (T value)
 Function adds new Node at the end of List.
void pop_back ()
 Function removes last Node of List.
void push_front (T value)
 Function adds new Node at the beginning of List.
void pop_front ()
 Function removes first Node of List.
void resize (size_t count)
 Function resize List to specified number of elements.
void resize (size_t count, const_reference value)
 Function resize List to specified number of elements.
void swap (List< T > &other) noexcept
 Function swaps content of two List objects.
void merge (List< T > &other)
 Function combines two sorted Lists into one sorted List.
void merge (List< T > &&other)
 Function combines two sorted Lists into one sorted List.
void splice (const const_iterator &pos, List< T > &other)
 Function moves elements from other List object.
void splice (const_iterator pos, List< T > &&other)
 Function moves elements from other List object.
void splice (const const_iterator &pos, List< T > &other, const const_iterator &iter)
 Function moves elements from other List object.
void splice (const_iterator pos, List< T > &&other, const_iterator iter)
 Function moves elements from other List object.
void splice (const const_iterator &pos, List< T > &other, const const_iterator &first, const const_iterator &last)
 Function moves elements in range [first, last) from other List object.
void splice (const_iterator pos, List< T > &&other, const_iterator first, const_iterator last)
 Function moves elements in range [first, last) from other List object.
void remove (const_reference value)
 Function removes all elements equal to value.
void reverse ()
 Function reverts in place Nodes of List.
void unique ()
 Function removes consecutive duplicated elements.
auto operator+= (const List< T > &other) -> List< T > &
 Append elements of another List to base container.
auto operator+= (const std::initializer_list< T > init_list) -> List< T > &
 push_back elements of another List to base container
auto get (size_t index) const -> Node *
 Function returns pointer to specific Node of List.
auto set (size_t index, T value) -> bool
 Function sets value of specifed Node of List.

Friends

auto operator+ (const List< T > &list1, const List< T > &list2) -> List< T >
 Construct new object based on two List objects.

Detailed Description

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

Implements List using Node with pointer to adjacent elements as internal base.

Template Parameters
Ttype of data stored in List Node
Todo

add get_allocator

add rbegin

add crbegin

add rend

add crend

add emplace

add emplace_back

add emplace_front

add remove_if

add sort

add operator<=>

add non-member specialized swap function

add non-member specialized erase function

add non-member specialized erase_if function

remove public functions / operators not supported by std::forward_list

Definition at line 56 of file list.h.

Member Typedef Documentation

◆ const_iterator

template<typename T>
using dsa::List< T >::const_iterator = ListIterator<true>

Alias for const iterator to data type used in class.

Definition at line 446 of file list.h.

◆ const_pointer

template<typename T>
using dsa::List< T >::const_pointer = const T*

Alias for const pointer to data type used in class.

Template Parameters
T*pointer to data type

Definition at line 427 of file list.h.

◆ const_reference

template<typename T>
using dsa::List< T >::const_reference = const T&

Alias for const reference to data type used in class.

Template Parameters
T&const reference to data type

Definition at line 441 of file list.h.

◆ iterator

template<typename T>
using dsa::List< T >::iterator = ListIterator<false>

Alias for iterator to data type used in class.

Definition at line 451 of file list.h.

◆ pointer

template<typename T>
using dsa::List< T >::pointer = T*

Alias for pointer to data type used in class.

Template Parameters
T*pointer to data type

Definition at line 420 of file list.h.

◆ reference

template<typename T>
using dsa::List< T >::reference = T&

Alias for reference to data type used in class.

Template Parameters
T&reference to data type

Definition at line 434 of file list.h.

◆ value_type

template<typename T>
using dsa::List< T >::value_type = T

Alias for data type used in class.

Template Parameters
Tdata type

Definition at line 413 of file list.h.

Constructor & Destructor Documentation

◆ List() [1/6]

template<typename T>
dsa::List< T >::List ( )

Construct a new List object.

Definition at line 1058 of file list.h.

1059 {
1060 init_node();
1061 }

◆ List() [2/6]

template<typename T>
dsa::List< T >::List ( size_t count)

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

Parameters
[in]countelement count

Definition at line 1064 of file list.h.

1065 : List(count, T{})
1066 {
1067 }
dsa::List
Implements List using Node with pointer to adjacent elements as internal base.
Definition list.h:57
dsa::List::List
List()
Construct a new List object.
Definition list.h:1058

◆ List() [3/6]

template<typename T>
dsa::List< T >::List ( size_t count,
const T & value )

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

Parameters
[in]countelement count
[in]valuevalue for all nodes

Definition at line 1070 of file list.h.

1071 {
1072 init_node();
1073
1074 for (size_t i = 0; i < count; i++)
1075 {
1076 push_front(value);
1077 }
1078 }
dsa::List::push_front
void push_front(T value)
Function adds new Node at the beginning of List.
Definition list.h:1341

◆ List() [4/6]

template<typename T>
dsa::List< T >::List ( const std::initializer_list< T > & init_list)

Construct a new List object using initializer list.

Parameters
[in]init_listinitializer list of values of type T

Definition at line 1081 of file list.h.

1082 {
1083 for (const auto& item : init_list)
1084 {
1085 push_back(item);
1086 }
1087 }
dsa::List::push_back
void push_back(T value)
Function adds new Node at the end of List.
Definition list.h:1385

◆ List() [5/6]

template<typename T>
dsa::List< T >::List ( const List< T > & other)

Construct a new List object using copy constructor.

Parameters
[in]otherList object of type T

Definition at line 1090 of file list.h.

1091 {
1092 for (size_t i = 0; i < other.size(); i++)
1093 {
1094 push_back(other.get(i)->value());
1095 }
1096 }
dsa::List::size
auto size() const -> size_t
Function returns List size.
Definition list.h:1237
dsa::List::get
auto get(size_t index) const -> Node *
Function returns pointer to specific Node of List.
Definition list.h:1768

◆ List() [6/6]

template<typename T>
dsa::List< T >::List ( List< T > && other)
noexcept

Construct a new List object using move constructor.

Content of other object will be taken by constructed object

Parameters
[in,out]otherList object of type T

Definition at line 1118 of file list.h.

1119 {
1120 operator=(std::move(other));
1121 }
dsa::List::operator=
auto operator=(const List< T > &other) -> List &
Constructs List using copy assignment.
Definition list.h:1099

◆ ~List()

template<typename T>
dsa::List< T >::~List ( )

Destroy the List object.

Definition at line 1143 of file list.h.

1144 {
1145 clear();
1146 }
dsa::List::clear
void clear()
Function removes all elements of List.
Definition list.h:1249

Member Function Documentation

◆ assign() [1/2]

template<typename T>
void dsa::List< T >::assign ( const std::initializer_list< T > & init_list)

Function assign values to the List.

Parameters
[in]init_listvalues to replace List with

Definition at line 1160 of file list.h.

1161 {
1162 clear();
1163
1164 for (const auto& item : init_list)
1165 {
1166 push_back(item);
1167 }
1168 }

◆ assign() [2/2]

template<typename T>
void dsa::List< T >::assign ( size_t count,
const_reference value )

Function assign values to the List.

Parameters
[in]countnew size of the container
[in]valuevalue to initialize elements of the container with

Definition at line 1149 of file list.h.

1150 {
1151 clear();
1152
1153 for (size_t i = 0; i < count; i++)
1154 {
1155 push_back(value);
1156 }
1157 }

◆ back() [1/2]

template<typename T>
auto dsa::List< T >::back ( ) -> reference

Function returns reference to value stored in List last Node.

Returns
reference to data stored in List last Node

Definition at line 1183 of file list.h.

1184 {
1185 return *(--end());
1186 }
dsa::List::end
auto end() -> iterator
Function returns pointer to List last Node.
Definition list.h:1213

◆ back() [2/2]

template<typename T>
auto dsa::List< T >::back ( ) const -> const_reference
nodiscard

Function returns const reference value stored in List last Node.

Returns
const reference to data stored in List last Node

Definition at line 1189 of file list.h.

1190 {
1191 return *(--cend());
1192 }
dsa::List::cend
auto cend() const -> const_iterator
Function returns pointer to List last Node.
Definition list.h:1225

◆ begin() [1/2]

template<typename T>
auto dsa::List< T >::begin ( ) -> iterator

Function returns pointer to List first Node.

Returns
iterator iterator to List first Node

Definition at line 1195 of file list.h.

1196 {
1197 return iterator(m_head.get());
1198 }
dsa::List::iterator
ListIterator< false > iterator
Alias for iterator to data type used in class.
Definition list.h:451

◆ begin() [2/2]

template<typename T>
auto dsa::List< T >::begin ( ) const -> const_iterator

Function returns const pointer to List first Node.

Returns
const_iterator const iterator to List first Node

Definition at line 1201 of file list.h.

1202 {
1203 return const_iterator(m_head.get());
1204 }
dsa::List::const_iterator
ListIterator< true > const_iterator
Alias for const iterator to data type used in class.
Definition list.h:446

◆ cbegin()

template<typename T>
auto dsa::List< T >::cbegin ( ) const -> const_iterator
nodiscard

Function returns const pointer to List first Node.

Returns
const_iterator const iterator to List first Node

Definition at line 1207 of file list.h.

1208 {
1209 return begin();
1210 }
dsa::List::begin
auto begin() -> iterator
Function returns pointer to List first Node.
Definition list.h:1195

◆ cend()

template<typename T>
auto dsa::List< T >::cend ( ) const -> const_iterator
nodiscard

Function returns pointer to List last Node.

Returns
const_iterator const iterator to List last Node

Definition at line 1225 of file list.h.

1226 {
1227 return end();
1228 }

◆ clear()

template<typename T>
void dsa::List< T >::clear ( )

Function removes all elements of List.

Definition at line 1249 of file list.h.

1250 {
1251 if (m_head && m_head->m_next)
1252 {
1253 while (m_head->m_next)
1254 {
1255 m_head = std::move(m_head->m_next);
1256 }
1257
1258 m_size = 0;
1259 m_tail->m_prev = nullptr;
1260 }
1261 }

◆ empty()

template<typename T>
auto dsa::List< T >::empty ( ) const -> bool
nodiscard

Function checks if container has no elements.

Return values
trueif container is empty
falseif container is not empty

Definition at line 1231 of file list.h.

1232 {
1233 return m_size == 0;
1234 }

◆ end() [1/2]

template<typename T>
auto dsa::List< T >::end ( ) -> iterator

Function returns pointer to List last Node.

Returns
iterator iterator to List last Node

Definition at line 1213 of file list.h.

1214 {
1215 return iterator(m_tail);
1216 }

◆ end() [2/2]

template<typename T>
auto dsa::List< T >::end ( ) const -> const_iterator

Function returns pointer to List last Node.

Returns
const_iterator const iterator to List last Node

Definition at line 1219 of file list.h.

1220 {
1221 return const_iterator(m_tail);
1222 }

◆ erase() [1/4]

template<typename T>
auto dsa::List< T >::erase ( const_iterator first,
const_iterator last ) -> iterator

Function erases Node objects in range [first, last)

Parameters
[in]firstelement to erase
[in]lastelement after last erased element
Returns
iterator following last erased element
Return values
iteratorto last
enditerator if last was end element prior to removal
lastiterator if first to last is empty range

◆ erase() [2/4]

template<typename T>
auto dsa::List< T >::erase ( const_iterator pos) -> iterator

Function erases Node object at specified pos.

Parameters
[in]positerator to element to erase
Returns
iterator following erased element
Return values
iteratorto element following pos
beginiterator if pos was first element prior to removal
enditerator if pos was last element prior to removal

◆ erase() [3/4]

template<typename T>
auto dsa::List< T >::erase ( iterator first,
iterator last ) -> iterator

Function erases Node objects in range [first, last)

Parameters
[in]firstelement to erase
[in]lastelement after last erased element
Returns
iterator following last erased element
Return values
iteratorto last
enditerator if last was end element prior to removal
lastiterator if first to p\ last is empty range

Definition at line 1318 of file list.h.

1319 {
1320 if (!if_valid_iterator(first) || !if_valid_iterator(last))
1321 {
1322 return nullptr;
1323 }
1324
1325 const size_t dist = distance(first, last);
1326 if (dist == 0)
1327 {
1328 return last;
1329 }
1330
1331 iterator iter(first.m_current_node);
1332 for (size_t i = 0; i < dist; i++)
1333 {
1334 iter = erase_element(iter);
1335 }
1336
1337 return iter;
1338 }

◆ erase() [4/4]

template<typename T>
auto dsa::List< T >::erase ( iterator pos) -> iterator

Function erases Node object at specified pos.

Parameters
[in]positerator to element to erase
Returns
iterator following erased element
Return values
iteratorto element following pos
beginiterator if pos was first element prior to removal
enditerator if pos was last element prior to removal

Definition at line 1307 of file list.h.

1308 {
1309 if (!if_valid_iterator(pos))
1310 {
1311 return nullptr;
1312 }
1313
1314 return erase_element(pos);
1315 }

◆ front() [1/2]

template<typename T>
auto dsa::List< T >::front ( ) -> reference

Function returns reference to value stored in List first Node.

Returns
reference to data stored in List first Node

Definition at line 1171 of file list.h.

1172 {
1173 return *begin();
1174 }

◆ front() [2/2]

template<typename T>
auto dsa::List< T >::front ( ) const -> const_reference
nodiscard

Function returns const reference value stored in List first Node.

Returns
const reference to data stored in List first Node

Definition at line 1177 of file list.h.

1178 {
1179 return *cbegin();
1180 }
dsa::List::cbegin
auto cbegin() const -> const_iterator
Function returns const pointer to List first Node.
Definition list.h:1207

◆ get()

template<typename T>
auto dsa::List< T >::get ( size_t index) const -> Node*
nodiscard

Function returns pointer to specific Node of List.

Parameters
[in]indexindex of element
Returns
Node*
Return values
Node*if index is valid
nullptrif invalid index

Definition at line 1768 of file list.h.

1769 {
1770 if (index >= m_size)
1771 {
1772 return nullptr;
1773 }
1774
1775 NodeBase* temp{};
1776
1777 // select list end to look for selected index
1778 enum Mode : std::uint8_t { FRONT, BACK, AUTO };
1779 constexpr Mode mode = Mode::AUTO;
1780
1781
1782 if constexpr (mode == FRONT)
1783 {
1784 // count nodes from front
1785 temp = m_head.get();
1786 for (size_t i = 0; i < index; i++)
1787 {
1788 temp = temp->m_next.get();
1789 }
1790 }
1791 else if constexpr (mode == BACK)
1792 {
1793 // count nodes from back
1794 temp = m_tail->m_prev;
1795 for (size_t i = m_size - 1; i > index; i--)
1796 {
1797 temp = temp->m_prev;
1798 }
1799 }
1800 else // mode == AUTO
1801 {
1802 // optimize counting nodes from front or back
1803 if (index < m_size / 2)
1804 {
1805 temp = m_head.get();
1806 for (size_t i = 0; i < index; i++)
1807 {
1808 temp = temp->m_next.get();
1809 }
1810 }
1811 else
1812 {
1813 temp = m_tail->m_prev;
1814 for (size_t i = m_size - 1; i > index; i--)
1815 {
1816 temp = temp->m_prev;
1817 }
1818 }
1819 }
1820
1821 return dynamic_cast<Node*>(temp);
1822 }
dsa::List::NodeBase
Struct implements base pointer used by List.
Definition list.h:64
dsa::List::Node
Implements Node template class with pointer to adjacent elements.
Definition list.h:128

◆ insert() [1/3]

template<typename T>
auto dsa::List< T >::insert ( const const_iterator & pos,
const_reference value ) -> iterator

Function inserts new Node before specified pos.

Parameters
[in]posconst_iterator to insert element before
[in]valueelement of type T to be inserted before pos
Returns
pointer to List element
Return values
iteratorto inserted value
posif no element was inserted

Definition at line 1264 of file list.h.

1265 {
1266 return insert(pos, 1, value);
1267 }
dsa::List::insert
auto insert(const const_iterator &pos, const_reference value) -> iterator
Function inserts new Node before specified pos.
Definition list.h:1264

◆ insert() [2/3]

template<typename T>
auto dsa::List< T >::insert ( const const_iterator & pos,
size_t count,
const_reference value ) -> iterator

Function inserts new Node before specified pos.

Parameters
[in]posconst_iterator to insert element before
[in]countnumber of elements to insert before pos
[in]valueelement of type T to be inserted
Returns
pointer to List element
Return values
iteratorto inserted value
posif no element was inserted

Definition at line 1270 of file list.h.

1271 {
1272 iterator iter{ pos.m_current_node };
1273
1274 if (!if_valid_iterator(pos))
1275 {
1276 return nullptr;
1277 }
1278
1279 for (size_t i = 0; i < count; i++)
1280 {
1281 iter = insert_element_before(iter, value);
1282 }
1283
1284 return iter;
1285 }

◆ insert() [3/3]

template<typename T>
auto dsa::List< T >::insert ( const const_iterator & pos,
std::initializer_list< T > init_list ) -> iterator

Function inserts new Node before specified pos.

Parameters
[in]posconst_iterator to insert element before
[in]init_listinitializer_list with elements to insert before pos
Returns
pointer to List element
Return values
iteratorto first inserted element
posif no element was inserted

Definition at line 1288 of file list.h.

1289 {
1290 iterator iter(pos.m_current_node);
1291
1292 if (!if_valid_iterator(pos))
1293 {
1294 return nullptr;
1295 }
1296
1297 for (const auto& val : init_list)
1298 {
1299 iter = insert_element_before(iter, val);
1300 ++iter;
1301 }
1302
1303 return iter;
1304 }

◆ max_size()

template<typename T>
auto dsa::List< T >::max_size ( ) const -> size_t
nodiscard

Function returns maximum number of elements container can hold.

Returns
size_t maximum number of elements

Definition at line 1243 of file list.h.

1244 {
1245 return std::numeric_limits<size_t>::max();
1246 }

◆ merge() [1/2]

template<typename T>
void dsa::List< T >::merge ( List< T > && other)

Function combines two sorted Lists into one sorted List.

Parameters
[in,out]othercontainer to take elements from

Content of other object will be taken by constructed object

Definition at line 1481 of file list.h.

1482 {
1483 if (&other != this)
1484 {
1485 if (m_size != 0)
1486 {
1487 auto temp_head = std::make_unique<Node>(0);
1488 NodeBase* temp_tail = temp_head.get();
1489
1490 std::unique_ptr<NodeBase> to_move{};
1491 std::unique_ptr<NodeBase> to_return{};
1492
1493 std::unique_ptr<NodeBase> sentinel_this{ std::move(m_tail->m_prev->m_next) };
1494 const std::unique_ptr<NodeBase> sentinel_other{ std::move(other.m_tail->m_prev->m_next) };
1495
1496 while (m_head && other.m_head)
1497 {
1498 Node* node_this = dynamic_cast<Node*>(m_head.get());
1499 Node* node_other = dynamic_cast<Node*>(other.m_head.get());
1500
1501 if (node_this && node_other)
1502 {
1503 if (node_this->value() <= node_other->value())
1504 {
1505 to_move = std::move(m_head);
1506 to_move->m_prev = temp_tail;
1507
1508 to_return = std::move(to_move->m_next);
1509 temp_tail->m_next = std::move(to_move);
1510 m_head = std::move(to_return);
1511 }
1512 else
1513 {
1514 to_move = std::move(other.m_head);
1515 to_move->m_prev = temp_tail;
1516
1517 to_return = std::move(to_move->m_next);
1518 temp_tail->m_next = std::move(to_move);
1519 other.m_head = std::move(to_return);
1520 }
1521
1522 temp_tail = temp_tail->m_next.get();
1523 }
1524 }
1525
1526 NodeBase* last{};
1527 if (m_head == nullptr) // other.m_head attached at the end
1528 {
1529 last = sentinel_other->m_prev;
1530 other.m_head->m_prev = temp_tail;
1531 temp_tail->m_next = std::move(other.m_head);
1532 }
1533 else // this.m_head attached at the end
1534 {
1535 last = sentinel_this->m_prev;
1536 m_head->m_prev = temp_tail;
1537 temp_tail->m_next = std::move(m_head);
1538 }
1539 last->m_next = std::move(sentinel_this);
1540 last->m_next->m_prev = last;
1541
1542 m_head = std::move(temp_head->m_next);
1543 m_head->m_prev = nullptr;
1544
1545 m_size += other.m_size;
1546 other.m_size = 0;
1547 }
1548 else
1549 {
1550 swap(other);
1551 }
1552 }
1553 }
dsa::List::swap
void swap(List< T > &other) noexcept
Function swaps content of two List objects.
Definition list.h:1465

◆ merge() [2/2]

template<typename T>
void dsa::List< T >::merge ( List< T > & other)

Function combines two sorted Lists into one sorted List.

Parameters
[in,out]othercontainer to take elements from

Content of other object will be taken by constructed object

Definition at line 1473 of file list.h.

1474 {
1475 merge(std::move(other));
1476 }
dsa::List::merge
void merge(List< T > &other)
Function combines two sorted Lists into one sorted List.
Definition list.h:1473

◆ operator+=() [1/2]

template<typename T>
auto dsa::List< T >::operator+= ( const List< T > & other) -> List<T>&
inline

Append elements of another List to base container.

Template Parameters
Ttype of data stored in List Node
Parameters
[in]otherList to read elements from
Returns
List<T>&

Definition at line 860 of file list.h.

861 {
862 for (auto it = other.cbegin(); it != other.cend(); ++it)
863 {
864 push_back(*it);
865 }
866
867 return *this;
868 }

◆ operator+=() [2/2]

template<typename T>
auto dsa::List< T >::operator+= ( const std::initializer_list< T > init_list) -> List<T>&
inline

push_back elements of another List to base container

Parameters
[in]init_listinitializer_list to read elements from
Returns
List<T>&

Definition at line 876 of file list.h.

877 {
878 for (const auto& item : init_list)
879 {
880 push_back(item);
881 }
882
883 return *this;
884 }

◆ operator=() [1/2]

template<typename T>
auto dsa::List< T >::operator= ( const List< T > & other) -> List&

Constructs List using copy assignment.

Parameters
[in]otherList object of type T
Returns
List&

Definition at line 1099 of file list.h.

1100 {
1101 if (&other != this)
1102 {
1103 while (m_head->m_next)
1104 {
1105 pop_front();
1106 }
1107
1108 for (size_t i = 0; i < other.size(); i++)
1109 {
1110 push_back(other.get(i)->value());
1111 }
1112 }
1113
1114 return *this;
1115 }
dsa::List::pop_front
void pop_front()
Function removes first Node of List.
Definition list.h:1363

◆ operator=() [2/2]

template<typename T>
auto dsa::List< T >::operator= ( List< T > && other) -> List&
noexcept

Assign List object using move assignment.

Content of other object will be taken by constructed object

Parameters
[in,out]otherList object of type T
Returns
List&

Definition at line 1124 of file list.h.

1125 {
1126 if (&other != this)
1127 {
1128 clear();
1129
1130 m_head = std::move(other.m_head);
1131 m_tail = std::move(other.m_tail);
1132 m_size = other.m_size;
1133
1134 other.m_head = nullptr;
1135 other.m_tail = nullptr;
1136 other.m_size = 0;
1137 }
1138
1139 return *this;
1140 }

◆ pop_back()

template<typename T>
void dsa::List< T >::pop_back ( )

Function removes last Node of List.

Definition at line 1409 of file list.h.

1410 {
1411 if (m_size == 0)
1412 {
1413 return;
1414 }
1415
1416 if (m_size == 1)
1417 {
1418 m_head = std::move(m_head->m_next);
1419 m_tail->m_prev = nullptr;
1420 }
1421 else
1422 {
1423 NodeBase* temp{ m_tail->m_prev->m_prev };
1424 m_tail->m_prev->m_prev->m_next = std::move(m_tail->m_prev->m_next);
1425 m_tail->m_prev = temp;
1426 }
1427
1428 m_size--;
1429 }

◆ pop_front()

template<typename T>
void dsa::List< T >::pop_front ( )

Function removes first Node of List.

Definition at line 1363 of file list.h.

1364 {
1365 if (m_size == 0)
1366 {
1367 return;
1368 }
1369
1370 if (m_size == 1)
1371 {
1372 m_head = std::move(m_head->m_next);
1373 m_tail->m_prev = nullptr;
1374 }
1375 else
1376 {
1377 m_head = std::move(m_head->m_next);
1378 m_head->m_prev = nullptr;
1379 }
1380
1381 m_size--;
1382 }

◆ push_back()

template<typename T>
void dsa::List< T >::push_back ( T value)

Function adds new Node at the end of List.

Parameters
[in]valueelement of type T

Definition at line 1385 of file list.h.

1386 {
1387 init_node();
1388
1389 auto newNode = std::make_unique<Node>(value);
1390
1391 if (!m_head->m_next) // only sentinel exists
1392 {
1393 newNode->m_next = std::move(m_head);
1394 m_head = std::move(newNode);
1395 m_tail->m_prev = m_head.get();
1396 }
1397 else
1398 {
1399 newNode->m_prev = m_tail->m_prev;
1400 newNode->m_next = std::move(m_tail->m_prev->m_next);
1401 m_tail->m_prev = newNode.get();
1402 m_tail->m_prev->m_prev->m_next = std::move(newNode);
1403 }
1404
1405 m_size++;
1406 }

◆ push_front()

template<typename T>
void dsa::List< T >::push_front ( T value)

Function adds new Node at the beginning of List.

Parameters
[in]valueelement of type T

Definition at line 1341 of file list.h.

1342 {
1343 init_node();
1344
1345 auto newNode = std::make_unique<Node>(value);
1346 if (!m_head->m_next)
1347 {
1348 newNode->m_next = std::move(m_head);
1349 m_head = std::move(newNode);
1350 m_tail->m_prev = m_head.get();
1351 }
1352 else
1353 {
1354 m_head->m_prev = newNode.get();
1355 newNode->m_next = std::move(m_head);
1356 m_head = std::move(newNode);
1357 }
1358
1359 m_size++;
1360 }

◆ remove()

template<typename T>
void dsa::List< T >::remove ( const_reference value)

Function removes all elements equal to value.

Parameters
[in]valuevalue of elements to remove

Definition at line 1661 of file list.h.

1662 {
1663 NodeBase* temp{ m_head.get() };
1664 NodeBase* next{};
1665
1666 while (temp->m_next.get())
1667 {
1668 next = temp->m_next.get();
1669
1670 if (Node* node = dynamic_cast<Node*>(m_head.get()))
1671 {
1672 if (node->value() == value)
1673 {
1674 pop_front();
1675 temp = m_head.get();
1676 continue;
1677 }
1678 }
1679
1680 if (next && next != m_tail && next->m_next != nullptr)
1681 {
1682 Node* node = dynamic_cast<Node*>(next);
1683 if (node->value() == value)
1684 {
1685 erase(ListIterator<false>(node));
1686 continue;
1687 }
1688 }
1689
1690 temp = temp->m_next.get();
1691 }
1692 }
dsa::List::ListIterator
Implements ListIterator.
Definition list.h:183
dsa::List::erase
auto erase(iterator pos) -> iterator
Function erases Node object at specified pos.
Definition list.h:1307

◆ resize() [1/2]

template<typename T>
void dsa::List< T >::resize ( size_t count)

Function resize List to specified number of elements.

Parameters
[in]countnew size of container

Definition at line 1432 of file list.h.

1433 {
1434 resize(count, T{});
1435 }
dsa::List::resize
void resize(size_t count)
Function resize List to specified number of elements.
Definition list.h:1432

◆ resize() [2/2]

template<typename T>
void dsa::List< T >::resize ( size_t count,
const_reference value )

Function resize List to specified number of elements.

Parameters
[in]countcount new size of container
[in]valuevalue to initialize new elements

Definition at line 1438 of file list.h.

1439 {
1440 if (count == m_size)
1441 {
1442 return;
1443 }
1444
1445 if (m_size > count)
1446 {
1447 // container is reduced to its count elements
1448 while (m_size > count)
1449 {
1450 pop_back();
1451 }
1452 }
1453
1454 if (m_size < count)
1455 {
1456 // additional copies of value are appended
1457 while (m_size < count)
1458 {
1459 push_back(value);
1460 }
1461 }
1462 }
dsa::List::pop_back
void pop_back()
Function removes last Node of List.
Definition list.h:1409

◆ reverse()

template<typename T>
void dsa::List< T >::reverse ( )

Function reverts in place Nodes of List.

Definition at line 1695 of file list.h.

1696 {
1697 if (m_head->m_next == nullptr)
1698 {
1699 return;
1700 }
1701
1702 NodeBase* new_back{ m_head.get() };
1703 std::unique_ptr<NodeBase> sentinel = std::move(m_tail->m_prev->m_next);
1704
1705 std::unique_ptr<NodeBase> temp = std::move(m_head);
1706 std::unique_ptr<NodeBase> prev{};
1707
1708 for (size_t i = 0; i < m_size; i++)
1709 {
1710 std::unique_ptr<NodeBase> next = std::move(temp->m_next);
1711 temp->m_next = std::move(prev);
1712 temp->m_prev = next.get();
1713
1714 prev = std::move(temp);
1715 temp = std::move(next);
1716 }
1717
1718 m_head = std::move(prev);
1719 m_tail->m_prev = new_back;
1720 m_tail->m_prev->m_next = std::move(sentinel);
1721 }

◆ set()

template<typename T>
auto dsa::List< T >::set ( size_t index,
T value ) -> bool

Function sets value of specifed Node of List.

Parameters
[in]indexindex of element to be modified
[in]valueto overwrite Node at index
Returns
operation status
Return values
trueif value of Node was overwritten
falseif invalid index

Definition at line 1825 of file list.h.

1826 {
1827 Node* temp = get(index);
1828 if (temp)
1829 {
1830 temp->m_value = value;
1831 return true;
1832 }
1833
1834 return false;
1835 }

◆ size()

template<typename T>
auto dsa::List< T >::size ( ) const -> size_t
nodiscard

Function returns List size.

Returns
size_t number of elements in container

Definition at line 1237 of file list.h.

1238 {
1239 return m_size;
1240 }

◆ splice() [1/6]

template<typename T>
void dsa::List< T >::splice ( const const_iterator & pos,
List< T > & other )

Function moves elements from other List object.

Parameters
[in]posconst_iterator before which content of other container will be inserted
[in,out]othercontainer to take elements from

Content of other object will be taken by constructed object

Definition at line 1624 of file list.h.

1625 {
1626 transfer(pos, std::move(other), other.begin(), other.end());
1627 }

◆ splice() [2/6]

template<typename T>
void dsa::List< T >::splice ( const const_iterator & pos,
List< T > & other,
const const_iterator & first,
const const_iterator & last )

Function moves elements in range [first, last) from other List object.

Parameters
[in]posconst_iterator before which content of other container will be inserted
[in,out]othercontainer to take elements from
[in]firstconst_iterator pointing to first element to move
[in]lastconst_iterator pointing to element after last taken element

Content of other object will be taken by constructed object

Definition at line 1648 of file list.h.

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

◆ splice() [3/6]

template<typename T>
void dsa::List< T >::splice ( const const_iterator & pos,
List< T > & other,
const const_iterator & iter )

Function moves elements from other List object.

Parameters
[in]posconst_iterator before which content of other container will be inserted
[in,out]othercontainer to take elements from
[in]iterconst_iterator pointing to element to move

Content of other object will be taken by constructed object

Definition at line 1636 of file list.h.

1637 {
1638 transfer(pos, std::move(other), iter, iter.m_current_node->m_next.get());
1639 }

◆ splice() [4/6]

template<typename T>
void dsa::List< T >::splice ( const_iterator pos,
List< T > && other )

Function moves elements from other List object.

Parameters
[in]posconst_iterator before which content of other container will be inserted
[in,out]othercontainer to take elements from

Content of other object will be taken by constructed object

Definition at line 1630 of file list.h.

1631 {
1632 transfer(pos, std::move(other), other.begin(), other.end());
1633 }

◆ splice() [5/6]

template<typename T>
void dsa::List< T >::splice ( const_iterator pos,
List< T > && other,
const_iterator first,
const_iterator last )

Function moves elements in range [first, last) from other List object.

Parameters
[in]posconst_iterator before which content of other container will be inserted
[in,out]othercontainer to take elements from
[in]firstconst_iterator pointing to first element to move
[in]lastconst_iterator pointing to element after last taken element

Content of other object will be taken by constructed object

Definition at line 1655 of file list.h.

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

◆ splice() [6/6]

template<typename T>
void dsa::List< T >::splice ( const_iterator pos,
List< T > && other,
const_iterator iter )

Function moves elements from other List object.

Parameters
[in]posconst_iterator before which content of other container will be inserted
[in,out]othercontainer to take elements from
[in]iterconst_iterator pointing to element to move

Content of other object will be taken by constructed object

Definition at line 1642 of file list.h.

1643 {
1644 transfer(pos, std::move(other), iter, iter.m_current_node->m_next.get());
1645 }

◆ swap()

template<typename T>
void dsa::List< T >::swap ( List< T > & other)
noexcept

Function swaps content of two List objects.

Parameters
[in,out]otherobject to swap content with

Definition at line 1465 of file list.h.

1466 {
1467 std::swap(m_head, other.m_head);
1468 std::swap(m_tail, other.m_tail);
1469 std::swap(m_size, other.m_size);
1470 }

◆ unique()

template<typename T>
void dsa::List< T >::unique ( )

Function removes consecutive duplicated elements.

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

Definition at line 1724 of file list.h.

1725 {
1726 NodeBase* temp{ m_head.get() };
1727 NodeBase* prev{};
1728 NodeBase* next{};
1729 while (temp)
1730 {
1731 prev = temp;
1732
1733 while (prev)
1734 {
1735 next = prev->m_next.get();
1736
1737 Node* node_next = dynamic_cast<Node*>(next);
1738 Node* node_temp = dynamic_cast<Node*>(temp);
1739 if (node_next && node_temp)
1740 {
1741 if (node_next->value() == node_temp->value())
1742 {
1743 NodeBase* to_remove = next;
1744
1745 if (to_remove->m_next)
1746 {
1747 to_remove->m_next->m_prev = prev;
1748 }
1749 else // temp was last node
1750 {
1751 m_tail = prev;
1752 }
1753
1754 prev->m_next = std::move(to_remove->m_next);
1755
1756 m_size--;
1757 continue;
1758 }
1759 }
1760
1761 prev = prev->m_next.get();
1762 temp = temp->m_next.get();
1763 }
1764 }
1765 }

◆ operator+

template<typename T>
auto operator+ ( const List< T > & list1,
const List< T > & list2 ) -> List<T>
friend

Construct new object based on two List objects.

Forward friend declaration of List operator+

Template Parameters
Ttype of data stored in List Node
Parameters
[in]list1input List
[in]list2input List
Returns
List<T> List<T> with content of two input lists
Template Parameters
Ttype of data stored in List Node
Parameters
[in]list1input List
[in]list2input List
Returns
List<T> List<T> with content of two input lists

Definition at line 1846 of file list.h.

1847 {
1848 List<T> temp(list1);
1849
1850 for (auto iter = list2.cbegin(); iter != list2.cend(); ++iter)
1851 {
1852 T value = *iter;
1853 temp.push_back(value);
1854 }
1855
1856 return temp;
1857 }
The documentation for this class was generated from the following file: