STL学习(7)：list

STL学习网址：

C语言中文网：http://c.biancheng.net/stl/

list容器具有如下特性：

可以在头部和尾部插入和删除元素不能随机访问元素，也就是迭代器只能只能++,不能一次性跳转

相对于vector的连续线性空间，list是一个双向链表，它有一个重要性质:插入操作和删除操作都不会造成原有的list迭代器失效，每次插入或删除一个元素，就配置或释放一个元素空间。也就是说，对于任何位置的元素插入或删除，list永远是常数O（1）。

常用函数

//(1)构造函数 list<Elem> c ;//创建一个空的list list<Elem> c1(c2) ;//拷贝另一个同类型元素的list list<Elem> c(n) ;//创建n个元素的list, 每个元素值由缺省构造函数确定 list<Elem> c(n，elem) ;//创建n个元素的list,每个元素值为elem list<Elem> c(begin，end) ;//由迭代器创建list,迭代区间为[begin,end] //(2)大小、判断空函数 int size() const ;//返回容器元素个数 bool empty() const ;//判断容器是否空，若返回true,表明容器已空 //(3)增加、删除函数： void push_back(const T& x) ;//list容器尾元素后增加一个元素x void push_front(const T& x) ;//list容器首元素前增加一个元素x void pop_back() ;//删除容器尾元素，当且仅当容器不为空 void pop_front() ;//删除容器首元素，当且仅当容器不为空 void remove(const T& x) ;//删除容器中所有元素值等于x的元素 void clear() ;//删除容器中所有元素 iterator insert(iterator it, const T& x = T()) ;//在迭带器指针it前插入元素x, 返回x迭带器指针 void insert(iterator it, size_type n, const T& x) ;//在迭带器指针it前插入n个相同元素x void insert(iterator it, const_iterator first, const_iterator last);//把[first, last)间的元素插入迭 带指针it前 iterator erase(iterator it) ;//删除迭带器指针it对应的元素 iterator erase(iterator first, iterator last) ;//删除迭带器指针[first, last）间的元素 //(4)遍历函数 iterator begin() ;//返回首元素的迭带器指针 iterator end() ;//返回尾元素后的迭带器指针，而不是尾元素的迭带器指针 reverse_iterator rbegin() ;//返回尾元素的逆向迭带器指针，用于逆向遍历容器 reverse_iterator rend() ;//返回首元素前的逆向迭带器指针，用于逆向遍历容器 reference front() ;//返回首元素的引用 reference back() ;//返回尾元素的引用 //(5)操作函数 void sort() ;//容器内所有元素排序，默认是升序 template <class Pred> void sort(Pred pr) ;//容器内所有元素根据预判定函数pr排序 void swap(list& str) ;//两list容器交换功能 void unique() ;//容器内相邻元素若有重复的，则仅保留一个 void splice(iterator it, list& x) ;//队列合并函数，队列x所有元素插入迭代指针it前，x变成空队列 void splice(iterator it, list& x, iterator first);//队列x中移走[first,end）间元素插入迭代指针it前 void splice(iterator it, list& x, iterator first, iterator last);// x中移走[first,last）间元素插入迭代指针it前 void reverse() ;//反转容器中元素顺序

 

list的基本操作

