189 8069 5689

【C++】STL——list的常用接口-创新互联

list的常用接口

在这里插入图片描述

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名申请、雅安服务器托管、营销软件、网站建设、迎泽网站维护、网站推广。文章目录
  • list的常用接口
  • 一、list的介绍
  • 二、list的使用
    • 1.list的构造
    • 2.迭代器的使用
      • 2.1.begin和end
      • 2.2.rbegin和rend
      • 2.3.范围for
      • 2.4.迭代器的分类
    • 3.list的元素访问函数
      • 3.1.front和back
    • 4.list的容量操作函数
      • 4.1.empty
      • 4.2.size和max_size
    • 5.list修改的相关函数
      • 5.1.push_front和pop_front
      • 5.2.push_back和pop_back
      • 5.3.insert和erase
      • 5.3.clear和resize
      • 5.4.swap
    • 6.list的其他操作函数
      • 6.1.sort
      • 6.2.splice
      • 6.3.move和move_if
      • 6.4.unique和merge
      • 6.5.reverse
    • 7.list与vector对比

一、list的介绍
  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
  4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  5. 与其他序列式容器相比，list和forward_list大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要因素
二、list的使用 1.list的构造
构造函数接口说明
list()构造空的list
list (size_type n, const value_type& val = value_type())构造的list中包含n个值为val的元素
list (const list& x)拷贝构造函数
list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list
  • list()
listlt1;
  • list (size_type n, value_type& val = value_type())
listlt2(4， 1);//构造4个值为1的元素
  • list (const list& x)
listlt3(lt2);//用lt2拷贝构造lt3
  • list (InputIterator first, InputIterator last)
//1、用l2的[begin(), end()）左闭右开的区间构造lt4
listlt4(lt2.begin(), lt2.end());
//2、以数组为迭代器区间构造lt5
int array[] = {1,2,3,4 };
listlt5(array, array + sizeof(array) / sizeof(int));
2.迭代器的使用
函数声明接口说明
begin返回第一个元素的迭代器
end返回最后一个元素下一个位置的迭代器
rbegin返回第一个元素的reverse_iterator,即end位置
rend返回最后一个元素下一个位置的reverse_iterator,即begin位置
2.1.begin和end

begin是返回第一个元素的迭代器，end是返回最后一个元素下一个位置的迭代器。可以通过迭代器进行元素访问：

void list_test1()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list::iterator it = lt.begin();
	while (it != lt.end()) //不能用it< lt.end()
	{cout<< *it<< " ";
		it++;
	}
	cout<< endl;
}
  • 注意：begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动。
2.2.rbegin和rend

和先前学到的string类似，rbegin的第一个元素为尾部end位置，rend返回的是begin的位置。

void list_test1()
{listlt(4, 1);
	list::reverse_iterator rit = lt.rbegin();
    //或者用auto自动识别类型：auto rit = lt.rbegin();
	while (rit != lt.rend()) 
	{cout<< *it<< " "; // 1 1 1 1
		it++;
    }
}
  • 注意：rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。
2.3.范围for

范围for的底层就是迭代器实现的，利用其也可进行元素访问：

void list_test1()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	for(auto e : lt)
   	{cout<< e<< " ";
	}
	cout<< endl;
}
2.4.迭代器的分类
  1. 单向迭代器：只能++，不能–。比如单链表、哈希表等。
  2. 双向迭代器：既能++也能–。比如双向链表。
  3. 随机访问迭代器：既能++、–；又能+、-。比如vector、string。
  4. 迭代器是内嵌类型（内部类或定义在类里）
3.list的元素访问函数
函数声明接口声明
front返回list第一个节点中值的引用
back返回list最后一个节点中值的引用
3.1.front和back

front返回第一个元素，back返回最后一个元素

void list_test2()
{listlt;
	for (int i = 1; i<= 4; i++)
	{lt.push_back(i);//1 2 3 4
	}
	cout<< lt.front()<< endl;//1
	cout<< lt.back()<< endl; //4
}
4.list的容量操作函数
函数声明接口说明
empty检测list是否为空，是返回true，不是返回false
size返回list中有效节点的个数
max_size返回list中的大数据
4.1.empty

empty判断list是否为空

void list_test2()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	
    if(lt.empty())
        cout<< "list empty"<< endl;
    lt.pop_back();
    lt.pop_back();
    lt.pop_back();
    lt.pop_back();
    if(lt.empty())
       	cout<< "list empty"<< endl;
}
4.2.size和max_size

size用来获取list的元素个数，max_size用来获取list的大元素个数。

void list_test2()
{list lt(5, 1);   
	cout<< lt.size()<< endl;// 5
    cout<< lt.max_size()<< endl; // 返回链表长度大值
}
5.list修改的相关函数
函数声明接口声明
push_front在list首元素前插入值为val的元素
pop_front删除list中第一个元素
push_back在list尾部插入值为val的元素
pop_back删除list中最后一个元素
insert在list position 位置中插入值为val的元素
erase删除list position位置的元素
swap交换两个list中的元素
clear清空list中的有效数据
resize为list开辟空间同时进行初始化
5.1.push_front和pop_front

