C++ STL 容器list如何改写为长尾？

本文共计2506个文字，预计阅读时间需要11分钟。

1、List基本概念

1.1、概念描述

链表（List）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的组成：链表由一系列节点组成，每个节点包含数据和指针两部分。功能：将数据元素存储在内存中，实现动态数据管理。

1、list基本概念

1.1、概念描述

链表（list）是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的

链表的组成：链表由一系列结点组成

功能：将数据进行链式存储

1.2、结点的组成

一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

STL中的链表是一个双向循环链表

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

1.3、list的优点

• 采用动态存储分配，不会造成内存浪费和溢出
• 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

1.4、list的缺点

• 链表灵活，但是空间(指针域) 和 时间（遍历）额外耗费较大

1.5、总结

List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

STL中list和vector是两个最常被使用的容器，各有优缺点

2、list构造函数

2.1、功能描述

• 创建list容器

2.2、函数原型

• list<T> lst; //list采用采用模板类实现,对象的默认构造形式：
• list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。
• list(n,elem); //构造函数将n个elem拷贝给本身。
• list(const list &lst); //拷贝构造函数。

2.3、示例

//list容器的构造 void printList(const list<int> li) { for (list<int>::const_iterator it = li.begin(); it != li.end();it++) { cout << *it << " "; } cout << endl; } void test01() { //1、默认构造 list<int> li; //插入元素 li.push_back(10); li.push_back(20); li.push_back(30); li.push_back(40); //打印链表 printList(li); //2、区间构造 list<int> li2(li.begin(),li.end()); printList(li2); //3、n个elem list<int> li3(4,100); printList(li3); //4、拷贝构造 list<int> li4(li3); printList(li4); } int main() { test01(); }

3、list赋值和交换

3.1、功能描述

• 给list容器进行赋值，以及交换list容器

3.2、函数原型

• assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
• assign(n, elem); //将n个elem拷贝赋值给本身。
• list& operator=(const list &lst); //重载等号操作符
• swap(lst); //将lst与本身的元素互换。

3.3、示例

//list容器的赋值和交换 void printList(const list<int> li) { for (list<int>::const_iterator it = li.begin(); it != li.end(); it++) { cout << *it << " "; } cout << endl; } void test01() { list<int> L; L.push_back(10); L.push_back(20); L.push_back(30); L.push_back(40); printList(L); //1、=赋值 list<int> L2; L2 = L; printList(L2); //2、assign区间赋值 list<int> L3; L3.assign(L.begin(),L.end()); printList(L3); //3、assign n个elem赋值 list<int> L4; L4.assign(4,100); printList(L4); //4、交换 cout << "交换前：" << endl; printList(L3); printList(L4); L4.swap(L3); cout << "交换后：" << endl; printList(L3); printList(L4); } int main() { test01(); }

4、list大小操作

4.1、功能描述

• 对list容器的大小进行操作

4.2、函数原型

• size(); //返回容器中元素的个数
• empty(); //判断容器是否为空
• resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。//如果容器变短，则末尾超出容器长度的元素被删除。
• resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。 //如果容器变短，则末尾超出容器长度的元素被删除。

4.3、示例

//list容器的大小操作 void printList(const list<string>& L) { for (list<string>::const_iterator it = L.begin(); it != L.end();it++) { cout << *it << " "; } cout << endl; } void test01() { list<string> ls; ls.push_back("ab"); ls.push_back("cd"); ls.push_back("ef"); ls.push_back("gh"); printList(ls); //1、判断是否为空 if (ls.empty()) { cout << "list为空" << endl; } else { cout << "list不为空" << endl; //2、获取大小 cout << "list大小：" << ls.size() << endl; } //重新指定大小 //过长，填充默认值,默认为空格" " ls.resize(10); printList(ls); //过长，填充指定值 ls.resize(15,"hh"); printList(ls); //过短，发生截取 ls.resize(2); printList(ls); } int main() { test01(); system("pause"); return 0; }

5、list插入和删除

5.1、功能描述

• 对list容器进行数据的插入和删除

5.2、函数原型

