??前言

今天把 list容器的基本操作、常用接口做一個系統(tǒng)的整理，結(jié)合具體案例熟悉自定義內(nèi)部排序方法的使用。list與vector 是STL中最常用的兩個容器，如果對vector 容器不熟悉的朋友可以在系列專欄里翻閱復(fù)習(xí)或者學(xué)習(xí)。

1、list 容器本質(zhì)與特點(diǎn)

本質(zhì)：

list 容器可以看做一個雙向循環(huán)鏈表，用于存儲的每個結(jié)點(diǎn)包含數(shù)據(jù)域和指針域

示意圖：

名詞解釋：

• begin和end都是迭代器，可以看成指針來操作
  • begin 對應(yīng)的是容器首個元素，而end 對應(yīng)容器最后一個元素的下一個位置
• prev和next代表前驅(qū)指針和后繼指針，并不是 list容器的接口
  • 指針域用來存儲下一個結(jié)點(diǎn)的地址
• front和back分別是第一個和最后一個結(jié)點(diǎn)的數(shù)據(jù)域
• push_back、push_front、pop_back、pop_front代表尾插、頭插、尾刪、頭刪

通過前驅(qū)后繼指針可以將每個結(jié)點(diǎn)連接起來，頭結(jié)點(diǎn)的前驅(qū)與尾結(jié)點(diǎn)后繼指針都指向null
由于鏈表的存儲方式并不是連續(xù)的內(nèi)存空間，因此鏈表list中的迭代器只支持前移和后移，屬于雙向迭代器

list 特點(diǎn)：

• 優(yōu)點(diǎn)：可以對任意位置快速插入刪除，動態(tài)分配存儲，不會造成內(nèi)存浪費(fèi)和溢出
• 缺點(diǎn)：遍歷速度比數(shù)組慢，占用空間比數(shù)組大

list 有一個重要的性質(zhì)，插入和刪除操作都不會造成原有 list迭代器的失效

2、list 基本操作與常用接口

包含 list容器的構(gòu)造、賦值交換、插入刪除、數(shù)據(jù)存取、空間大小、反轉(zhuǎn)、排序。

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

• 用于創(chuàng)建list容器

函數(shù)原型：

• list<T> lst;
  • 采用模板類實(shí)現(xiàn),對象的默認(rèn)構(gòu)造形式
• list(beg,end);
  • 構(gòu)造函數(shù)將[beg, end)區(qū)間中的元素拷貝給本身。
• list(n,elem);
  • 構(gòu)造函數(shù)將n個elem拷貝給本身。
• list(const list &lst);
  • 拷貝構(gòu)造函數(shù)

示例：

#include<iostream>
#include <list>
using namespace std;

void printList(const list<int>& L) {

	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

void test()
{
	//默認(rèn)構(gòu)造
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	
	printList(L1);
    //區(qū)間構(gòu)造
	list<int>L2(L1.begin(),L1.end());
	printList(L2);
	//拷貝構(gòu)造
	list<int>L3(L2);
	printList(L3);
	//相同值構(gòu)造
	list<int>L4(10, 1000);
	printList(L4);
}

2.2、list 賦值和交換

• 用于給list容器進(jìn)行賦值，以及交換list容器

函數(shù)原型：

• assign(beg, end);
  • 將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身
• assign(n, elem);
  • 將n個elem拷貝賦值給本身
• list& operator=(const list &lst);
  • 重載等號操作符
• swap(lst);
  • 將lst與本身的元素互換

示例：

//賦值和交換
void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	//賦值
	list<int>L2;
	L2 = L1;

	list<int>L3;
	L3.assign(L2.begin(), L2.end());

	list<int>L4;
	L4.assign(10, 100);
}

//交換
void test02()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);

	list<int>L2;
	L2.assign(10, 100);

	cout << "交換前： " << endl;
	printList(L1);
	printList(L2);

	L1.swap(L2);
	cout << "交換后： " << endl;
	printList(L1);
	printList(L2);
}

2.3、list 大小操作

• 用于對list容器的大小進(jìn)行操作

函數(shù)原型：

• size();
  • 返回容器中元素的個數(shù)
• empty();
  • 判斷容器是否為空
• resize(num);
  • 重新指定容器的長度為num，若容器變長，則以默認(rèn)值填充新位置。
  • 如果容器變短，則末尾超出容器長度的元素被刪除。
• resize(num, elem);
  • 與resize(num)的區(qū)別是默認(rèn)值變?yōu)?code>elem

示例：

void testr()
{
	list<int>L6;
	L6.push_back(10);
	L6.push_back(30);
	L6.push_back(40);

	//判斷容器是否為空
	if (L6.empty())
	{
		cout << "list 為空" << endl;
	}
	else {
		cout << "lsit 不為空，元素個數(shù)為：" << L6.size() << endl;
	}
	//重新指定大小
	L6.resize(6, 100);
	printInfo(L6);

	L6.resize(3);
	printInfo(L6);
}

2.4、 list 插入和刪除

• 用于對 list容器進(jìn)行數(shù)據(jù)的插入和刪除

函數(shù)原型：

• push_back(elem);
  • 在容器尾部加入一個元素
• pop_back();
  • 刪除容器中最后一個元素
• push_front(elem);
  • 在容器開頭插入一個元素
• pop_front();
  • 從容器開頭移除第一個元素
