【C++】list常用接口

目录

1.引言

2.list介绍 

3.list相关成员函数 

3.1相关成员类型： 

3.2成员函数 

3.21构造函数： 

4.迭代器使用 

4.1迭代器简介

 4.2正反向迭代器（begin，end/rbegin,rend）

5.元素访问 

6.list容量 

7.元素修改 

7.11头插，尾插(push_front,push_back ), 任意位置插入(inser）

7.12头删，尾删 ,erase 

7.2clear清理 

8.list的操作函数 

---

1.引言

string容器时关于字符串的，这个和vector,list没啥大的交集，那为啥有了vector还有list?

两者的区别：

• vector底层实现是数组；list是双向链表。
• vector支持随机访问，list不支持。
• vector是顺序内存，list不是。
• vector在中间节点进行插入删除会导致内存拷贝，list不会。
• vector一次性分配好内存，不够时才进行2倍扩容；list每次插入新节点都会进行内存申请。

6）vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。

两者相关应用：

• vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。
• list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。

2.list介绍 

1. list是序列容器，允许在序列中的任何位置执行固定O(1)时间复杂度的插入和删除操作，并在两个方向进行迭代。
2. list容器使用双链表实现；双链表将每个元素存储在不同的位置，每个节点通过next，prev指针链接成顺序表。
3. list与其他标准序列容器（array，vector和deque）相比，list通常可以在容器内的任何位置插入、提取和移动元素。
4. list与其他标准序列容器（array，vector和deque）相比，list和forward_list（单链表实现）的主要缺点是他们不能通过位置直接访问元素；例如，要访问列表中的第五个元素，必须从已知位置（开始或结束）迭代到该位置，需要哦线性时间开销。
5. 存储密度低，list要使用一些额外的内容空间（next，prev）来保持与每个元素相关联（前后续的线性）的链接信息，从而导致存储小元素类型（如char，short，int等）的列表的存储密度低。

讲了这么多就说了：list是双向带头循环列表，内存空间不连续、不支持随机访问。

3.list相关成员函数 

3.1相关成员类型： 

成员类型 定义 笔记 value_type 第一个模板参数 （T) allocator_type 第二个模板参数（分配）) 默认值为：分配器 参考 allocator_type：：参考 对于默认分配器：value_type& const_reference allocator_type：const_reference 对于默认分配器：常量 value_type& 指针 allocator_type：:p 对于默认分配器：value_type* const_pointer allocator_type：const_pointer 对于默认分配器：常量value_type* 迭 代 指向value_type的双向迭代器 可转换为const_iterator const_iterator 用于构造value_type的双向迭代器 reverse_iterator reverse_iterator<迭代器> const_reverse_iterator reverse_iterator difference_type 有符号整数类型，与以下类型相同：iterator_traits<迭代器>：:d验证类型 通常与ptrdiff_t相同 size_type 一种无符号整数类型，可以表示difference_type的任何非负值 通常与size_t相同

3.2成员函数 

3.21构造函数： 

空容器构造函数（默认构造函数）构造一个没有元素的空容器。

explicit list (const allocator_type& alloc = allocator_type());

填充构造函数：构造一个包含 n 个元素的容器。每个元素都是 val 的副本。

