Forward list cpp reference

std:: forward_list

std::forward_list is a container that supports fast insertion and removal of elements from anywhere in the container. Fast random access is not supported. It is implemented as a singly-linked list. Compared to std::list this container provides more space efficient storage when bidirectional iteration is not needed.

Adding, removing and moving the elements within the list, or across several lists, does not invalidate the iterators currently referring to other elements in the list. However, an iterator or reference referring to an element is invalidated when the corresponding element is removed (via erase_after ) from the list.

std::forward_list meets the requirements of Container (except for the size member function and that operator== ‘s complexity is always linear), AllocatorAwareContainer and SequenceContainer .

Contents

[edit] Template parameters

The requirements that are imposed on the elements depend on the actual operations performed on the container. Generally, it is required that element type meets the requirements of Erasable , but many member functions impose stricter requirements. This container (but not its members) can be instantiated with an incomplete element type if the allocator satisfies the allocator completeness requirements.

[edit] Member types

Member type	Definition
value_type	T [edit]
allocator_type	Allocator [edit]
size_type	Unsigned integer type (usually std::size_t ) [edit]
difference_type	Signed integer type (usually std::ptrdiff_t ) [edit]
reference	value_type& [edit]
const_reference	const value_type & [edit]
pointer	std:: allocator_traits < Allocator >:: pointer [edit]
const_pointer	std:: allocator_traits < Allocator >:: const_pointer [edit]
iterator	LegacyForwardIterator to value_type [edit]
const_iterator	LegacyForwardIterator to const value_type [edit]

Источник

std:: forward_list

Forward lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence.

Forward lists are implemented as singly-linked lists; Singly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept by the association to each element of a link to the next element in the sequence.

The main design difference between a forward_list container and a list container is that the first keeps internally only a link to the next element, while the latter keeps two links per element: one pointing to the next element and one to the preceding one, allowing efficient iteration in both directions, but consuming additional storage per element and with a slight higher time overhead inserting and removing elements. forward_list objects are thus more efficient than list objects, although they can only be iterated forwards.

Compared to other base standard sequence containers (array, vector and deque), forward_list perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

The main drawback of forward_lists and lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a forward_list one has to iterate from the beginning to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

The forward_list class template has been designed with efficiency in mind: By design, it is as efficient as a simple handwritten C-style singly-linked list, and in fact is the only standard container to deliberately lack a size member function for efficiency considerations: due to its nature as a linked list, having a size member that takes constant time would require it to keep an internal counter for its size (as list does). This would consume some extra storage and make insertion and removal operations slightly less efficient. To obtain the size of a forward_list object, you can use the distance algorithm with its begin and end, which is an operation that takes linear time.

Container properties

Sequence Elements in sequence containers are ordered in a strict linear sequence. Individual elements are accessed by their position in this sequence. Linked list Each element keeps information on how to locate the next element, allowing constant time insert and erase operations after a specific element (even of entire ranges), but no direct random access. Allocator-aware The container uses an allocator object to dynamically handle its storage needs.

Template parameters

T Type of the elements.
Aliased as member type forward_list::value_type. Alloc Type of the allocator object used to define the storage allocation model. By default, the allocator class template is used, which defines the simplest memory allocation model and is value-independent.
Aliased as member type forward_list::allocator_type.

Member types

member type	definition	notes
value_type	The first template parameter (T)
allocator_type	The second template parameter (Alloc)	defaults to: allocator
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits::pointer	for the default allocator: value_type*
const_pointer	allocator_traits::const_pointer	for the default allocator: const value_type*
iterator	a forward iterator to value_type	convertible to const_iterator
const_iterator	a forward iterator to const value_type
difference_type	a signed integral type, identical to: iterator_traits::difference_type	usually the same as ptrdiff_t
size_type	an unsigned integral type that can represent any non-negative value of difference_type	usually the same as size_t

Member functions

(constructor) Construct forward_list object (public member function) (destructor) Destroy forward_list object (public member function) operator= Assign content (public member function)

Iterators

before_begin Return iterator to before beginning (public member function) begin Return iterator to beginning (public member type) end Return iterator to end (public member function) cbefore_begin Return const_iterator to before beginning (public member function) cbegin Return const_iterator to beginning (public member function) cend Return const_iterator to end (public member function)

Capacity

empty Test whether array is empty (public member function) max_size Return maximum size (public member function)

Element access

Modifiers

assign Assign content (public member function) emplace_front Construct and insert element at beginning (public member function) push_front Insert element at beginning (public member function) pop_front Delete first element (public member function) emplace_after Construct and insert element (public member function) insert_after Insert elements (public member function) erase_after Erase elements (public member function) swap Swap content (public member function) resize Change size (public member function) clear Clear content (public member function)

Operations

splice_after Transfer elements from another forward_list (public member function) remove Remove elements with specific value (public member function) remove_if Remove elements fulfilling condition (public member function template) unique Remove duplicate values (public member function) merge Merge sorted lists (public member function) sort Sort elements in container (public member function) reverse Reverse the order of elements (public member function)

Observers

Non-member function overloads

relational operators (forward_list) Relational operators for forward_list (function template) swap (forward_list) Exchanges the contents of two forward_list containers (function template)

Источник

std::forward_list:: forward_list

Constructs a new container from a variety of data sources, optionally using a user supplied allocator alloc .

This constructor has the same effect as forward_list ( static_cast < size_type >( first ) , static_cast < value_type >( last ) , a ) if InputIt is an integral type.

This overload participates in overload resolution only if InputIt satisfies LegacyInputIterator , to avoid ambiguity with the overload (3) .

The allocator is obtained as if by calling std:: allocator_traits < allocator_type >:: select_on_container_copy_construction (
other. get_allocator ( ) ) .

During class template argument deduction, only the first argument contributes to the deduction of the container's Allocator template parameter.

8) Move constructor. Constructs the container with the contents of other using move semantics. Allocator is obtained by move-construction from the allocator belonging to other .

9) Allocator-extended move constructor. Using alloc as the allocator for the new container, moving the contents from other ; if alloc ! = other. get_allocator ( ) , this results in an element-wise move.

During class template argument deduction, only the first argument contributes to the deduction of the container's Allocator template parameter.

Contents

[edit] Parameters

alloc	-	allocator to use for all memory allocations of this container
count	-	the size of the container
value	-	the value to initialize elements of the container with
first, last	-	the range [ first , last ) to copy the elements from
other	-	another container to be used as source to initialize the elements of the container with
init	-	initializer list to initialize the elements of the container with
rg	-	a container compatible range, that is, an input_range whose elements are convertible to T

Источник