push_front即头插，pop_front即头删。

void list_test3()
{listlt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
	lt.push_front(4);

	for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;

	lt.pop_front();
	lt.pop_front();
    
    for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;
}
5.2.push_back和pop_back

push_back即尾插，pop_back即尾删。

void list_test3()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;

	lt.pop_back();
	lt.pop_back();
	lt.pop_back();
	lt.pop_back();
    
    if(lt.empty())
        cout<< "list empty"<< endl;
}
5.3.insert和erase

list中的insert支持下列三种插入方式：

  1. 在指定位置插入一个值为val的元素
  2. 在指定位置插入n个值为val的元素
  3. 在指定位置插入一段左闭右开的迭代器区间
void list_test3()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	list::iterator pos = find(lt.begin(), lt.end(), 2);
	//1、在3的位置插入值20
	lt.insert(pos, 20);
	for (auto e : lt)
    {cout<< e<< " ";//1 20 2 3 4
	}
	cout<< endl;

	//2、在3的位置插入3个30
	pos = find(lt.begin(), lt.end(), 3);
	lt.insert(pos, 3, 30);
	for (auto e : lt)
    {cout<< e<< " ";//1 20 2 30 30 30 3 4
	}		
	cout<< endl;

	//3、在7的位置插入迭代器区间
	pos = find(lt.begin(), lt.end(), 20);
	listlt2(3, 0);
	lt.insert(pos, lt2.begin(), lt2.end());
	for (auto e : lt)
    {cout<< e<< " ";//1 0 0 0 20 2 30 30 30 3 4
	}
    cout<< endl;
}

erase支持下列两种删除方式：

  1. 删除在指定迭代器位置的元素

  2. 删除指定迭代器区间的元素

void list_test3()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);
	list::iterator pos = find(lt.begin(), lt.end(), 2);
    
	//1、删除2位置的元素
	lt.erase(pos);
	for (auto e : lt)
    {cout<< e<< " ";//1 3 4 5 6     
	}	
	cout<< endl;
    
	//2、删除4到list末尾的所有元素
	pos = find(lt.begin(), lt.end(), 4);
	lt.erase(pos, lt.end());
	for (auto e : lt)
    {cout<< e<< " ";//1 3    
	}
}

注意：这里的find使用的是算法库里面的，list并未提供find算法。

5.3.clear和resize

clear用来清空list中的有效数据。

void list_test4()
{listlt(5, -1);
	for (auto e : lt)
    {cout<< e<< " ";//-1 -1 -1 -1 -1
	}
	cout<< endl;
	lt.clear();
	for (auto e : lt)
    {cout<< e<< " ";//空        
    }
}

resize扩容并初始化分为两种：

如果 n 小于当前容器大小，则内容将减少到其前n个元素，删除超出的元素（并销毁它们）。

如果 n 大于当前容器大小，则通过在末尾插入所需数量的元素来扩展内容，以达到n的大小。如果指定了 val，则新元素将初始化为 val ，否则，它们将被值初始化为0 或者 匿名对象。

void list_test4()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);
    resize(5);
    for(auto e : ch)
    {cout<< e<< " "; // 1 2 3 4 5
    }
    cout<< endl;
    
    resize(8, 10);
    for(auto e : ch)
    {cout<< e<< " "; // 1 2 3 4 5 10 10 10
    }
    cout<< endl;
    
    resize(10);
    for(auto e : ch)
    {cout<< e<< " "; // 1 2 3 4 5 10 10 10 0 0
    }
    cout<< endl;
}
5.4.swap

swap用于交换两个list的内容。

void list_test4()
{listlt1(5, 1);
	listlt2(3, 2);
	lt2.swap(lt1);
	for (auto e : lt1)
	 {cout<< e<< " "; //2 2 2   
	 }
	cout<< endl;

	for (auto d : lt2)
 	{cout<< d<< " "; //1 1 1 1 1     
 	}
}
6.list的其他操作函数
函数声明接口说明
sort对list进行排序
unique删除list中的重复元素
splice将元素从一个list剪切到另一个list
move删除具有特定值的元素
move_if删除满足条件的元素
merge合并排序list
reverse反转list元素的顺序
6.1.sort

list中的sort函数默认排升序。

void list_test5()
{listlt;
	lt.push_back(2);
	lt.push_back(23);
	lt.push_back(6);
	lt.push_back(14);
	lt.push_back(10);
	lt.push_back(100);

	lt.remove(100);
	for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;
	// list 双向循环链表提供
	lt.sort();
	// algorithm 算法库提供
	//sort(lt.begin(), lt.end()); 报错
	for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;

	//迭代器功能分类
	// 1.单向 ++
	// 2.双向 --
	// 3.随机 ++ -- + - ——>vector、string
}

注意：

list单独提供排序是因为它不能用算法库中的排序。算法库中的排序是一个快排，需要满足三数取中以及传递随机访问迭代器，list并不能满足，所以不适用。而list自己提供的排序的底层是归并排序，但是它本身提供的排序比较慢，如果数据量较小，那效率还可以，但是如果数据量很大，我们宁愿把list中的数据尾插到vector中使用算法库中的快排，再拷贝回list中，也不会使用自身的归并排序。

