STL List

Container, STL

List

Structure of a List
Internal Structure of a List when Appending a Value

包含头文件<list>。
定义：

1
2
3
4
5
namespace std {
	template <	typename T,
			typename Allocator = allocator<T> >
	class list;
}

顺序容器。不提供随机存取。插入删除操作在任何位置都很快，并且不会使迭代器失效。安全。双向迭代器。

List容器的操作

Create, Copy and Destroy

Operation Effect
list c Default constructor; creates an empty list without any elements
list c(c2) Copy constructor; creates a new list as a copy of c2 (all elements are copied)
list c = c2 Copy constructor; creates a new list as a copy of c2 (all elements are copied)
list c(rv) Move constructor; creates a new list, taking the contents of the rvalue rv (since C++11)
list c = rv Move constructor; creates a new list, taking the contents of the rvalue rv (since C++11)
list c(n) Creates a list with n elements created by the default constructor
list c(n, elem) Creates a list initialized with n copies of element elem
list c(beg, end) Creates a list initialized with the elements of the range [beg,end)
list c(initlist) Creates a list initialized with the elements of initializer list initlist (since C++11)
list c = initlist Creates a list initialized with the elements of initializer list initlist (since C++11)
c.~list() Destroys all elements and frees the memory

Nonmodifying Operations

Operation Effect
c.empty() Returns whether the container is empty (equivalent to size()==0 but might be faster)
c.size() Returns the current number of elements
c.max_size() Returns the maximum number of elements possible
c1 == c2 Returns whether c1 is equal to c2 (calls == for the elements)
c1 != c2 Returns whether c1 is not equal to c2 (equivalent to !(c1==c2) )
c1 < c2 Returns whether c1 is less than c2
c1 > c2 Returns whether c1 is greater than c2 (equivalent to c2<c1)
c1 <= c2 Returns whether c1 is less than or equal to c2 (equivalent to !(c2<c1) )
c1 >= c2 Returns whether c1 is greater than or equal to c2 (equivalent to !(c1<c2) )

Assignments

Operation Effect
c = c2 Assigns all elements of c2 to c
c = rv Move assigns all elements of the rvalue rv to c (since C++11)
c = initlist Assigns all elements of the initializer list initlist to c (since C++11)
c.assign(n, elem) Assigns n copies of element elem
c.assign(beg, end) Assigns the elements of the range [beg,end)
c.assign(initlist) Assigns all the elements of the initializer list initlist
c1.swap(c2) Swaps the data of c1 and c2
swap(c1, c2) Swaps the data of c1 and c2

Element Access

Operation Effect
c.front() Returns the first element (no check whether a first element exists)
c.back() Returns the last element (no check whether a last element exists)

Iterator Functions

Bidirectional Iterator.

Operation Effect
c.begin() Returns a bidirectional iterator for the first element
c.end() Returns a bidirectional iterator for the position after the last element
c.cbegin() Returns a constant bidirectional iterator for the first element (since C++11)
c.cend() Returns a constant bidirectional iterator for the position after the last element (since C++11)
c.rbegin() Returns a reverse iterator for the first element of a reverse iteration
c.rend() Returns a reverse iterator for the position after the last element of a reverse iteration
c.crbegin() Returns a constant reverse iterator for the first element of a reverse iteration (since C++11)
c.crend() Returns a constant reverse iterator for the position after the last element of a reverse iteration (since C++11)

Inserting and Removing Elements

Operation Effect
c.push_back(elem) Appends a copy of elem at the end
c.pop_back() Removes the last element (does not return it)
c.push_front(elem) Inserts a copy of elem at the beginning
c.pop_front() Removes the first element (does not return it)
c.insert(pos, elem) Inserts a copy of elem before iterator position pos and returns the position of the new element
c.insert(pos, n, elem) Inserts n copies of elem before iterator position pos and returns the position of the first new element (or pos if there is no new element)
c.insert(pos, beg, end) Inserts a copy of all elements of the range [beg,end) before iterator position pos and returns the position of the first new element (or pos if there is no new element)
c.insert(pos, initlist) Inserts a copy of all elements of the initializer list initlist before iterator position pos and returns the position of the first new element (or pos if there is no new element; since C++11)
c.emplace(pos, args…) Inserts a copy of an element initialized with args before iterator position pos and returns the position of the new element (since C++11)
c.emplace_back(args…) Appends a copy of an element initialized with args at the end (returns nothing; since C++11)
c.emplace_front(args…) Inserts a copy of an element initialized with args at the beginning (returns nothing; since C++11)
c.erase(pos) Removes the element at iterator position pos and returns the position of the next element
c.erase(beg, end) Removes all elements of the range [beg,end) and returns the position of the next element
c.remove(val) Removes all elements with value val
c.remove_if(op) Removes all elements for which op(elem) yields true
c.resize(num) Changes the number of elements to num (if size() grows new elements are created by their default constructor)
c.resize(num, elem) Changes the number of elements to num (if size() grows new elements are copies of elem)
c.clear() Removes all elements (empties the container)

Splice Functions and Functions to Change the Order of Elements

Splice Operations to Change the Order of List Elements

Operation Effect
c.unique() Removes duplicates of consecutive elements with the same value
c.unique(op) Removes duplicates of consecutive elements, for which op() yields true
c.splice(pos, c2) Moves all elements of c2 to c in front of the iterator position pos
c.splice(pos, c2, c2pos) Moves the element at c2pos in c2 in front of pos of list c (c and c2 may be identical)
c.splice(pos, c2, c2beg, c2end) Moves all elements of the range [c2beg,c2end) in c2 in front of pos of list c (c and c2 may be identical)
c.sort() Sorts all elements with operator < c.sort(op) Sorts all elements with op()
c.merge(c2) Assuming that both containers contain the elements sorted, moves all elements of c2 into c so that all elements are merged and still sorted
c.merge(c2, op) Assuming that both containers contain the elements sorted due to the sorting criterion op() , moves all elements of c2 into c so that all elements are merged and still sorted according to op()
c.reverse() Reverses the order of all elements

使用List的示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Examples of Using List
#include <list>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
void printLists (const list<int>& l1, const list<int>& l2)
{
	cout<<"list1:	";
	copy (l1.cbegin(), l1.cend(), ostream_iterator<int>(cout, " "));
	cout<<endl<<"list2:	";
	copy (l2.cbegin(), l2.cend(), ostream_iterator<int>(cout, " "));
	cout<<endl<<endl;
}
int main()
{
	// create two empty lists
	list<int> list1, list2;
	// fill both lists with elements
	for (int i = 0; i < 6; ++i)
	{
		list1.push_back(i);
		list2.push_front(i);
	}
	printLists(list1, list2);
	// insert all elements of list1 before the first element with value 3 of list2
	// - find() returns an iterator to the first element with value 3
	list2.splice(find(list2.begin(), list2.end(),	// destination position
		3),
		list1);										// source list
	printLists(list1, list2);
	// move first element of list2 to the end
	list2.splice(list2.end(),	// destination position
		list2,					// source list
		list2.begin());			// source position
	printLists(list1, list2);
	// sort second list, assign to list1 and remove duplicates
	list2.sort();
	list1 = list2;
	list2.unique();
	printLists(list1, list2);
	// merge both sorted lists into the first list
	list1.merge(list2);
	printLists(list1, list2);
	system("Pause");
}

[1] The C++ Standard Library 2nd Edition