cpp►STL容器->序列容器->list

目录

            • 描述
            • 容器属性(Container properties)
            • 模板参数(Template parameters)
            • 修改器(Modifiers)
            • 操作(Operations)

描述

std::list
template <class T, class Alloc = allocator<T>> class list;
list是序列容器,允许在序列中的任何位置执行固定时间的插入和删除操作,并在两个方向上进行迭代。

list容器实现为双链接列表;双链接列表可以将其包含的每个元素存储在不同且不相关的存储位置。在内部,顺序是通过与每个元素的关联来保持的,每个元素都有链接指向它前面的元素,也有链接指向它后面的元素。

它们非常类似于forward_list:主要区别在于forward_list对象是单链表,因此它们只能向前迭代,以换取更小和更高效。

与其他基本标准序列容器(array、vector和deque)相比,list容器通常在迭代器的任何位置插入、提取和移动元素方面表现更好,因此在大量使用这些元素的算法(如排序算法)中也表现更好。

与其他序列容器相比,forward_list的主要缺点是它们无法通过位置直接访问元素;例如,要访问前向列表中的第六个元素,必须从开始到该位置进行迭代,这需要在这些元素之间的距离上花费线性时间。它们还消耗一些额外的内存来保持与每个元素相关联的链接信息(这可能是小size元素的大列表的一个重要因素)。

容器属性(Container properties)
  • Sequence
    序列容器中的元素按严格的线性序列排序。单个元素通过其在此序列中的位置进行访问。
  • Doubly-linked list
    每个元素都保存有关如何定位下一个和上一个元素的信息,允许在特定元素之前或之后进行固定时间的插入和擦除操作(即使是整个范围),但不允许直接随机访问。
  • Allocator-aware
    容器使用分配器对象动态处理其存储需求。
模板参数(Template parameters)
  • T
    元素的类型。别名是成员类型list::value_type。
  • Alloc
    用于定义存储分配模型的分配器对象的类型。默认情况下,使用分配器类模板,它定义了最简单的内存分配模型,并且与值无关。别名为成员类型list::allocator_type。

成员类型(Member types)------略
成员函数(Member functions)------略
迭代器(Iterators)------略
容量(Capacity)------略
访问元素(Element access)------略

修改器(Modifiers)
  • emplace_front
template <class... Args>
void emplace_front(Args&&... args)

构造及在开始位置插入元素。

// list::emplace_front
#include <iostream>
#include <list>
int main() {
	std::list<std::pair<int, char>> mylist;
	mylist.emplace_front(10, 'a');
	mylist.emplace_front(20, 'b');
	mylist.emplace_front(30, 'c');
	std::cout << "mylist contains:";
	for (auto& x : mylist)
		std::cout << " (" << x.first << "," << x.second << ")";
	return 0;
}
mylist contains: (30,c) (20,b) (10,a)
  • push_front
// list::push_front
#include <iostream>
#include <list>
int main() {
    std::list<int> mylist(2, 100);// two ints with a value of 100
    mylist.push_front(200);
    mylist.push_front(300);
    std::cout << "mylist contains:";
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << ' ' << *it;
    return 0;
}
300 200 100 100
  • pop_front
// list::pop_front
#include <iostream>
#include <list>
int main() {
	std::list<int> mylist;
	mylist.push_back(100);
	mylist.push_back(200);
	mylist.push_back(300);
	std::cout << "Popping out the elements in mylist:";
	while (!mylist.empty()) {
		std::cout << ' ' << mylist.front();
		mylist.pop_front();
	}
	std::cout << "\nFinal size of mylist is " << mylist.size();
	return 0;
}
Popping out the elements in mylist: 100 200 300
Final size of mylist is 0
操作(Operations)
  • splice /splaɪs/ 移接=移除+接合
entire list (1)	 
	void splice (iterator position, list& x);
single element (2)
	void splice (iterator position, list& x, iterator i);