测试一：vector使用算法库中的sortVSlist自身的sort

// N个数据需要排序，vector+ 算法sort  list+ sort
void test_op1()
{srand((unsigned int)time(0));
	const int N = 1000000;
	vectorv;
	v.reserve(N);
	listlt1;

	for (int i = 0; i< N; ++i)
	{auto e = rand();
		v.push_back(e);
		lt1.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	//sort(lt2.begin(), lt2.end());
	lt1.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

测试二：list先把数据拷贝到vector，再排序，排序完成后，再将数据拷贝回list所用时间VSlist使用自身的sort所用时间

void test_op2()
{srand((unsigned int)time(0));
	const int N = 10000000;
	vectorv;
	v.reserve(N);

	listlt1;
	listlt2;
	for (int i = 0; i< N; ++i)
	{auto e = rand();
		//v.push_back(e);
		lt1.push_back(e);
		//lt2.push_back(e);
	}

	// 拷贝到vector排序，排完以后再拷贝回来
	int begin1 = clock();
	for (auto e : lt1)
	{v.push_back(e);
	}
	sort(v.begin(), v.end());
	size_t i = 0;
	for (auto& e : lt1)
	{//e = v[i++];
		lt2.push_back(e);
	}
	int end1 = clock();

	int begin2 = clock();
	//sort(lt2.begin(), lt2.end());
	lt1.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

image-20221214154254163

6.2.splice

splice将元素从一个list剪切到另一个list，被剪切的list没有元素了。

void list_test6()
{listlt1;
	lt1.push_back(10);
	lt1.push_back(20);
	lt1.push_back(30);

	listlt2;
	lt2.push_back(1);
	lt2.push_back(2);
	lt2.push_back(3);
	lt2.push_back(4);

	auto it = lt2.begin();
	++it; // 迭代器下标为2
	lt2.splice(it, lt1); // 把lt1的元素转移到lt2迭代器下标为2的位置
	for (auto e : lt2)
	{cout<< e<< " "; // 1 10 20 30 2 3 4
	}
	cout<< endl;
    for(auto e : lt1)
    {cout<< e<< " "; // 空
    }
}
6.3.move和move_if

move作用是从容器中删除所有与 val 相等的元素。这将调用这些对象的析构函数，并通过删除的元素数来减小容器大小。

void list_test6()
{listlt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
    lt1.push_back(2);
    
	lt1.move(2);
    for(auto e : lt1)
    {cout<< e<< " "; // 1 3 4
    }
    cout<< endl;
}

move_if作用是移除满足条件的元素。这将调用这些对象的析构函数，并通过删除的元素数来减小容器大小。

// 是否为偶数
bool is_even(const int& value)
{return (value % 2) == 0;
}
// 是否为奇数
struct is_odd {bool operator() (const int& value)
  {  return (value % 2) == 1;
  }
};

int main ()
{int arr[]= {15,36,7,17,20,39,4,1};
  	listlt1 (arr, arr+8);  // 15 36 7 17 20 39 4 1
    
  	lt1.remove_if (is_even);    
    
 	for(auto e : lt1)
    {cout<< e<< " "; // 15 36 7 17 39 1
    }
    cout<< endl;
    
  	lt1.remove_if (is_odd());  
    for(auto e : lt1)
    {cout<< e<< " "; // 空
    }
    cout<< endl; 
 	return 0;
}
6.4.unique和merge

unique是删除list中的重复元素。

void list_test5()
{listlt;
 listlt;
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(6);
	lt.push_back(23);
	lt.push_back(10);
	lt.push_back(3);
 lt.push_back(10);
	lt.sort();
	lt.unique();
	for (auto e : lt)
 {cout<< e<< " ";//2 3 6 10 23
 }
}
  • 注意：要想对list进行真正的去重，必须先排序。

merge的作用是合并两个链表，并且这两个链表必须是有序的。

void list_test6()
{listlt1;
	lt1.push_back(10);
	lt1.push_back(30);
	lt1.push_back(20);

	listlt2;
	lt2.push_back(3);
	lt2.push_back(2);
	lt2.push_back(1);
	lt2.push_back(4);

 lt1.sort();
 lt2.sort();
 lt1.merge(lt2);

 for(auto e : lt1)
 { cout<< e<< " "; // 1 2 3 4 10 20 30 
	}
 cout<< endl;
6.5.reverse

reverse的作用是反转list中元素的顺序。

void list_test6()
{listlt1;
    for(int i = 1; i<= 5; i++)
    {lt1.push_back(i);
	}
    reverse(lt1);
    for(auto e : lt1)
    {cout<< e<< " "; // 5 4 3 2 1
	}
    cout<< endl;
}
7.list与vector对比
vectorlist
底层结构动态顺序表，一段连续空间带头结点的双向循环链表
随机访问支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元素效率O(N)
插入和删除任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器原生态指针对原生态指针(节点指针)进行封装
迭代器失效在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


本文标题：【C++】STL——list的常用接口-创新互联
转载注明：http://cdxtjz.cn/article/csgdde.html

其他资讯