list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。
支持++ -- 但是不支持+和-
list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。
链表的主流访问方式就是迭代器
list构造
1) 空容器构造函数(默认构造函数)
构造一个没有元素的空容器。
(2) 填充构造函数
构造一个包含 n 个元素的容器。每个元素都是 val 的副本。
(3) 范围构造函数
构造一个容器,其中包含与范围 [first,last] 一样多的元素,每个元素都按相同的顺序从该区域中的相应元素构造。
(4) 复制构造函数
以相同的顺序构造一个容器,其中包含 x 中每个元素的副本。
int main()
{std::list<int> first; //空构造 std::list<int> second(4, 100); //4个值为100的构造 std::list<int> third(second.begin(), second.end()); //范围构造std::list<int> fourth(third); //拷贝构造int myints[] = { 16,2,77,29 };std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int));//也可以使用其他容器进行范围构造std::cout << "The contents of fifth are: ";for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)std::cout << *it << ' ';std::cout <<endl;return 0;
}
void list1()
{list<int>l1 = { 1,2,3,4,5,6 };list<int>::iterator it = l1.begin();while(it != l1.end()){cout << *it << " ";it++;}cout << endl;}
list迭代器
list的begin()指向头结点的下一个结点 也就是第一个有效元素的结点 end()指向头节点 也就是最后有效元素的下一个结点 rbegin()指向头结点 rend()指向头节点的下一个结点
list的成员函数empty是检测链表是否为空 并且返回布尔值 若为空 返回1 若不为空 返回0
返回链表容器中的元素数
front 和back 分别返回链表的第一个有效元素 和最后一个有效元素 有const和非const两个版本
list::push_front (const vallue_type & val) list ::push_back(const value_type& val)
分别对链表进行头插 和尾插
list::pop_front () list ::pop_back()
分别对链表进行头删和尾删
(1)通过在指定位置插入单个元素
(2) 通过在指定的位置插入 n个相同的val元素
(3)通过在指定的位置 范围插入一段内容
(1)在指定位置删除单个元素
(2)在指定的范围内删除所有元素
list无法使用alogrithm库 中的sort进行排序
void list1()
{list<int>l1 = { 1,2,3,4,5,6 };list<int>::iterator it = l1.begin();while(it != l1.end()){cout << *it << " ";it++;}cout << endl;sort(l1.begin(),l1.end());
}
原因是sort底层是快排 要使用随机迭代器 但是list是双向迭代器
那么链表如何排序呢
在链表的成员函数中存在专门为链表排序的sort成员函数
void list1()
{list<int>l1 = { 1,2,3,4,5,6 ,1,3,4};list<int>::iterator it = l1.begin();while(it != l1.end()){cout << *it << " ";it++;}cout << endl;//sort(l1.begin(),l1.end());l1.sort();list<int>::iterator it1 = l1.begin();while (it1 != l1.end()){cout << *it1 << " ";it1++;}
}
这是默认升序 如果想要降序那么就要传仿函数作为参数进入
void list1()
{list<int>l1 = { 1,2,3,4,5,6 ,1,3,4};list<int>::iterator it = l1.begin();while(it != l1.end()){cout << *it << " ";it++;}cout << endl;//sort(l1.begin(),l1.end());l1.sort();list<int>::iterator it1 = l1.begin();while (it1 != l1.end()){cout << *it1 << " ";it1++;}cout << endl;//greater<int>gt;l1.sort(greater<int>());for (auto e:l1){cout << e << " ";}cout << endl;
}
在现在的链表中是存在重复的数据的 如果想要去重该如何
有专门的去重成员函数unique
void list1()
{list<int>l1 = { 1,2,3,4,5,6 ,1,3,4};list<int>::iterator it = l1.begin();while(it != l1.end()){cout << *it << " ";it++;}cout << endl;//sort(l1.begin(),l1.end());l1.sort();list<int>::iterator it1 = l1.begin();while (it1 != l1.end()){cout << *it1 << " ";it1++;}cout << endl;//greater<int>gt;l1.sort(greater<int>());for (auto e:l1){cout << e << " ";}cout << endl;l1.unique();for (auto e : l1){cout << e << " ";}cout << endl;
}
但是list.sort排序的效率相较于快速排序的sort的效率还是非常低的 这点需要注意
拼接(转移)
接合
第一个版本 (1) 将 x 的所有元素传输到容器中。
第二个版本 (2) 仅将 i 指向的元素从 x 传输到容器中。
第三个版本 (3) 将范围 [first,last] 从 x 传输到容器中
void list2()
{std::list<int> mylist1, mylist2;std::list<int>::iterator it;// set some initial values:for (int i = 1; i <= 4; ++i)mylist1.push_back(i); // mylist1: 1 2 3 4for (int i = 1; i <= 3; ++i)mylist2.push_back(i * 10); // mylist2: 10 20 30it = mylist1.begin();++it; // points to 2mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4for (auto e:mylist1){cout << e << " ";}cout << endl;
}
这里使用的是第一个版本 将lsit容器x的全部元素插入 到 mylist1的pos位置 且此时链表二中被转移的内容是不会在存在在链表二的 相当于是转移
链表中不存在find 所以想要使用find需要使用算法库中的find
第一个参数和第二个参数确定查找的范围 第三个元素是要查找的元素
void list3()
{list<int> mylist1;for (int i = 1; i <= 4; i++)mylist1.push_back(i);auto it = find(mylist1.begin(),mylist1.end(),3);mylist1.splice(mylist1.begin() , mylist1,it);for (auto e : mylist1){cout << e << " ";}cout << endl;
}