explicit list (size_type n, const value_type& val = value_type(),
                const allocator_type& alloc = allocator_type());

 范围构造函数构造一个包含与范围 [first，last） 一样多的元素的容器，每个元素都以相同的顺序从该区域中的相应元素构造。

list (InputIterator first, InputIterator last,
         const allocator_type& alloc = allocator_type());

复制构造函数以相同的顺序构造一个容器，其中包含 x 中每个元素的副本。

list (const list& x);

1.list（） 定义list类型变量：

list<int> l1;

2.list l2（n,val）:填充构造函数：

list<int> l2(7,3); //构造7个初始值为3的数

3.（begin,end）范围构造函数：

	list<int> l1;//构造空链表
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
 
 //迭代器构造
	list<int> l3(l1.begin(), l1.end());//构造l3,以l1起始区间到终止区间的内容为元素
	
//使用tmp的元素作为迭代区间进行构造
	int tmp[] = { 4, 5, 6, 7, 8, 9 };
	list<int> l4(tmp, tmp+sizeof(tmp)/sizeof(tmp[0]));

4.list (const list& x) 复制构造函数：

list<int> l2(7,3); //构造7个初始值为3的数
list<int> l5(l2); //  //将l2拷贝给l5

4.迭代器使用 

4.1迭代器简介

迭代器跟vector的使用简直一毛一样。

 
iterator begin();//正向迭代器，对迭代器++，迭代器向后移动
const_iterator begin() const;//正向const迭代器，对迭代器++，迭代器向前移动
 
reverse_iterator rbegin();//反向迭代器，对迭代器++，迭代器向后移动
const_reverse_iterator rbegin() const;//const反向const迭代器，对迭代器++，迭代器向前移动
 

 4.2正反向迭代器（begin，end/rbegin,rend）

list<int>::iterator it1 = l1.begin();
	while (it1 != l1.end())
	{
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;
 
	//链表不能使用[]进行元素访问，使用迭代器访问，打印l2
	list<int>::iterator it2 = l2.begin();
	while (it2 != l2.end())
	{
		cout << *it2 << " ";
		it2++;
	}
	cout << endl;
 

有一个细节大家一定要注意，因为list的空间是不连续的，所以我们一定不能像vector那样用下标+[]来访问。要进行访问就要用到迭代器和范围for（也是用迭代器实现的）。 

int main()
{
		list<int> lt;
		for (int i = 1; i <= 8; i+=2)
		{
			lt.push_back(i);//1  3 5 7
		}
		list<int>::reverse_iterator itc = lt.rbegin();
		//或者用auto自动识别类型：auto itc = lt.rbegin();
		while (itc != lt.rend())
		{
			cout << *itc << " "; //7 5 3 1
			itc++;
		}
 
}

list的访问和vector大差不差，都要通过循环进行打印。

在这里我想强调一点：

它的迭代器前面的类型时不时太多太冗杂，我们直接用auto可以直接省去了。因为auto会根据后面的条件来自动识别变量的类型。

范围for

int main()
{
	
		list<int> lt;
		for (int i = 1; i <= 8; i+=2)
		{
			lt.push_back(i);//1  3 5 7
		}
 
		for (auto e : lt)
		{
			cout << e << " ";
		}
｝

前已经讲过范围for的用饭和作用了，这里就不赘述了。

5.元素访问 

元素访问	功能
reference front();	返回到容器首元素的引用。
const_reference front() const;	返回到容器首元素的引用
reference back();	返回到容器中最后一个元素的引用。
const_reference back() const;	返回到容器中最后一个元素

 归根到底就两种，front(),返回首元素,back()返回最后一个元素。

int main()
{
	
		list<int> lt;
		for (int i = 1; i <= 8; i+=2)
		{
			lt.push_back(i);//1  3 5 7
		}
 
		cout << lt.front() << endl;   // 1
		cout << lt.back() << endl;    // 7
}

6.list容量 

容量	功能
bool empty() const;	检查容器是否无元素，即是否 begin() == end() 。
size_type size() const;    返回容器中的元素数，	即 std::distance(begin(), end()) 。
size_type max_size() const;	返回根据系统或库实现限制的容器可保有的元素最大数量，即对于最大容器的 std::distance(begin(), end()) 。

xdm，这个empty和size已经是老生常谈了，有点新奇的是这个max_size()。

nt main()
{
	
		list<int> lt;
		for (int i = 1; i <= 8; i+=2)
		{
			lt.push_back(i);//1 3 5 7
		}
 
		cout << lt.empty() << endl;   // 0
		cout << lt.size() << endl;    //4(1 3 5 7）
}

max_size()还有点意思但意思不多。就是返回list容器的最大容量值。

int main()
{
	
		list<int> lt;
		for (int i = 1; i <= 8; i+=2)
		{
			lt.push_back(i);//1 3 5 7
		}
 
		cout <<"empty: "<< lt.empty() << endl;   // 0
		cout <<"size: " <<lt.size() << endl;    //4(1 3 5 7）
		cout << "max_size: " << lt.max_size() << endl; // 357913941
｝

7.元素修改 

修改器	功能
void clear();	从容器擦除所有元素。此调用后 size() 返回零。
iterator insert( iterator pos, const T& value );	在 pos 前插入 value 。
void insert( iterator pos, size_type count, const T& value );	在 pos 前插入 value 的 count 个副本。
template< class InputIt >
void insert( iterator pos, InputIt first, InputIt last);	在 pos 前插入来自范围 [first, last) 的元素
iterator insert( const_iterator pos, std::initializer_list ilist );	在 pos 前插入来自 initializer_list ilist 的元素。
iterator erase( iterator pos );	移除位于 pos 的元素。
iterator erase( iterator first, iterator last );	移除范围 [first; last) 中的元素。
void pop_back();	移除容器的末元素。
void pop_front();	移除容器首元素。
void push_front( const T& value );	前附给定元素 value 到容器起始。
void push_back( const T& value );	后附给定元素 value 到容器尾。
void resize( size_type count );	重设容器大小以容纳 count 个元素。
void resize( size_type count, T value = T() );	count - 容器的大小，value - 用以初始化新元素的值
void swap( list& other );	将内容与 other 的交换。

7.11头插，尾插(push_front,push_back ), 任意位置插入(inser）

7.t相较于vector，list多了头插和尾插，任意位置插入。 一般vector不支持头插是因为顺序表是从所分配内存的起始地址开始存储的,第0个元素前的空间一般是未分配的,所以无法进行头插。

void test2()
{
	list<int> lt;
	for (int i = 1; i <= 8; i += 2)
	{
		lt.push_back(i);//1 3 5 7
	}
	
	for (auto e : lt)
	{
		cout << e << " ";    //1 3 5 7
	}
	cout << endl; 
	lt.push_front(0);
	lt.push_front(-1);
	cout << lt.front() << endl;  // 0
	for (auto e : lt)
	{
		cout << e << " ";    // -1 0 1 3 5 7
	}
	cout << endl;   
//尾插
	lt.push_back(8);
	for (auto e : lt)
	{
		cout << e << " ";    // -1 0 1 3 5 7 8
	}
}

任意位置插入：insert

• 在指定位置插入一个值为val的元素
• 在指定位置插入n个值为val的元素
• 在指定位置插入一段左闭右开的迭代器区间.

void test3()
{
	
		list<int> lt;
		for (int i = 1; i <= 4; i++)
		{
			lt.push_back(i);//1 2 3 4
		}
		list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
		//1、在2的位置插入值7
		lt.insert(pos, 7);
		for (auto e : lt)
			cout << e << " ";//1 7 2 3 4
		cout << endl;
 
		//2、在3的位置插入4个5
		pos = find(lt.begin(), lt.end(), 3);
		lt.insert(pos, 4, 5);
		for (auto e : lt)
			cout << e << " ";//1 7 2 5 5 5 5 3 4
		cout << endl;
 
		//3、在数字3的位置前插入迭代器区间
		pos = find(lt.begin(), lt.end(), 3);
		list<int> lt2(3, 0);
		lt.insert(pos, lt2.begin(), lt2.end());
		for (auto e : lt)
			cout << e << " ";//	1 7 2 5 5 5 5 0 0 0 3 4
	
}

7.12头删，尾删 ,erase 

头删尾删就不过多介绍了

void test4()
{
	list<int> lt;
	for (int i = 1; i <= 8; i += 2)
	{
		lt.push_back(i);//1 3 5 7
	}
	lt.pop_front();
	cout << lt.front() << endl;  // 3
	for (auto e : lt)
	{
		cout << e << " ";    //  3 5 7
	}
	cout << endl;
	//尾删
	lt.pop_back();
	for (auto e : lt)
	{
		cout << e << " ";    // 3  5
	｝
}

erase:

• 删除在指定迭代器位置的元素。
• 删除指定迭代器区间的元素。

void test5()
{
	list<int> lt;
	for (int i = 1; i <= 8; i++)
	{
		lt.push_back(i);//1 2 3 4 5 6 7 8
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
	//1、删除数字是3位置的元素
	lt.erase(pos);
	for (auto e : lt)
		cout << e << " ";//1 2 4 5 6 7
	cout << endl;
	//2、删除值为5后的所有元素
	pos = find(lt.begin(), lt.end(), 5);
	lt.erase(pos, lt.end());
	for (auto e : lt)
		cout << e << " ";//1 2 4
	cout << endl;
}

有一点一定要注意：

list<int>::iterator pos = find(lt.begin(), lt.end(), 3);

这个代码中，找的3是数字3，而不是链表中第三个数据，如果链表中没有3，就删不了。

 这一点一定要注意，也包括上面的insert也有这个，找到某个数字，才能在这个数字前插入不是这个位置。

7.2clear清理 

void test()
{
	list<int> lt(4，3);
	for (auto e : lt)
		cout << e << " ";//3 3 3 3
	cout << endl;
	lt.clear();
	for (auto e : lt)
		cout << e << " ";//空
}

8.list的操作函数 

操作函数	功能
void merge( list& other );	归并二个已排序链表为一个。链表应以升序排序。
void reverse();	逆转容器中的元素顺序。
void unique();	从容器移除所有相继的重复元素。只留下相等元素组中的第一个元素。
void sort();	以升序排序元素。保持相等元素的顺序。用 operator< 比较元素

void merge(  ); 和void reverse();

void test6()
{
	list<int> lt1;
	for (int i = 4; i <= 8; i++)
	{
	   lt1.push_back(i);//4 5 6 7 8
	}
	list<int> lt2(5, 3);
	lt1.merge(lt2);
	for (auto e : lt1) 
		cout << e << " ";//3 3 3 3 3 4 5 6 7 8
	cout << endl;
	lt1.reverse();
	for (auto e : lt1)
		cout << e << " ";//8 7 6 5 4 3 3 3 3 3
	cout << endl;
}

void unique()  是删除链表中的重复数据的。

void test7()
{
	list<int> lt1;
	for (int i = 4; i <= 8; i++)
	{
	   lt1.push_back(i);//4 5 6 7 8
	}
	list<int> lt2(5, 3);
	lt1.merge(lt2);
	for (auto e : lt1)
		cout << e << " ";//3 3 3 3 3 4 5 6 7
	cout << endl;
	lt1.unique();
	for (auto e : lt1)
		cout << e << " ";// 3 4 5 6 7
	cout << endl;
}

void sort()  升序排序

void test7()
{
	list<int> lt;
	lt.push_back(13);
	lt.push_back(7);
	lt.push_front(11);
	lt.push_back(4);
	lt.push_back(9);
	lt.push_back(10);
	for (auto e : lt)
		cout << e << " ";  //11 13 7 4 9 10
	cout << endl; 
	lt.sort();
	for (auto e : lt)
		cout << e << " ";//4 7 9 10 11 13 
	cout << endl;
}

注意：STL库中也有sort函数，但是list定义的对象不用std::sort函数，而是用自己的库函数。

原因是std::sort（）需要的时随机访问的迭代器，而list容器相当于双向循环链表，不允许有随机访问(下标+[])的操作。