element range (3)	
	void splice (iterator position, list& x, iterator first, iterator last);

entire list (1):将(list& x)的所有元素移接到容器中。
single element (2):只将(iterator i)所指的元素从(list& x)移接到容器中。
element range (3):将范围在[first,last]的(list& x)移接到容器中。

// splicing lists
#include <iostream>
#include <list>
int main() {
	std::list<int> mylist1, mylist2;
	std::list<int>::iterator it;
	for (int i = 1; i <= 4; ++i)
		mylist1.push_back(i);// mylist1: 1 2 3 4
	for (int i = 1; i <= 3; ++i)
		mylist2.push_back(i * 10);// mylist2: 10 20 30

	it = mylist1.begin();
	++it;// points to 2

	/* ➊entire list (1) */
	/* 将整个mylist2移接到mylist1的“it”所指位置 */
	/* mylist2全部移接到mylist1后,mylist2就没有元素了 */
	mylist1.splice(it, mylist2);
	// mylist1: 1 10 20 30 2 3 4
	// mylist2 (empty)
	// "it" still points to 2 (the 5th element)
	
	/* ➋single element (2) */
	/* 将“it”所指元素从mylist1移接到mylist2的begining位置 */
	/* 移接后,mylist1失去一个元素,mylist2增加一个元素 */
	mylist2.splice(mylist2.begin(), mylist1, it);
	// mylist1: 1 10 20 30 3 4
	// mylist2: 2
	// "it" is now invalid.
	
	it = mylist1.begin();
	std::advance(it, 3);// "it" points now to 30

	/* ➌element range (3) */
	/* 将区间[it, mylist1.end()]的mylist1移接到自己的begining位置 */
	/* mylist1的{30,3,4}移接到它的首位置,变为:30,3,4,1,10,20 */
	mylist1.splice(mylist1.begin(), mylist1, it, mylist1.end());
	// mylist1: 30 3 4 1 10 20

	std::cout << "mylist1 contains:";
	for (it = mylist1.begin(); it != mylist1.end(); ++it)
		std::cout << ' ' << *it;
	std::cout << '\n';

	std::cout << "mylist2 contains:";
	for (it = mylist2.begin(); it != mylist2.end(); ++it)
		std::cout << ' ' << *it;
	return 0;
}
mylist1 contains: 30 3 4 1 10 20
mylist2 contains: 2
  • remove
    void remove(const value_type& val);
// remove from list
#include <iostream>
#include <list>
int main() {
	int myints[] = { 17,89,7,14 };
	std::list<int> mylist(myints, myints + 4);
	mylist.remove(89);
	std::cout << "mylist contains:";
	for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
		std::cout << ' ' << *it;
	return 0;
}
mylist contains: 17 7 14
  • remove_if
    template <class Predicate> void remove_if(Predicate pred);
    参数pred:一元谓词,取与forward_list对象中包含的值类型相同的值,对于要从容器中删除的值返回true,对于剩余的值返回false。它可以是函数指针或函数对象。
// list::remove_if
#include <iostream>
#include <list>
// a 一元谓语 implemented as a 【function】:
bool single_digit(const int& value) {
	return (value < 10);
}
// a 一元谓语 implemented as a 【class】:
struct is_odd {
	bool operator() (const int& value) {
		return (value % 2) == 1;
	}
};
int main() {
	int myints[] = { 15,36,7,17,20,39,4,1 };
	std::list<int> mylist(myints, myints + 8);// 15 36 7 17 20 39 4 1

	mylist.remove_if(single_digit);// 15 36 17 20 39

	mylist.remove_if(is_odd());// 36 20

	std::cout << "mylist contains:";
	for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
		std::cout << ' ' << *it;
	return 0;
}
mylist contains: 36 20
  • unique
    void unique();
    template <class BinaryPredicate> void unique<BinaryPredicate binary_pred);
    参数binary_pred:二元谓词,取两个与列表中包含的值类型相同的值,返回true以从容器中删除作为第一个参数传递的元素,否则返回false。这应该是函数指针或函数对象。