• push_back(elem);//在容器尾部加入一个元素
• pop_back();//删除容器中最后一个元素
• push_front(elem);//在容器开头插入一个元素
• pop_front();//从容器开头移除第一个元素
• insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
• insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
• insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
• clear();//移除容器的所有数据
• erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
• erase(pos);//删除pos位置的数据，返回下一个数据的位置。
• remove(elem);//删除容器中所有与elem值匹配的元素。

5.3、示例

void test01() { list<int> li; //1、尾插 10 20 li.push_back(10); li.push_back(20); printList(li); //2、头插 200 100 10 20 li.push_front(100); li.push_front(200); printList(li); //3、尾删 200 100 10 li.pop_back(); printList(li); //4、头删 100 10 li.pop_front(); printList(li); //5、插入 //40 100 10 li.insert(li.begin(), 40); //插入一个 printList(li); //40 100 10 50 50 li.insert(li.end(),2,50); //插入n个elem,2个50 printList(li); //40 100 10 50 50 40 100 10 50 50 li.insert(li.end(),li.begin(),li.end()); //插入一个区间 printList(li); //6、删除 //40 50 li.erase(++li.begin(),--li.end()); //删除指定区间 printList(li); //50 li.erase(li.begin()); //删除指定位置 printList(li); //7、清空 li.clear(); printList(li); } int main() { test01(); system("pause"); return 0; }

6、list数据存取

6.1、功能描述

• 对list容器中数据进行存取

6.2、函数原型

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

6.3、示例

void test01() { list<int> li; li.push_back(10); li.push_back(20); li.push_back(30); li.push_back(40); cout << "访问第一个元素：" << li.front() << endl; cout << "访问最后一个元素：" << li.back() << endl; } int main() { test01(); }

注意事项：

list容器没有 [] ,at() ,不可以用这样的方式访问数据，会报错

原因：list本质是一个链表，不是用连续的空间存储数据，迭加器不支持随机访问

7、list反转和排序

7.1、功能描述

• 将容器中的元素反转，以及将容器中的数据进行排序

7.2、函数原型

• reverse(); //反转链表
• sort(); //链表排序

7.3、示例

//list容器的反转和排序 void printList(const list<int>& L) { for (list<int>::const_iterator it = L.begin(); it != L.end();it++) { cout << *it << " "; } cout << endl; } bool myCompare(int v1,int v2) { return v1 > v2; //v1 > v2 表示降序，反之升序 } void test01() { list<int> li; li.push_back(10); li.push_back(30); li.push_back(20); li.push_back(50); li.push_back(40); //1、反转 cout << "反转前：" << endl; printList(li); li.reverse(); cout << "反转后：" << endl; printList(li); //2、排序 cout << "排序前：" << endl; printList(li); //默认升序 li.sort(); cout << "默认升序排序后：" << endl; printList(li); //重载降序： li.sort(myCompare); cout << "重载降序排序后：" << endl; printList(li); } int main() { test01(); }

注意事项：

1、所有不支持随机访问迭代器的容器，都不可以使用标准库的算法

2、不支持随机范文迭代器的容器，但对象内部会提供一些对应算法的成员函数

8、排序案例

8.1、案例描述

将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高

8.2、排序规则

按照年龄进行升序，如果年龄相同按照身高进行降序

8.3、示例

//list 自定义类型，自定义规则排序案例 //按照年龄进行升序，如果年龄相同按照身高进行降序 #include<list> class Person { public: Person(string name,int age,int height):m_name(name),m_age(age),m_height(height){} string m_name; int m_age; int m_height; }; void printList(list<Person> L) { for (list<Person>::const_iterator it = L.begin(); it != L.end();it++) { cout << "姓名：" << it->m_name << "年龄：" << it->m_age << "身高：" << it->m_height << endl;; } } bool myCompare(const Person& p1,const 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 test01() { list<Person> lp; Person p1("刘备", 35, 175); Person p2("曹操", 45, 180); Person p3("孙权", 40, 170); Person p4("赵云", 25, 190); Person p5("张飞", 35, 160); Person p6("关羽", 35, 200); lp.push_back(p1); lp.push_back(p2); lp.push_back(p3); lp.push_back(p4); lp.push_back(p5); lp.push_back(p6); cout << "排序前：" << endl; printList(lp); cout << "------------------" << endl; cout << "排序后" << endl; //自定义排序规则 lp.sort(myCompare); printList(lp); } int main() { test01(); system("pause"); return 0; }