cplusplus.com cplusplus.com
cplusplus.com   C++ : Reference : STL Containers : list
- -
C++
Information
Documentation
Reference
Articles
Sourcecode
Forum
Reference
C Library
IOstream Library
Strings library
STL Containers
STL Algorithms
STL Containers
bitset
deque
list
map
multimap
multiset
priority_queue
queue
set
stack
vector
list
comparison operators
list::list
list::~list
member functions:
· list::assign
· list::back
· list::begin
· list::clear
· list::empty
· list::end
· list::erase
· list::front
· list::get_allocator
· list::insert
· list::max_size
· list::merge
· list::operator=
· list::pop_back
· list::pop_front
· list::push_back
· list::push_front
· list::rbegin
· list::remove
· list::remove_if
· list::rend
· list::resize
· list::reverse
· list::size
· list::sort
· list::splice
· list::swap
· list::unique

-

list class template
<list>

List

Lists are a kind of sequence containers. As such, their elements are ordered following a linear sequence.

List containers are implemented as doubly-linked lists; Doubly 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 element preceding it and a link to the element following it.

This provides the following advantages to list containers:

  • Efficient insertion and removal of elements anywhere in the container (constant time).
  • Efficient moving elements and block of elements within the container or even between different containers (constant time).
  • Iterating over the elements in forward or reverse order (linear time).

Compared to other base standard sequence containers (vectors and deques), lists 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 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 list one has to iterate from a known position (like the beginning or the end) 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).

Storage is handled automatically by the class, allowing lists to be expanded and contracted as needed.

In their implementation in the C++ Standard Template Library lists take two template parameters:

template < class T, class Allocator = allocator<T> > class list;
Where the template parameters have the following meanings:
  • T: Type of the elements.
  • Allocator: Type of the allocator object used to define the storage allocation model. By default, the allocator class template for type T is used, which defines the simplest memory allocation model and is value-independent.
In the reference for the list member functions, these same names are assumed for the template parameters.

Member functions

(constructor) Construct list (public member function)
(destructor) List destructor (public member function)
operator= Copy container content (public member function)

Iterators:

begin Return iterator to beginning (public member function)
end Return iterator to end (public member function)
rbegin Return reverse iterator to reverse beginning (public member function)
rend Return reverse iterator to reverse end (public member function)

Capacity:

empty Test whether container is empty (public member function)
size Return size (public member function)
max_size Return maximum size (public member function)
resize Change size (public member function)

Element access:

front Access first element (public member function)
back Access last element (public member function)

Modifiers:

assign Assign new content to container (public member function)
push_front Insert element at beginning (public member function)
pop_front Delete first element (public member function)
push_back Add element at the end (public member function)
pop_back Delete last element (public member function)
insert Insert elements (public member function)
erase Erase elements (public member function)
swap Swap content (public member function)
clear Clear content (public member function)

Operations:

splice Move elements from list to 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 (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)

Allocator:

get_allocator Get allocator (public member function)

Member types

of template <class T, class Allocator=allocator<T> > class list;

member typedefinition
referenceAllocator::reference
const_referenceAllocator::const_reference
iteratorBidirectional iterator
const_iteratorConstant bidirectional iterator
size_typeUnsigned integral type (usually same as size_t)
difference_typeSigned integral type (usually same as ptrdiff_t)
value_typeT
allocator_typeAllocator
pointerAllocator::pointer
const_pointerAllocator::const_pointer
reverse_iteratorreverse_iterator<iterator>
const_reverse_iteratorreverse_iterator<const_iterator>

© The C++ Resources Network, 2000-2007 - All rights reserved
Spotted an error? - contact us