注意:该函数将为所有成对的元素(其中it是元素的迭代器,从第二个开始)调用binary_pred(*it, *(it-1)),如果谓词返回true,则从列表中删除it。

// list::unique
#include <iostream>
#include <cmath>
#include <list>
// a 二元谓语 implemented as a 【function】:
bool same_integral_part(double first, double second) {
	return (int(first) == int(second));
}
// a 二元谓语 implemented as a 【class】:
struct is_near {
	bool operator() (double first, double second) {
		return (fabs(first - second) < 5.0);
	}
};

int main() {
	double mydoubles[] = { 12.15, 2.72, 73.0, 12.77, 3.14,
						 12.77, 73.35, 72.25, 15.3, 72.25 };
	std::list<double> mylist(mydoubles, mydoubles + 10);

	mylist.sort();// 2.72, 3.14, 12.15, 12.77, 12.77,
				  // 15.3, 72.25, 72.25, 73.0, 73.35
	mylist.unique();// 2.72, 3.14, 12.15, 12.77
					// 15.3, 72.25, 73.0, 73.35
	mylist.unique(same_integral_part);// 2.72, 3.14, 12.15
									  // 15.3, 72.25, 73.0
	mylist.unique(is_near());// 2.72, 12.15, 72.25
	std::cout << "mylist contains:";
	for (std::list<double>::iterator it = mylist.begin(); it != mylist.end(); ++it)
		std::cout << ' ' << *it;
	return 0;
}
mylist contains: 2.72 12.15 72.25

对于mylist:{2.72, 3.14, 12.15, 15.3, 72.25, 73.0},调用mylist.unique(isnear());时,从第2个元素开始,与前一个元素比较,如果<5,返回true,则删除第2个元素。否则删除前一个元素。(|3.14-2.72|<5)==true,删除3.14。同理,还要删除15.3、73.0,删除完毕。

  • merge
(1) void merge(list& x);
(2) template <class Compare>
    void merge(list& x, Compare comp);

作用:合并有序list。
通过将(list& x)的所有元素在其各自的已排序位置转移到容器中(两个容器都已排序好),将(list& x)合并到列表中。
这将有效地删除(list& x)中的所有元素(该元素变为空),并将它们插入到容器中的有序位置(容器的大小按传输的元素数扩展)。
参数comp:二元谓词,取与列表中包含的值类型相同的两个值,如果第一个参数被认为在它定义的严格弱顺序中先于第二个参数,则返回true,否则返回false。这应该是函数指针或函数对象。

// list::merge
#include <iostream>
#include <list>
// compare only integral part:
bool mycomparison(double first, double second) {
	return (int(first) < int(second));
}
int main() {
	std::list<double> first, second;
	first.push_back(3.1);
	first.push_back(2.2);
	first.push_back(2.9);
	second.push_back(3.7);
	second.push_back(7.1);
	second.push_back(1.4);
	first.sort();// 2.2 2.9 3.1(merge的两个list得是ordered list)
	second.sort();// 1.4 3.7 7.1

	// merge后是ordered list
	first.merge(second);// first:1.4 2.2 2.9 3.1 3.7 7.1
                        // second:empty
	second.push_back(2.1);// second:2.1

	first.merge(second, mycomparison);
	std::cout << "first contains:";
	for (std::list<double>::iterator it = first.begin(); it != first.end(); ++it)
		std::cout << ' ' << *it;
	return 0;
}
first contains: 1.4 2.2 2.9 2.1 3.1 3.7 7.1

second:{2.1}这个元素依次与first:{1.4, 2.2, 2.9, 3.1, 3.7, 7.1}中每个元素比较,mycomparison(2.1, 1.4)==false,…,mycomparison(2.1, 3.1)==true,这时2.1就放在了3.1的前面。

  • sort
