list<T>

The list container class represents a list of elements that can be accessed sequentially. Unlike vector and deque, list does not support random access. Insertions and deletions from a list can be performed in constant time, and all of the properties of linked lists you have learned from CS106B/X apply to the list container.

list intrinsically supports a huge number of operations normally only accessible through algorithms, such as sort, merge, and splice, which work very quickly over a list.

Common list<T> Member Functions

Constructor: list<T> ()

Constructs a new empty list.

list<int> myList; // Constructs a new, empty list.

Constructs a new list. This is the default constructor.

Constructor: list<T> (size_type numElems)

Constructor: list<T> (size_type numElems, const T &elem)

Constructs a pre-initialized list

list<int> myList(10, 137); // Constructs a list with 10 elements, all 137

list<string> myList(10); // Constructs a list with 10 elements, all the empty string

Constructs a new list with the specified number of copies of the specified element. With a single parameter, this constructor creates a list containing the specified number of elements, all initialized to the default. With two parameters, this constructor creates a list of the specified number of copies of the specified element.

size_type size() const

Get container size

for(int i = 0; i < myList.size(); ++i) { ... }

Returns the number of elements stored in the container.

bool empty() const

Is container empty?

if(myList.empty()) { ... }

Returns whether the list is empty. It's considered good practice to call empty to determine whether the list is empty rather than checking whether size() returns zero.

void clear()

Empty container

myList.clear();

Removes all elements from the list.

void resize(size_type size);

void resize(size_type size, const T& fill);

Resize list

myList.resize(137); // Resizes the list to 137 elements.

myList.resize(137, 42); // Resizes the list to 137 elements, filling new entries with 137

Resizes the list by adding or removing elements from the end of the list. The first version resizes the list to the specified size, trimming elements from the end if the new size is smaller than the old size and padding the end with new objects if the new size is greater than the old size. The newly-added elements are constructed using the default constructor.

The second version of the function works identically to the first, except that any newly-added elements are initialized to have the same value as the parameter.

iterator begin()

const_iterator begin() const

Get start iterator.

for(list<int>::iterator itr = myList.begin(); /* ... */)

Returns an iterator to the first element in the list.

iterator end()

const_iterator end() const

Get stop iterator.

for(/* ... */ itr != myList.end(); /* ... */)

Returns an iterator to the element one past the end of the list. This iterator does not point to a valid element, so do not dereference it.

void push_back(const T& elem);

Append element

myList.push_back(137); // Appends 137 to the end of the list.

Appends the specified element to the back of the list, increasing the size by one.

void pop_back()

Delete last element

myList.pop_back();

Removes the last element in the list. pop_back does not return a value, so if you want to get the value, call back first. pop_back does not do any bounds-checking, so make sure the list is nonempty before calling.

T& back()

const T& back() const

Get last element

int lastElem = myList.back();

Returns a reference to the last element of the list. There is no bounds-checking, so make sure the list is nonempty before calling.

void push_front(const T& elem);

Prepend element

myList.push_front(137); // Prepends 137 to the front of the list.

Prepends the specified element to the front of the list, increasing the size by one.

void pop_front()

Delete first element

myList.pop_front();

Removes the first element in the list. pop_front does not return a value, so if you want to get the value, call front first. pop_front does not do any bounds-checking, so make sure the list is nonempty before calling.

T& front()

const T& front() const

Get first element

int firstElem = myList.front();

Returns a reference to the first element of the list. There is no bounds-checking, so make sure the list is nonempty before calling.

iterator insert(iterator position, const T& elem)

iterator insert(iterator position, size_type numCopies, const T&elem)

iterator insert(iterator position, InputIterator begin, InputIterator end)

Insert elements

myList.insert(myList.begin() + 3, 137); // Insert 137 after the third element

myList.insert(myList.begin() + 3, 42, 137); // Insert 42 copies of 137 after the third element

myList.insert(myList.begin(), otherContainer.begin(), otherContainer.end()); // Insert elements from another container

The first version inserts the specified element at the position indicated by the specified iterator. There is no bounds-checking. The size of the container will grow by one and elements will be shifted down.

The second version inserts the specified number of copies of the specified element at the specified position.

The third version inserts the elements in the specified iterator range into the list at the specified position. The source iterators can be of any type.

iterator erase(iterator position)

iterator erase(iterator start, iterator stop)

