学了又忘学了又忘，明知道会忘又不想复习又还得学
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 个位置后面 插入,返回新数据位置 2printl(l);it++;//it--2，it++=3l.insert(it, 99,3);//在第 3 个位置后面 插入，it= 4+99=103printl(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;
}