(1) void sort();
(2) template <class Compare>
	void sort(Compare comp);
// list::sort
#include <iostream>
#include <list>
#include <string>
#include <cctype>
// comparison, not case sensitive.
bool compare_nocase(const std::string& first, const std::string& second) {
	unsigned int i = 0;
	while ((i < first.length()) && (i < second.length())) {
		if (tolower(first[i]) < tolower(second[i])) 
			return true;
		else if (tolower(first[i]) > tolower(second[i])) 
			return false;
		++i;
	}
	return (first.length() < second.length());
}
int main() {
	std::list<std::string> mylist;
	std::list<std::string>::iterator it;
	mylist.push_back("one");
	mylist.push_back("two");
	mylist.push_back("Three");

	mylist.sort();
	std::cout << "mylist contains:";
	for (it = mylist.begin(); it != mylist.end(); ++it)
		std::cout << ' ' << *it;
	std::cout << '\n';

	mylist.sort(compare_nocase);
	std::cout << "mylist contains:";
	for (it = mylist.begin(); it != mylist.end(); ++it)
		std::cout << ' ' << *it;
	return 0;
}
mylist contains: Three one two
mylist contains: one Three two
  • reverse
    void reverse() noexcept;
// reversing list
#include <iostream>
#include <list>
int main() {
    std::list<int> mylist;
    for (int i = 1; i < 10; ++i) 
        mylist.push_back(i);
    mylist.reverse();
    std::cout << "mylist contains:";
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << ' ' << *it;
    return 0;
}
mylist contains: 9 8 7 6 5 4 3 2 1

观察者(Observers)------略
非成员函数重载(Non-member function overloads)------略

热门文章

暂无图片
编程学习 ·

那些年让我们目瞪口呆的bug

程序员一生与bug奋战&#xff0c;可谓是杀敌无数&#xff0c;见怪不怪了&#xff01;在某知识社交平台中&#xff0c;一个“有哪些让程序员目瞪口呆的bug”的话题引来了6700多万的阅读&#xff0c;可见程序员们对一个话题的敏感度有多高。 1、麻省理工“只能发500英里的邮件” …
暂无图片
编程学习 ·

redis的下载与安装

下载redis wget http://download.redis.io/releases/redis-5.0.0.tar.gz解压redis tar -zxvf redis-5.0.0.tar.gz编译 make安装 make install快链方便进入redis ln -s redis-5.0.0 redis
暂无图片
编程学习 ·

《大话数据结构》第三章学习笔记--线性表(一)

线性表的定义 线性表&#xff1a;零个或多个数据元素的有限序列。 线性表元素的个数n定义为线性表的长度。n为0时&#xff0c;为空表。 在比较复杂的线性表中&#xff0c;一个数据元素可以由若干个数据项组成。 线性表的存储结构 顺序存储结构 可以用C语言中的一维数组来…
暂无图片
编程学习 ·

对象的扩展

文章目录对象的扩展属性的简洁表示法属性名表达式方法的name属性属性的可枚举性和遍历可枚举性属性的遍历super关键字对象的扩展运算符解构赋值扩展运算符AggregateError错误对象对象的扩展 属性的简洁表示法 const foo bar; const baz {foo}; baz // {foo: "bar"…
暂无图片
编程学习 ·

让程序员最头疼的5种编程语言

世界上的编程语言&#xff0c;按照其应用领域&#xff0c;可以粗略地分成三类。 有的语言是多面手&#xff0c;在很多不同的领域都能派上用场。大家学过的编程语言很多都属于这一类&#xff0c;比如说 C&#xff0c;Java&#xff0c; Python。 有的语言专注于某一特定的领域&…
暂无图片
编程学习 ·

写论文注意事项

参考链接 给研究生修改了一篇论文后&#xff0c;该985博导几近崩溃…… 重点分析 摘要与结论几乎重合 这一条是我见过研究生论文中最常出现的事情&#xff0c;很多情况下&#xff0c;他们论文中摘要部分与结论部分重复率超过70%。对于摘要而言&#xff0c;首先要用一小句话引…
暂无图片
编程学习 ·