int main(int argc, const char * argv[]) { //创建list对象 list<int> l; //尾部添加元素 for (int i = 0; i < 10; i++) { l.push_back(i); } //头部添加元素 l.push_front(111); //遍历 for (list<int>::iterator it = l.begin(); it != l.end(); it++) { cout << *it << " "; } cout << endl; //list不能随机访问 list<int>::iterator it = l.begin(); it++; it++; cout << *it <<endl; // it = it + 1; //编译报错，不能随机访问 // it = it + 5; //编译报错，不能随机访问 return 0; }

list的删除

list提供了两个函数用来删除元素,分别是erase和remove。

erase是通过位置或者区间来删除,主要结合迭代器指针来操作remove是通过值来删除 int main(int argc, const char * argv[]) { //创建list对象 list<int> l; //添加数据 for (int i = 0; i < 10; i++) { l.push_back(i); } l.push_back(100); l.push_back(100); //删除头部元素 l.erase(l.begin()); //删除某个区间 list<int>::iterator it = l.begin(); it++; it++; it++; l.erase(l.begin(), it); //移除值为100的所有元素 l.remove(100); //遍历 for (list<int>::iterator it = l.begin(); it != l.end(); it++) { cout << *it << " "; } cout << endl; return 0; }

list的排序

list 不能使用STL 算法 sort()，必须使用自己的 sort() member function， 因为STL算法sort() 只接受RamdonAccessIterator.

总结：事实上，list有两个版本的sort成员函数：   

  一个是不带参数的sort()，用来实现升序排列；另一个嘛，另一个是带参数的sort(greater<T>   pr)，用来实现降序排列。后者的greater实际上是被VC实作好的一个二元函数（binary   funtion)对象，具体可以参见参考文档[1]

参考：

STL 中list的sort()方法使用总结：https://blog.csdn.net/baidu_35679960/article/details/79592318

 

常用方法一：直接用默认的升序

my_list.sort();

常用方法二：对运算符“（）”重写

struct node{ bool operator()(const int& t1,const int& t2){ return t1 < t2; //<会产生升序排序,若改为>,则变为降序 } }; int main(int argc, const char * argv[]) { list<int> my_list1; for (int i = 0; i < 10; ++i) { my_list1.push_back(rand() % 100); } my_list1.sort(node()); for (list<int>::iterator it = my_list1.begin(); it != my_list1.end(); it++) { cout << *it << " "; } cout << endl; return 0; }

常用方法三：使用回调函数自定义排序规则

bool compare(int a1, int a2){ return a1 < a2; //会产生升序排列，若改为>,则会产生降序； } int main(int argc, const char * argv[]) { list<int> my_list1; for (int i = 0; i < 10; ++i) { my_list1.push_back(rand() % 100); } my_list1.sort(compare); for (list<int>::iterator it = my_list1.begin(); it != my_list1.end(); it++) { cout << *it << " "; } cout << endl; return 0; }

 

 

 

两个链表形成一个链表

#include <stdio.h> #include <iostream> #include <string.h> #include <stdlib.h> #include <ctype.h> #include <vector> #include <stack> #include <list> #include <algorithm> #include <time.h> using namespace std; list<int> *fun(list<int> &list1, list<int> &list2) { list<int> *list3 = new list<int>; list<int>::iterator p1 = list1.begin(); list<int>::iterator p2 = list2.begin(); list<int>::iterator p3; while (p1 != list1.end() && p2 != list2.end()) { if (*p1 < *p2) { list3->push_back(*p1); ++p1; }else{ list3->push_back(*p2); ++p2; } } while (p1 != list1.end()) { list3->push_back(*p1); ++p1; } while (p2 != list2.end()) { list3->push_back(*p2); ++p2; } return list3; } int main(int argc, const char * argv[]) { list<int> my_list1; list<int> my_list2; srand((unsigned int) time(NULL)); for (int i = 0; i < 10; ++i) { my_list1.push_back(rand() % 100);//生成随机数 my_list2.push_back(rand() % 100); } my_list1.sort();//升序排序 my_list2.sort(); list<int> *tmp_list = fun(my_list1, my_list2); for (list<int>::iterator it = tmp_list->begin(); it != tmp_list->end(); it++) { cout << *it << " "; } cout << endl; return 0; }

拼接或归并两个有序表

void main() { LISTINT t1; t1.push_back(1); t1.push_back(5); t1.push_back(3); t1.push_back(10); //1 5 3 10 LISTINT t2; t2.push_back(2); t2.push_back(8); t2.push_back(6); t2.push_back(9); //2 8 6 9 t1.sort(); //1 3 5 10 t2.sort(); //2 6 8 9 //t1.splice(t1.begin(), t2);//2 6 8 9 1 3 5 10 t1.merge(t2); //1 2 3 5 6 8 9 10 for(LISTINT::iterator it=t1.begin(); it != t1.end(); it++) { cout << *it << "\t"; } cout << endl; cout << t1.size() << "\t" << t2.size() << endl; //8 0 }

(1)两个链表merge合并前，一般都已经按升序排好序，合并后的链表元素仍然是升序序列。

(2)merge操作是数据移动操作，不是拷贝操作，因此t1.merge(t2)表示把t2中所有元素依次移动并插入到源链表t1的适当位置，t1增加了多少个元素，t2就减少了多少个元素。

(3)若用t1.splice(t1.begin(), t2)代替程序中的t1.merge(t2),其余不变，就能看出splice的特点。splice完成的是拼接功能,且也是数据移动操作，不是拷贝操作。 t1.splice(t1.begin(), t2)表明把t2中所有元素整体的移动到原始链表t1的首元素前，t1增加了多少个元素，t2就减少了多少个元素。

综合操作示例

两个文本文件中包含某中学的高考成绩，包含准考证号、姓名、所考大学名、总成绩信息，准考证号是关键字。但可能由于一些原因，造成两个文件中有重复的纪录，现要求把两个文件内容和并在一起，去掉重复纪录，并按准考证号升序排列。

分析：

（1）把两个文本文件数据映射成两个list容器中的元素；

（2）对两个list容器分别按准考证号进行升序排序，利用函数是sort；

（3）合并两个已排好序的list容器元素，利用函数是merge;

  (4)利用unique函数去掉准考证号重复的记录，仅保留一个即可。

#include <iostream> #include <list> #include <string> using namespace std; class Student { private: string m_strNO; //准考证号 string m_strName; //姓名 string m_strUniversity; //大学 int m_nTotal; //高考成绩 public: Student(string strNO,string strName,string strUniversity,int nTotal): m_strNO(strNO),m_strName(strName), m_strUniversity(strUniversity),m_nTotal(nTotal) { } bool operator < (Student& s) { return m_strNO<s.GetNO(); } bool operator == (Student& s) { return m_strNO == s.GetNO(); } string GetNO() {return m_strNO;} string GetName() {return m_strName;} string GetUniversity() {return m_strUniversity;} int GetTotal(){return m_nTotal;} }; ostream& operator << (ostream& os, Student& s) { os << s.GetNO() << "\t" << s.GetName() << "\t" << s.GetUniversity() << "\t" <<s.GetTotal(); return os; } typedef list<Student> LISTSTUD; class StudManage { private: LISTSTUD m_stlList; public: bool Add(const Student& s) { m_stlList.push_back(s); return true; } bool Merge(StudManage& stud) { m_stlList.sort(); stud.m_stlList.sort(); m_stlList.merge(stud.m_stlList); m_stlList.unique(); return true; } void Show() { for(LISTSTUD::iterator it=m_stlList.begin(); it != m_stlList.end(); it++) { cout << *it << endl; } } }; void main() { StudManage sm1; StudManage sm2; Student s1("1001", "zhangsan","tsinghua", 670); Student s2("1002", "lisi","beida", 660); Student s3("1003", "wangwu","fudan", 650); Student s4("1004", "zhaoliu","nankai", 640); Student s5("1005", "zhouqi","tongji", 630); sm1.Add(s1); sm1.Add(s2); sm1.Add(s5); sm2.Add(s5); sm2.Add(s4); sm2.Add(s3); sm2.Add(s1); sm1.Merge(sm2); sm1.Show(); }

 

 

 

实例

问题访问这里：https://leetcode-cn.com/problems/relative-ranks/

typedef struct node { int index; int val; bool operator()(struct node& t1, struct node& t2){//重载函数，不然没法比较大小 return t1.val > t2.val; //<会产生升序排序,若改为>,则变为降序 } }NODE; class Solution { public: string Gold = {"Gold Medal"}; string Silver = {"Silver Medal"}; string Bronze = {"Bronze Medal"}; vector<string> findRelativeRanks(vector<int>& nums) { list<NODE> value; NODE tmp_node; vector<string> ret_string(nums.size()); for (int i = 0; i < nums.size(); ++i) { tmp_node.index = i; tmp_node.val = nums[i]; value.push_back(tmp_node);//依次插入链表 } value.sort(node());//降序排序 int i = 1; for (list<NODE>::iterator it = value.begin(); it != value.end(); it++) { if (i < 4) { switch (i) { case 1: ret_string[(*it).index] = Gold; break; case 2: ret_string[(*it).index] = Silver; break; case 3: ret_string[(*it).index] = Bronze; break; } }else{ ret_string[(*it).index] = to_string(i);//对索引下面的元素写字符串 } ++i; } return ret_string; } };