Remove elements

myList.erase(myList.begin() + 7); // Erase seventh element.

myList.erase(myList.begin(), myList.end() - 4); // Erase all but last four elements

Removes elements from the list without bounds-checking. The first version removes the element pointed at by the iterator, and the second removes all elements in the specified range.

list<T> Utility Member Functions

void merge(list<T> &other)

void merge(list<T> &other, CompareFunction comp)

Merge two lists

sortedList1.merge(sortedList2); // Merges the two lists, emptying sortedList2

Assuming that the list is sorted, merges the list and the other sorted list other so that the calling list now contains the elements of both lists in sorted order. The parameter other becomes empty. If the two lists are sorted according to a special comparison function, you can specify it as the second parameter to the function.

This function is best illustrated by example. Suppose you have two list<int>s, list1 and list2. The contents of list1 are

{0, 2, 4, 6, 8, 10}

And the contents of list2 are

{1, 3, 5, 7, 9, 11}

If you call list1.merge(list2), then list2 will become empty and list1 will contain

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

In that order.

void remove(const T& elem)

Remove all copies of an element

myList.remove(137); // Removes all instances of 137 from the list.

Removes all elements from the list whose value is equal to that of elem. To remove elements by iterator rather than value, use erase.

void remove_if(PredicateFunction pred)

Remove certain elements

myList.remove(isalpha); // Removes elements from a list<char> that are letters

Removes all elements from the list for which the predicate function pred returns true.

void reverse()

Reverse list

myList.reverse(); // myList is now backwards

Reverses the elements of the list. Iterators over the list are unaffected.

void sort()

void sort(CompareFunction comp)

Sort list

myList.sort(); // Sorts the list

Sorts the list according to the < operator. To use a special comparison function instead, pass it as a parameter.

void splice(iterator pos, list<T> &source)

void splice(iterator pos, list<T> &source, iterator elem)

void splice(iterator pos, list<T> &source, iterator start, iterator stop)

Move elements from other list into this one

myList.splice(myList.begin(), myOtherList); // Prepend myOtherList to this list

Moves elements from one list into the calling object. The elements are removed from the other list and inserted into the caller at the index specified by the pos iterator.

The first version of this function empties the first list and inserts all its elements into the caller at the specified position. Note that the list specified as a parameter will become empty.

The second version of the function moves only the element specified by the elem parameter into the caller list. The rest of the other list will be unmodified.

The third version of the function moves all elements from the specified iterator range into the caller list.

void unique()

void unique(BinaryPredicate comp)

Remove adjacent duplicate elements

myList.unique();

For each group of adjacent identical elements in the list, unique removes all but one of them. This function should most likely be called on a sorted list, since otherwise the resulting values of the list are not guaranteed to be unique.

Normally, elements are compared using the == operator. To override this behavior, you can pass a comparison function to unique as a parameter. This function should return true if the two elements are equal and false otherwise.

Other list<T> Member Functions

reverse_iterator begin()

const_reverse_iterator begin() const

Get start reverse iterator

for(list<int>::reverse_iterator itr = myList.rbegin(); /* ... */)

Returns a reverse_iterator to the last element of the list. reverse_iterators are like regular iterators except that they traverse in the opposite direction. Check for the end-of-container condition of reverse_iterators with rend.

reverse_iterator end()

const_reverse_iterator end() const

Get stop reverse iterator.

for(/* ... */ itr != myList.rend(); /* ... */)

Returns a reverse_iterator to the element one element before the start of the array. Like end, the iterator returned by rend does not actually reference a real element of the list and you should take care not to actually dereference it.

size_type max_size() const

Get maximum container size

list<int>::size_type maxElems = myList.max_size()

Returns the maximum number of elements the list can hold, which is usually the number of unique memory addresses divided by the size of the elements stored in the container.

void swap(list<T> &other)

Exchange two lists

myList.swap(myOtherlist); // Exchanges the two lists

Exchanges the contents of this list and another list.

void assign(size_type numCopies, const T& elem)

void assign(InputIterator start, InputIterator end)

Reset list content.

myList.assign(5, 137); // Reset content to five copies of the number 137

myList.assign(otherContainer.begin(), otherContainer.end()); // Copy other container into this list.

Erases any stored content and replaces it with either the specified number of repeats of the specified elements or the elements contained in the range [start, end). In either case, the original list contents are deleted.