|
| | LinkedList () noexcept(noexcept(Allocator())) |
| |
| | LinkedList (const Allocator &alloc) |
| |
| | LinkedList (size_t count, const value_type &value=value_type(), const Allocator &alloc=Allocator()) |
| | Constructs count elements with given value.
|
| |
| template<InputIterator Iter> |
| | LinkedList (Iter first, Iter last, const Allocator &alloc=Allocator()) |
| | Initialize list with the given range.
|
| |
| | LinkedList (std::initializer_list< value_type > init_list, const Allocator &alloc=Allocator()) |
| | Initialize list with the given initializer_list.
|
| |
| | LinkedList (const LinkedList &other) |
| | Copy constructor.
|
| |
| | LinkedList (LinkedList &&other) noexcept(noexcept(Allocator(move(other.alloc_)))) |
| | Move constructor. No iterators are invalidated.
|
| |
| LinkedList & | operator= (LinkedList other) |
| | Copy/move assignment operator.
|
| |
| | ~LinkedList () |
| |
| void | swap (LinkedList &other) |
| | Effectively swaps content of the lists.
|
| |
| void | clear () noexcept |
| | Removes all elements in the list.
|
| |
| iterator | insertAfter (const_iterator pos, value_type value) |
| | Creates element and places it after the given iterator.
|
| |
| iterator | insertAfter (const_iterator pos, std::initializer_list< T > init_list) |
| | Inserts elements from initializer list in the list.
|
| |
| template<InputIterator Iter> |
| iterator | insertAfter (const_iterator pos, Iter first, Iter last) |
| | Inserts elements from [first, last) in the list after pos.
|
| |
| template<typename... Args> |
| iterator | emplaceAfter (const_iterator pos, Args &&... args) |
| | Creates new node from given arguments and places it after the given position.
|
| |
| template<typename... Args> |
| reference | emplaceFront (Args &&... args) |
| | Creates new node from given arguments in the start of the list.
|
| |
| template<typename... Args> |
| reference | emplaceBack (Args &&... args) |
| | Creates new node from given arguments in the end of the list.
|
| |
| iterator | eraseAfter (const_iterator pos) noexcept |
| | Destroys element right after pos.
|
| |
| iterator | eraseAfter (const_iterator first, const_iterator last) noexcept |
| | Destroys elements in (first, last).
|
| |
| void | popFront () noexcept |
| | Destroys first element in the list.
|
| |
| void | popBack () noexcept |
| | Destroys last element in the list.
|
| |
| template<typename Cmp = less> |
| void | merge (LinkedList &other, Cmp cmp=Cmp()) |
| | See merge(LinkedList&&, auto)
|
| |
| template<typename Cmp = less> |
| void | merge (LinkedList &&other, Cmp cmp=Cmp()) |
| | Merges elements from 2 sorted lists into one sorted.
|
| |
| iterator | spliceAfter (const_iterator pos, LinkedList &other) |
| | See spliceAfter(const_iterator, LinkedList&&)
|
| |
| iterator | spliceAfter (const_iterator pos, LinkedList &&other) |
| | Transfers all elements from other to *this. other becomes empty.
|
| |
| iterator | spliceAfter (const_iterator pos, LinkedList &other, const_iterator first, const_iterator last) |
| | See spliceAfter(const_iterator, LinkedList&&, const_iterator, const_iterator)
|
| |
| iterator | spliceAfter (const_iterator pos, LinkedList &&other, const_iterator first, const_iterator last) |
| | Transfers all elements in (first, last) from other to *this right after pos.
|
| |
| void | reverse () noexcept |
| | Reverses linked list.
|
| |
| reference | front () noexcept |
| | Returns first element in the list.
|
| |
| const_reference | front () const noexcept |
| | Returns first element in the list.
|
| |
| reference | back () noexcept |
| | Returns last element in the list.
|
| |
| const_reference | back () const noexcept |
| | Returns last element in the list.
|
| |
| Node * | getRawFirstNode () const noexcept |
| | Returns raw representation of the first list's node.
|
| |
| size_t | size () const noexcept |
| | Returns list's size.
|
| |
| bool | isEmpty () const noexcept |
| | Checks whether list has elements.
|
| |
| allocator_type | getAllocator () const |
| |
| iterator | begin () noexcept |
| |
| iterator | end () noexcept |
| |
| const_iterator | begin () const noexcept |
| |
| const_iterator | end () const noexcept |
| |
| const_iterator | cbegin () const noexcept |
| |
| const_iterator | cend () const noexcept |
| |
| iterator | beforeBegin () noexcept |
| |
| const_iterator | beforeBegin () const noexcept |
| |
| const_iterator | cbeforeBegin () const noexcept |
| |
| iterator | beforeEnd () noexcept |
| |
| const_iterator | beforeEnd () const noexcept |
| |
| const_iterator | cbeforeEnd () const noexcept |
| |
| bool | operator== (const LinkedList &other) const noexcept |
| |
| auto | operator<=> (const LinkedList &other) const noexcept |
| |
Singly linked list.
- Template Parameters
-
| T | type to hold |
| TrackSize | enables fast size access |
| TrackLast | enables fast last element access |
| Allocator | allocator to use for memory management |
This implementation may be used in several modes: 1) Memory saving: sizeof this class equals 1 pointer, but methods that use size and last element will work slowly(linearly). 2) Fast size: sizeof this class equals sizeof(void*) + sizeof(size_t), enables access to size for a constant time, 3) Fast last element: sizeof this class equals 2*sizeof(void*), last element access is constant. 4) Fast size and last element: modes 2 + 3
All methods provides strong/basics exception safety(all
strong except the move assignment)
template<typename... Args>
Creates new node from given arguments and places it after the given position.
After this operation, next(pos) will give an iterator to the newly created node.
pos must be valid iterator in [beforeBegin(), end()). Otherwise UB.
No iterators are invalidated.
Time complexity: O(1).
- Parameters
-
| pos | Position to insert after |
| args... | Arguments to forward in the element's c-tor |
- Returns
- iterator to the created element
- Exceptions
-
| Provides | strong exception guarantee |
template<typename... Args>
Creates new node from given arguments in the end of the list.
That's it, places the new node after prev(end()), so it becomes last element in the list.
See emplaceAfter(const_iterator, Args&&...) docs for details.
Time complexity: 1) If TrackLast=true: O(1). 2) If TrackLast=false: O(n) where n=size().
- Parameters
-
| args... | Arguments to forward in the element's c-tor |
- Returns
- iterator to the created element
- Exceptions
-
| Provides | strong exception guarantee |
Destroys elements in (first, last).
That's it, all elements from next(first) to prev(last) are erased. And next(first) becomes equal to last.
first and last must be valid iterators in [beforeBegin(), end()]. Otherwise UB.
No iterators, except ones to the erased elements, are invalidated.
If first==last or next(first)==last, does nothing.
- Parameters
-
| first | Iterator to start the erase after |
| last | Iterator to end the erase before |
- Returns
last
- Exceptions
-
template<InputIterator Iter>
Inserts elements from [first, last) in the list after pos.
That's it, copies elements in [first, last) and places them between pos and next(pos).
pos must be valid iterator in [beforeBegin(), end()). Otherwise UB.
No iterators are invalidated.
Time complexity: O(distance(first, last)) - number elements to insert.
- Parameters
-
| pos | Iterator to place range after |
| first | Start of range |
| last | End of range |
- Returns
- iterator to the last element inserted, or
pos if first==last
- Exceptions
-
| Provides | strong exception guarantee. |
Merges elements from 2 sorted lists into one sorted.
Transfers all elements from other to this, so this is sorted. other becomes empty after this operation.
Assumes that this and other are already sorted according to cmp. If they don't, resulting list will be unpredictably merged. Current implementation is NOT stable.
this->getAllocator() must be equal to other.getAllocator(). Otherwise exception is thrown.
If other refers to this, does nothing.
No iterators are invalidated.
Time complexity: O(max(this->size(), other.size())).
- Parameters
-
| other | List to merge with |
| cmp | Comparator to use |
- Exceptions
-
| Provides | conditional exception safety. If allocators are different - throws std::runtime_error. If a call to cmp throws - no exception guarantee, there will be memory leak. Otherwise noexcept. |
Destroys last element in the list.
If isEmpty()==true, does nothing.
Finds element before the last in the list and calls eraseAfter on it. By construction, to find node before the last one we need to iterate over the whole list.
No iterators, except one to the erased element, are invalidated.
Time complexity: O(n) where n=size().
- Exceptions
-
Transfers all elements from other to *this. other becomes empty.
this->getAllocator() must be equal to other.getAllocator(). Otherwise exception is thrown.
pos must be valid iterator in [beforeBegin(), end()). Otherwise UB.
If other refers to *this, does nothing.
No iterators are invalidated.
Time complexity: 1) If TrackLast==true: O(1). 2) If TrackLast==false: O(other.size()).
- Parameters
-
| pos | Iterator to transfer after |
| other | List to transfer from |
- Returns
- iterator to the last element transferred or
pos
- Exceptions
-
| std::runtime_error | if allocators aren't equal |
Transfers all elements in (first, last) from other to *this right after pos.
If first==last or next(first)==last, does nothing and returns pos.
other can refer to *this. In this case pos must not be in (first, last), otherwise UB - at least memory leak.
this->getAllocator() must be equal to other.getAllocator(). Otherwise exception is thrown.
pos must be valid iterator in [beforeBegin(), end()). Otherwise UB.
No iterators are invalidated.
Time complexity: O(distance(first, last)).
- Parameters
-
| pos | Iterator to transfer range after |
| other | List to transfer from |
| first | Iterator before the element to start cut |
| last | Iterator after the element to stop cut |
- Returns
- iterator to the last element transferred or
pos
- Exceptions
-
| std::runtime_error | if allocators aren't equal |
1.9.8