• Structural
  • list::list(constructor) - Allocates or constructs a list in several ways: empty, n copies of the same value, from a sublist of another list object, or as a duplicate of another list object. The different uses require different parameters.
  • list::~list(destructor) - Deallocates or destructs a list. It invokes destructors for all of the elements in the list and then deallocates the memory associated with the list object.
  • list::operator= - Performs the semantics of an assignment between two lists, which means it copies list B into list A and destroys the old contents of list A when used as A = B.
• Iterators
  • list::begin - Returns an iterator to start traversal of the list from the beginning, and can be thought of being used to traverse the next links in the doubly-linked list.
  • list::end - Returns an iterator that points just beyond the end of the list.
  • list::rbegin - Returns an iterator to start traversal of the list from the end, and can be thought of being used to traverse the previous links in the doubly-linked list.
  • list::rend - Returns an iterator that points just beyond the reverse end (the special node before list::begin()).
• Capacity
  • list::size - Returns number of elements in the list.
  • list::empty - Returns true if list has no elements.
  • list::max_size - Returns the maximum number of elements that can be stored in the list object. This is implementation dependent because in general list are not thought of as having a maximum size.
  • list::resize - Resizes the list based on an integer argument. If the argument is less than the current size then the extra elements are deallocated. If the argument is greater than the current size, then new empty elements are appended to the end of the list. This resize does not work like the vector resize in that it does not automatically double the size of the list. It only adds enough nodes to get the size up to the value of the argument.
• Element Access
  • list::front - Returns reference to first element of list.
  • list::back - Returns reference to last element of list.
• Modifiers
  • list::assign - Puts new contents into the list based on iterators to change a sublist of the list or a constant to set the entire list to that value.
  • list::push_back - Appends (inserts) an element to the end of a list. It allocates memory for the new element.
  • list::push_front - Prepends (inserts) an element to the front of a list. It allocates memory for the new element.
  • list::pop_back - Erases the last element of the list, and deallocates the memory associated with the element.
  • list::pop_front - Erases the first element of the list, and deallocates the memory associated with the element.
  • list::erase - Deletes elements from a list. It can delete a single element or a range of consecutive elements using two iterators for the range.
  • list::insert - Inserts elements into a list. It can insert a single element or a range of consecutive elements from another list. The insertions happen previous to the selected position denoted by an iterator.
  • list::clear - Erases all of the elements.
• Other Operations
  • list::remove_if - Removes elements from the list based on a boolean condition. A predicate function or functor must be created to evaluate the condition.
  • list::unique - Removes duplicate elements from the list. An equality operator overload must be created for elements of user-defined types.
  • list::sort - Sorts the elements in the list. An ordering operator must be created as an operator overload for the element type. Sorting can be done in ascending or descending order.

There are other operations that are available as a part of the list class and there are algorithms that are part of the C++ STL (Algorithm (C++)) that can be used with the list class.

[edit] List Iterators

The list class makes thorough use of iterators because all element access is done via an iterator. The list class uses forward and reverse iterators. However, it does not use the random access iterator (used by the vector class). This is because the random access iterator relies on the elements being stored in consecutive memory locations. The elements of the list class are not stored in consecutive or even necessarily adjacent locations.

[edit] Capacity and Allocation

List implementations are based on a dynamically allocated linked data structure such as a doubly-linked list. Because of this, the list objects allocate memory for elements as the elements are added to the list and deallocate memory as elements are removed from the list. Removing and adding elements to a linked structure are O(1) at the point of insertion or deletion. The list class only requires the amount of memory that it is currently using for data. There is a concept of a list having a maximum size. This is implementation dependent, but is tied to maximum heap size allowed by the platform. When memory is allocated in the list, the allocations are dynamic and involve performing a new (new (C++)) or malloc (malloc operation. Both of these operations allocate memory from the processes heap memory space by making an operating system request. The operating system can either satisfy or deny the requests. In some cases, the decision to deny or satisfy the request is dependent on the state of the machine at that given time; and therefore, it is not always clear what the maximum size of the list could be.

One of the problems with iterators in vectors is that they become invalid when the vector is resized explicitly or implicitly. This is because the memory location of the vector is likely to change after a resize. This is not the case with a list because there is no constraint on the elements of the list to be adjacent in consecutive memory locations as with a vector or array. Therefore, iterators are always valid before and after additions and deletions unless the iterator is referring to an element that is actually deleted.

[edit] Usage

A C++ program that is to use lists must #include <list>. A list is declared using:

std::list<T> instance;