list的常用接口

一、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()

list<int> lt1;

• list (size_type n, value_type& val = value_type())

list<int> lt2(4， 1);//构造4个值为1的元素

• list (const list& x)

list<int> lt3(lt2);//用lt2拷贝构造lt3

• list (InputIterator first, InputIterator last)

//1、用l2的[begin(), end()）左闭右开的区间构造lt4
list<int> lt4(lt2.begin(), lt2.end());
//2、以数组为迭代器区间构造lt5
int array[] = { 1,2,3,4 };
list<int> lt5(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()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::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()
{list<int> lt(4, 1);list<int>::reverse_iterator rit = lt.rbegin();//或者用auto自动识别类型：auto rit = lt.rbegin();while (rit != lt.rend()) {cout << *it << " "; // 1 1 1 1it++;}
}

• 注意：rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。

2.3.范围for

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

void list_test1()
{list<int> lt;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()
{list<int> lt;for (int i = 1; i <= 4; i++){lt.push_back(i);//1 2 3 4}cout << lt.front() << endl;//1cout << lt.back() << endl; //4
}

---

4.list的容量操作函数

函数声明	接口说明
empty	检测list是否为空，是返回true，不是返回false
size	返回list中有效节点的个数
max_size	返回list中的最大数据

4.1.empty

empty判断list是否为空

void list_test2()
{list<int> lt;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;// 5cout << 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()
{list<int> lt;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()
{list<int> lt;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()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator pos = find(lt.begin(), lt.end(), 2);//1、在3的位置插入值20lt.insert(pos, 20);for (auto e : lt){	cout << e << " ";//1 20 2 3 4}cout << endl;//2、在3的位置插入3个30pos = 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);list<int> lt2(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()
{list<int> lt;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<int>::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()
{list<int> lt(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()
{list<int> lt;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()
{list<int> lt1(5, 1);list<int> lt2(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()
{list<int> lt;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使用算法库中的sort VS list自身的sort

// N个数据需要排序，vector+ 算法sort  list+ sort
void test_op1()
{srand((unsigned int)time(0));const int N = 1000000;vector<int> v;v.reserve(N);list<int> lt1;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所用时间 VS list使用自身的sort所用时间

void test_op2()
{srand((unsigned int)time(0));const int N = 10000000;vector<int> v;v.reserve(N);list<int> lt1;list<int> lt2;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);
}

6.2.splice

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

void list_test6()
{list<int> lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);list<int> lt2;lt2.push_back(1);lt2.push_back(2);lt2.push_back(3);lt2.push_back(4);auto it = lt2.begin();++it; // 迭代器下标为2lt2.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()
{list<int> lt1;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};list<int> lt1 (arr, arr+8);  // 15 36 7 17 20 39 4 1lt1.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()
{list<int> lt;list<int> lt;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()
{list<int> lt1;lt1.push_back(10);lt1.push_back(30);lt1.push_back(20);list<int> lt2;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()
{list<int> lt1;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对比

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

---