学了又忘学了又忘，明知道会忘又不想复习又还得学
LIST容器
1.1 基本概念
链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的；链表由一系列结点组成
结点：一个是存储数据元素的数据域，一个是存储下一个结点地址的指针域
STL中的链表是一个双向循环链表，迭代器只支持前移和后移（不支持跳跃式访问），属于双向迭代器
优点：可以对任意位置进行快速插入或删除元素，操作方便，修改指针即可，不需要移动大量元素；动态内存分配，不会造成内存浪费和溢出
缺点：容器遍历速度没有数组快，占用空间比数组大；灵活，但空间（指针域）和时间（遍历）额外耗费巨大
LIST有一个重要的性质，插入和删除都不会造成原有LIST迭代器的失效，这在VECTOR里面是不成立的
STL中LIST和VECTOR是两个最常使用容器，各有优缺点
1.2 构造函数
list<T> lst; //采用模板类实现，对象的默认构造形式
list(beg,end); //首尾区间拷贝
list(n,elem); //N个ELEM拷贝
list(const list &lst); //拷贝构造函数
#include<iostream>
#include<list>
#include<string>
using namespace std;
/*
list<T> lst; //采用模板类实现，对象的默认构造形式
list(beg,end); //首尾区间拷贝
list(n,elem); //N个ELEM拷贝
list(const list &lst); //拷贝构造函数
*/
void printl(const list<int>& l) {
for (list<int>::const_iterator it = l.begin(); it != l .end(); it++) {
cout << *it << " ";
}
cout << endl;
}
void test01() {
list<int>l; // list<T> lst;
l.push_back(10);
l.push_back(20);
l.push_back(30);
l.push_back(40);
printl(l);
list<int>l2(l.begin(), l.end());
printl(l2);
list<int>l3(5,100);
printl(l3);
list<int>l4(l);
printl(l4);
}
int main() {
test01();
system("pause");
return 0;
}1.3 赋值和交换
assign(beg,end);
assign(n,elem)
list &operator=(const list &lst);
swap(lst)
#include<iostream>
#include<list>
#include<string>
using namespace std;
/*
assign(beg,end);
assign(n,elem)
list &operator=(const list &lst);
swap(lst)
*/
void printl(const list<int>& l) {
for (list<int>::const_iterator it = l.begin(); it != l .end(); it++) {
cout << *it << " ";
}
cout << endl;
}
void test01() {
list<int>l; // list<T> lst;
l.push_back(10);
l.push_back(20);
l.push_back(30);
l.push_back(40);
printl(l);
list<int>l2;
l2.assign(l.begin(), l.end());
printl(l2);
l2.assign(9, 78);
printl(l2);
cout <<"l2.size()="<< l2.size() << endl;
list<int>l3;
l3 = l;
printl(l3);
cout << "l3.size()=" << l3.size() << endl;
l3.swap(l2);
printl(l2);
cout << "l2.size()=" << l2.size() << endl;
printl(l3);
cout << "l3.size()=" << l3.size() << endl;
}
int main() {
test01();
system("pause");
return 0;
}1.4 大小操作
empty()
size()
lst.resize(n,elem)
lst.resize(n)
#include<iostream>
#include<list>
#include<string>
using namespace std;
/*
empty()
size()
lst.resize(n,elem)
lst.resize(n)
*/
void printl(const list<int>& l) {
for (list<int>::const_iterator it = l.begin(); it != l .end(); it++) {
cout << *it << " ";
}
cout << endl;
}
void isempty(const list<int>& l) {
if (l.empty()) {
cout << "空" << endl;
}
else {
cout << " bubu <" << endl;
cout << " size:" << l.size() << endl;
}
}
void test01() {
list<int>l; // list<T> lst;
isempty(l);
l.push_back(10);
l.push_back(20);
l.push_back(30);
l.push_back(40);
printl(l);
isempty(l);
l.resize(10, 99);
printl(l);
isempty(l);
l.resize(2);
printl(l);
isempty(l);
}
int main() {
test01();
system("pause");
return 0;
}1.5 插入和删除——代码有BUG，暂时搞不懂
push_back(elem) push_front(elem) pop_back() pop_front()
insert(pos,elem)返回新数据位置 insert(pos,n,elem)无返回值 insert(n,beg,end)无返回值
cleae() erase(beg,end)返回下一个数据位置 erase(pos)返回下一个数据位置
remove(elem)删除容器中所有值与ELEM匹配的元素
#include<iostream>
#include<list>
#include<string>
using namespace std;
/*
push_back(elem) push_front(elem) pop_back() pop_front()
insert(pos,elem)返回新数据位置 insert(pos,n,elem)无返回值 insert(n,beg,end)无返回值
cleae() erase(beg,end)返回下一个数据位置 erase(pos)返回下一个数据位置
remove(elem)删除容器中所有值与ELEM匹配的元素
*/
void printl(const list<int>& l) {
for (list<int>::const_iterator i = l.begin(); i != l .end(); i++) {
cout << *i<< " ";
}
cout << endl;
}
void isempty(const list<int>& l) {
if (l.empty()) {
cout << "空" << endl;
}
else {
cout << " bubu <" << endl;
cout << " size:" << l.size() << endl;
}
}
void test01() {
list<int>l;
l.push_back(10);
l.push_back(20);
l.push_back(30);
l.push_back(40);
l.push_front(111);
l.push_front(222);
l.push_front(333);
printl(l);
isempty(l);
l.pop_back();
l.pop_front();
printl(l);
list<int>::iterator it = l.begin();
//l.insert(it,10000);
it++;
//cout << it << endl;
l.insert(it, 4);//在第 1 个位置后面 插入,返回新数据位置 2
printl(l);
it++;//it--2，it++=3
l.insert(it, 99,3);//在第 3 个位置后面 插入，it= 4+99=103
printl(l);
l.insert(it,l.begin(),l.end());//在第 it 个位置后面 插入
printl(l);
l.erase(it);
printl(l);
//l.erase(it);//加上就报错，说无效参数传……*&&（*&（……
//l.erase(l.end());//
l.remove(3);
printl(l);
l.erase(l.begin());
printl(l);
l.clear();
printl(l);
}
int main() {
test01();
system("pause");
return 0;
}1.6 数据存取
front() back()，不支持中括号的方式访问，本质是链表，因为不是连续的线性空间存储数据，迭代器也不支持随机访问
++，--就是支持双向，+N就是支持随机
#include<iostream>
#include<list>
#include<string>
using namespace std;
/*
front() back()
*/
void printl(const list<int>& l) {
for (list<int>::const_iterator i = l.begin(); i != l .end(); i++) {
cout << *i<< " ";
}
cout << endl;
}
void isempty(const list<int>& l) {
if (l.empty()) {
cout << "空" << endl;
}
else {
cout << " bubu <" << endl;
cout << " size:" << l.size() << endl;
}
}
void test01() {
list<int>l;
l.push_back(10);
l.push_back(20);
l.push_back(30);
l.push_back(40);
l.push_front(111);
l.push_front(222);
l.push_front(333);
printl(l);
isempty(l);
cout << l.front() << endl;
cout << l.back() << endl;
}
int main() {
test01();
system("pause");
return 0;
}1.7 反转和排序
reverse()//反转链表 sort()链表排序——升序降序
#include<iostream>
#include<list>
#include<string>
#include<algorithm>
using namespace std;
/*
reverse()//反转链表 sort()链表排序
*/
void printl(const list<int>& l) {
for (list<int>::const_iterator i = l.begin(); i != l .end(); i++) {
cout << *i<< " ";
}
cout << endl;
}
bool mycompare(int v1, int v2) {
//降序，第一个数，大于，第二个数
return v1 > v2;
}
void test01() {
list<int>l;
l.push_back(10);
l.push_back(20);
l.push_back(30);
l.push_back(40);
l.push_front(111);
l.push_front(222);
l.push_front(333);
printl(l);
l.reverse();
printl(l);
//sort(l.begin(),l.end());//所有不支持随机访问迭代器的容器，不可以用标准算法
//但容器内部会提供对应的一些算法，成员函数
l.sort();
printl(l);
l.sort(mycompare);
printl(l);
}
int main() {
test01();
system("pause");
return 0;
}1.8 排序案例——Person自定义数组类型进行排序，Person(姓名，年龄，身高）
年龄升序，年龄相同身高降序
先指定排序规则，再直接调用
#include<iostream>
#include<list>
#include<string>
using namespace std;
/*
Person自定义数组类型进行排序，Person(姓名，年龄，身高）
年龄升序，年龄相同身高降序
*/
class Person {
public:
Person(string name, int age, int tall) {
this->_name = name;
this->_age = age;
this->_tall = tall;
}
public:
string _name;
int _age;
int _tall;
};
void printl(const list<Person>& l) {
for (list<Person>::const_iterator it = l.begin(); it != l .end(); it++) {
cout << "选手： " << it->_name << "\t年龄： " << it->_age << "\t身高:" << it->_tall << endl;
}
cout << endl;
}
void setpp(list<Person>& l) {
Person p1("有哈", 18, 180);
Person p2("hhki", 16, 190);
Person p3("黄金分割", 22, 210);
Person p4("会后i", 16, 130);
Person p5("经济", 30, 150);
l.push_back(p1);
l.push_back(p2);
l.push_back(p3);
l.push_back(p4);
l.push_back(p5);
}
void setpp2(list<Person>& l) {
srand((unsigned int)time(NULL));
string nameseed = "abcde";
for (int i = 0; i < 5; i++) {
string name = "选手";
name += nameseed[i];
int age = rand() % 21 + 20;
int tall = rand() % 51 + 150;
Person p(name, age, tall);
l.push_back(p);
}
}
//指定排序规则
bool mycompare(Person&p1,Person&p2) {
if (p1._age == p2._age) {
return p1._tall < p2._tall;
}
else {
return p1._age < p2._age;
}
}
void test01() {
list<Person>l;
//setpp(l);
setpp2(l);
printl(l);
l.sort(mycompare);
printl(l);
}
int main() {
test01();
system("pause");
return 0;
}