• insert(pos,elem);
  • 在pos位置插elem元素的拷貝，返回新數(shù)據(jù)的位置。
• insert(pos,n,elem);
  • 在pos位置插入n個elem數(shù)據(jù)，無返回值。
• insert(pos,beg,end);
  • 在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無返回值。
• clear();
  • 移除容器的所有數(shù)據(jù)
• erase(beg,end);
  • 刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。
• erase(pos);
  • 刪除pos位置的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。
• remove(elem);
  • 刪除容器中所有與elem值匹配的元素

示例：

void testt()
{
	list<int>L7;
	//尾插
	L7.push_back(1);
	L7.push_back(2);
	L7.push_back(3);
	//頭插
	L7.push_front(30);
	L7.push_front(20);
	L7.push_front(10);
	printInfo(L7);
	//插入 insert
	list<int>::iterator t = L7.begin();
	L7.insert(++t, 6);
	//刪除 erase
	t = L7.end();//end迭代器指向最后一個有效元素的下一個位置
	L7.erase(--t);
	printInfo(L7);
	//移除
	L7.push_back(10000);
	L7.push_back(10000);
	printInfo(L7);
	L7.remove(10000);
	printInfo(L7);
	//清空
	L7.clear();
	if (L7.empty())
	{
		cout << "list 已經(jīng)清空" << endl;
	}
}

2.5、list 數(shù)據(jù)存取

• 用于對 list容器中數(shù)據(jù)進(jìn)行存取

函數(shù)原型：

• front();
  • 返回第一個元素。
• back();
  • 返回最后一個元素。

示例：

void testy()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(50);
	//訪問首尾元素
	cout << "第一個元素值為：" << L1.front() << endl;
	cout << "最后一個元素值為：" << L1.back() << endl;
	//不支持下標(biāo)訪問，也不支持隨機(jī)訪問，底層是鏈表
	list<int>::iterator it = L1.begin();
	it++;//正確
	//it + 1;//錯誤，不存在與"+"匹配的運(yùn)算符
}

2.6、list 反轉(zhuǎn)和排序

• 將容器中的元素反轉(zhuǎn)，以及將容器中的數(shù)據(jù)進(jìn)行排序

函數(shù)原型：

• reverse();
  • 反轉(zhuǎn)鏈表
• sort();
  • 鏈表排序

反轉(zhuǎn)示例：

void testu()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	cout << "反轉(zhuǎn)前：" << endl;
	printInfo(L1);
	cout << "反轉(zhuǎn)后：" << endl;
	L1.reverse();
	printInfo(L1);
}

排序示例：

//用于降序排序
bool myCompare(int v1, int v2)
{
	//降序：讓第一個數(shù) > 第二個數(shù)
	return v1 > v2;
}
void testi()
{
	list<int>L;
	L.push_back(2);
	L.push_back(1);
	L.push_back(6);
	L.push_back(4);
	L.push_back(5);
	L.push_back(3);
	cout << "排序前：" << endl;
	printInfo(L);
	cout << "升序排序后：" << endl;
	L.sort();
	printInfo(L);
	cout << "降序排序后：" << endl;
	L.sort(myCompare);
	printInfo(L);
}

• 所有不支持隨機(jī)訪問迭代器的容器，不可以使用標(biāo)準(zhǔn)算法
• 這些容器內(nèi)部會提供排序的成員方法

sort是 list容器內(nèi)部的排序方法，默認(rèn)為升序排列，可以通過自己編寫函數(shù)來決定排序的規(guī)則。

3、排序案例

3.1、生肖類

class Person
{
public:
	Person(string name, int age, int height)
	{
		this->name = name;
		this->age = age;
		this->height = height;
	}

	//屬性
	string name;
	int age;
	int height;
};

3.2、排序規(guī)則

//自定義排序規(guī)則 compare
bool compare(Person& p1, Person& p2)
{
	//按照身高降序
	if (p1.height == p2.height)
	{
		//如果身高相同，按照年齡升序排序
		return p1.age < p2.age;
	}
	else {
		return p1.height > p2.height;
	}
	
}

3.3、具體實(shí)現(xiàn)與效果

//打印list容器
void printList(list<Person>&L)
{
	for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
	{
		cout << "姓名：" << it->name << "\t年齡："
			<< it->age << "\t身高：" << it->height << endl;
	}
}
//函數(shù)主體
void test_Person()
{
	list<Person>L;
	//準(zhǔn)備數(shù)據(jù)
	Person p1("辰龍", 29, 188);
	Person p2("寅虎", 27, 186);
	Person p3("子鼠", 25, 168);
	Person p4("丑牛", 26, 189);
	Person p5("卯兔", 28, 168);
	Person p6("亥豬", 36, 186);
	//尾插
	L.push_back(p1);
	L.push_back(p2);
	L.push_back(p3);
	L.push_back(p4);
	L.push_back(p5);
	L.push_back(p6);

	cout << "排序前：" << endl;
	printList(L);
	cout << "---------------------------------------" << endl;
	cout << "排序后：" << endl;
	L.sort(compare);
	printList(L);
}

list容器在泛型編程里還是比較重要的，希望我的分享可以給大家?guī)韼椭?，最后要個贊不過分吧文章來源地址http://www.zghlxwxcb.cn/news/detail-791436.html

到了這里，關(guān)于＜C++＞ list容器本質(zhì)|常用接口|自定義排序規(guī)則的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！