一、基本概念

（一）定義

list：雙向鏈表。list是一種分布式存儲的線性表，每個節(jié)點分為數(shù)據(jù)域和指針域，其中指針域中包含一個指向前驅(qū)節(jié)點的指針和一個指向后續(xù)節(jié)點的指針，基本模型如下：

（二）特性

1、雙向鏈表：每個元素都有一個前驅(qū)和一個后繼，這種結(jié)構(gòu)允許在鏈表的任何位置實現(xiàn)快速的插入和刪除而不影響其他元素。插入和刪除時間復雜度為O（1）。

2、迭代器：list提供了雙向迭代器，支持++和--運算符，能夠前后移動，但不支持隨機訪問，也就是不支持+、-、+=、-=運算。

3、優(yōu)勢和劣勢：相對于deque或者vector，在任意位置插入或者刪除元素效率較高；但隨機訪問效率較低。使用場景多為需要頻繁插入或者刪除元素時。

二、構(gòu)造函數(shù)

（1）list<T>::list();? ? ? ? ? ? ? ? ? ? ? ? 默認構(gòu)造函數(shù)

（2）list<T>::list(size_t size);? ? ? ?構(gòu)造包含size個元素的鏈表，默認值為0；

（3）list<T>::list(size_t size,T value);? ? ? ? 申請size大小鏈表，初始化為value；

（4）list<T>::list(initializer_list<int> _list);? ?初始化列表構(gòu)造；

（5）list<T>::list(list<int>& other);? ? ? ? ? ? ? ?拷貝構(gòu)造函數(shù)；?

（6）list<T::list(iterator begin,iterator end);?指定范圍構(gòu)造；

（7）list<T>::list(list<int>&& other);? ? ? ? ? ? ?移動構(gòu)造；（c++11）

三、成員函數(shù)

（一）迭代器相關函數(shù)

begin()和end();? ? ? ? ? ? ? ? 返回指向首節(jié)點迭代器和指向尾節(jié)點后面一個位置迭代器；

cbegin()和cend();? ? ? ? ? ? ?begin()和end()的常量迭代器

rbegin()和rend();? ? ? ? ? ? ? begin()和end()的反向迭代器

crbegin()和crend();? ? ? ? ? ?begin()和end()的反向常量迭代器

（二）大小相關函數(shù)

size_t list<T>::size();? ? ? ? ? ? ? ? ? ? ? ? 返回鏈表當前元素數(shù)量

size_t list<T>::max_size();? ? ? ? ? ? ? ?返回鏈表最大容納元素數(shù)量

bool ??list<T>::empty();? ? ? ? ? ? ? ? ? ? ? ?判斷鏈表是否為空

（三）訪問函數(shù)

const T& list<T>::front();? ? ? ? ? ? ? ? ????????????????返回第一個元素常量引用；

const T& list<T>::back();? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?返回最后一個元素常量引用；

（四）修改函數(shù)

void list<T>::push_back(T&value);? ? ? ? ? ? ? ? 尾插

void?list<T>::push_front(T&value);? ? ? ? ? ? ? ? 頭插

void?list<T>::pop_back();? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?尾刪

void list<T>::pop_front();? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?頭刪

void list<T>::remove(T&value);? ? ? ? ? ? ? ? ? ? ?刪除指定元素

void list<T>::unique();? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?刪除相鄰且重復的后續(xù)元素

void list<T>::insert(iterator pos,T&value);? ? ?指定位置插入元素，存在插入多個元素、插入?yún)^(qū)間、插入初始化列表等多個重載

void list<T>::splice(iterator pos,list<T>&other); 指定位置復制插入或者移動插入other鏈表（指定元素或指定區(qū)間的元素）

void list<T>::erase(iterator pos);? ? ? ? ? ? ? ? ? ?刪除迭代器指定位置的元素，或者區(qū)間

（五）查找函數(shù)

list<T>::itrator find(list<T>::iterator first,list<T>::iterator last,const T& value);? ? ? ? ? 查找容器指定區(qū)間內(nèi)的value值第一次出現(xiàn)的位置

int count(list<T>::iterator first,list<T>::iterator last,const T&value);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?查找容器指定區(qū)間內(nèi)value的個數(shù)

lower_bound(value);? ? ? ? 對于有序容器返回從左邊找到的最合適的插入位置的迭代器

upper_bound(vlaue);? ? ? ?對于有序容器返回從右邊找到的最合適的插入位置的迭代器

equal_range(value);? ? ? ? 返回有序序列中第一個value值和最后一個value值出現(xiàn)位置的區(qū)間，返回值為pair類型，叫做對組。原型為pair<typename T,typename K>,代表包含兩個數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)。first代表第一個類型，second代表第二個類型。

注意：這些函數(shù)不是容器的成員函數(shù)

（六）其他函數(shù)

list<T>::swap(list<T>&other);? ? ?交換兩個鏈表的內(nèi)容

list<T>::revers();? ? ? ? ? ? ? ? ? ? ? ? ?翻轉(zhuǎn)鏈表

list<T>::sort();? ? ? ? ? ? ? ? ? ? ? ? ? ? ?排序函數(shù)，默認遞增；當鏈表內(nèi)元素是自定義類型或者需要遞減排序時，需要傳入比較函數(shù)作為參數(shù)。

list<T>::clear();? ? ? ? ? ? ? ? ? ? ? ? ? ?清空鏈表

list<T>::resize(size_t newsize);? 改變鏈表大小，大于原鏈表大小時，添加初始化元素；小于原鏈表大小時，從鏈表后面刪除相應元素。

四、排序算法示例

#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
#include<string>
class Person {
public:
	string m_Nmae;
	int m_Age;
	int m_Height;
};
void printPerson(const Person&p) {
	cout << "姓名：" << p.m_Nmae << " 年齡：" << p.m_Age << " 身高：" << p.m_Height << endl;
}
bool MyCompare(Person&p1, Person&p2) {
	if (p1.m_Age == p2.m_Age) {
		return p1.m_Height > p2.m_Height;
	}
	else {
		return p1.m_Age < p2.m_Age;
	}
}
void test() {
	Person p1 = { "張三",20,170 };
	Person p2 = { "李四",30,165 };
	Person p3 = { "王五",40,185 };
	Person p4 = { "趙六",40,180 };
	Person p5 = { "陳七",50,185 };
	list<Person>l;
	l.push_back(p1);
	l.push_back(p3);
	l.push_back(p4);
	l.push_back(p2);
	l.push_front(p5);
	for_each(l.begin(), l.end(), printPerson); cout << endl;
	l.sort(MyCompare);
	for_each(l.begin(), l.end(), printPerson);
}
int main(int argc,char const **argv) {
	test();
	return 0;
}

?例子中對排序多加了一層邏輯，優(yōu)先年齡排序，年齡相同時根據(jù)身高排序。文章來源地址http://www.zghlxwxcb.cn/news/detail-793522.html

到了這里，關于C++——STL標準模板庫——容器詳解——list的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！