安卓 串口开发

上图&#xff1a; 上码&#xff1a; 在APP grable添加 // 串口 需要配合在项目build.gradle中的repositories添加 maven {url "https://jitpack.io" }implementation com.github.licheedev.Android-SerialPort-API:serialport:1.0.1implementation com.jakewhart…
暂无图片
编程学习 ·

2021-2027年中国铪市场调研与发展趋势分析报告

2021-2027年中国铪市场调研与发展趋势分析报告 本报告研究中国市场铪的生产、消费及进出口情况&#xff0c;重点关注在中国市场扮演重要角色的全球及本土铪生产商&#xff0c;呈现这些厂商在中国市场的铪销量、收入、价格、毛利率、市场份额等关键指标。此外&#xff0c;针对…
暂无图片
编程学习 ·

Aggressive cows题目翻译

描述&#xff1a; Farmer John has built a new long barn, with N (2 < N < 100,000) stalls.&#xff08;John农民已经新建了一个长畜棚带有N&#xff08;2<N<100000&#xff09;个牛棚&#xff09; The stalls are located along a straight line at positions…
暂无图片
编程学习 ·

剖析组建PMO的6个大坑︱PMO深度实践

随着事业环境因素的不断纷繁演进&#xff0c;项目时代正在悄悄来临。设立项目经理转岗、要求PMP等项目管理证书已是基操&#xff0c;越来越多的组织开始组建PMO团队&#xff0c;大有曾经公司纷纷建造中台的气质&#xff08;当然两者的本质并不相同&#xff0c;只是说明这个趋势…
暂无图片
编程学习 ·

Flowable入门系列文章118 - 进程实例 07

1、获取流程实例的变量 GET运行时/进程实例/ {processInstanceId} /变量/ {变量名} 表1.获取流程实例的变量 - URL参数 参数需要值描述processInstanceId是串将流程实例的id添加到变量中。变量名是串要获取的变量的名称。 表2.获取流程实例的变量 - 响应代码 响应码描述200指…
暂无图片
编程学习 ·

微信每天自动给女[男]朋友发早安和土味情话

微信通知&#xff0c;每天给女朋友发早安、情话、诗句、天气信息等~ 前言 之前逛GitHub的时候发现了一个自动签到的小工具&#xff0c;b站、掘金等都可以&#xff0c;我看了下源码发现也是很简洁&#xff0c;也尝试用了一下&#xff0c;配置也都很简单&#xff0c;主要是他有一…
暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·

项目经理,你有什么优势吗?

大侠被一个问题问住了&#xff1a;你和别人比&#xff0c;你的优势是什么呢? 大侠听到这个问题后&#xff0c;脱口而出道&#xff1a;“项目管理能力和经验啊。” 听者抬头看了一下大侠&#xff0c;显然听者对大侠的这个回答不是很满意&#xff0c;但也没有继续追问。 大侠回家…
暂无图片
编程学习 ·

nginx的负载均衡和故障转移

#注&#xff1a;proxy_temp_path和proxy_cache_path指定的路径必须在同一分区 proxy_temp_path /data0/proxy_temp_dir; #设置Web缓存区名称为cache_one&#xff0c;内存缓存空间大小为200MB&#xff0c;1天没有被访问的内容自动清除&#xff0c;硬盘缓存空间大小为30GB。 pro…
暂无图片
编程学习 ·

业务逻辑漏洞

身份认证安全 绕过身份认证的几种方法 暴力破解 测试方法∶在没有验证码限制或者一次验证码可以多次使用的地方&#xff0c;可以分为以下几种情况︰ (1)爆破用户名。当输入的用户名不存在时&#xff0c;会显示请输入正确用户名&#xff0c;或者用户名不存在 (2)已知用户名。…