list 基本概念
- list 容器将数据进行链式存储,是一个双向循环链表
- list 存储方式不是连续存储空间,迭代器只能前移和后移,属于双向迭代器
- list 数据元素的逻辑顺序是通过指针链实现的
- list 由一系列结点组成。节点由数据域和指针域构成
- list 插入和删除不会造成原迭代器失效,这对 vector 是不成立的
- list 和 vector 是最常被使用的容器
list 优点:
- list 可以对任意位置进行快速插入和删除
- 采用动态存储分配,不会造成内存的浪费和移除
list 缺点:
- list 遍历速度没有 vector 快
- list 占用的控件比 vector 大

list 构造函数
list<T> li1;
list<T> li2( li1.begin(), li1.end() ); // [ begin, end ),左闭右开
list<T> li3( n, elem );
list<T> li4( const list& lst )
void list_print(const list<int>& li) { for (list<int>::const_iterator it = li.begin(); it != li.end(); it++) { cout << *it << " "; } cout << endl; } void list_constructor() { list<int> li1; li1.push_back(10); li1.push_back(20); li1.push_back(30); li1.push_back(40); list_print(li1); list<int> li2(li1.begin(), li1.end()); list_print(li2); list<int> li3(li2); list_print(li3); list<int> li4(10, 1000); list_print(li4); }
list 赋值和交换
list& operator=( const list& lst );
void assign( li.begin(), li.end() ); // [ begin, end ),左闭右开
void assign( n, elem);
void swap( list& lst )
;
void list_assign() { list<int> li1; li1.push_back(10); li1.push_back(20); li1.push_back(30); li1.push_back(40); list_print(li1); list<int> li2 = li1; list_print(li2); list<int> li3; li3.assign(li2.begin(), li2.end()); list_print(li3); list<int> li4; li4.assign(10, 100); list_print(li4); } void list_swap() { list<int> li1; li1.push_back(10); li1.push_back(20); li1.push_back(30); li1.push_back(40); list_print(li1); list<int> li2; li2.assign(10, 100); cout << "交换前:" << endl; list_print(li1); list_print(li2); cout << "交换后:" << endl; li1.swap(li2); list_print(li1); list_print(li2); }
list 大小操作
bool empty();
int size();
void resize( int num );
void resize ( int num, elem );
void list_size() { list<int> li; li.push_back(10); li.push_back(20); li.push_back(30); li.push_back(40); list_print(li); if (li.empty()) { cout << "li 为空" << endl; } else { cout << "li 不为空" << endl; cout << "li 的元素个数为:" << li.size() << endl; } li.resize(10); list_print(li); li.resize(15, 10000); list_print(li); li.resize(2); list_print(li); }
list 插入和删除
void push_back( elem );
void pop_back();
void push_front( elem );
void pop_front();
iterator insert( const_iterator pos, elem );
iterator insert( const_iterator pos, int count, elem );
iterator insert( const_iterator pos, li.begin(), li.end() );
iterator erase( const_iterator pos);
iterator erase( li.begin(), li.end() );
void remove( elem )
void clear();
void list_insertAndErase() { list<int> li; li.push_back(10); li.push_back(20); li.push_back(30); li.push_front(100); li.push_front(200); li.push_front(300); list_print(li); li.pop_back(); li.pop_front(); list_print(li); li.insert(++li.begin(), 1000); list_print(li); li.erase(li.begin()); list_print(li); li.push_back(10000); li.push_back(10000); li.push_back(10000); li.push_back(10000); list_print(li); li.remove(10000); list_print(li); li.clear(); list_print(li); }
list 数据存取
T& front();
T& back();
- 迭代器支持
it++
和it--
,但是不支持it += 1
和it -= 1
void list_frontAndBack() { list<int> li; li.push_back(10); li.push_back(20); li.push_back(30); li.push_back(40); cout << "第一个元素:" << li.front() << endl; cout << "最后一个元素:" << li.back() << endl; }
list 反转和排序
void reverse();
void sort();
- 注意,不支持随机访问迭代器的容器,会提供对应的成员函数用于排序
bool compare(int num1, int num2) { return num1 > num2; } void list_sort() { list<int> li; li.push_back(20); li.push_back(10); li.push_back(50); li.push_back(40); li.push_back(30); list_print(li); li.sort(); list_print(li); li.sort(compare); list_print(li); }
排序案例:
class Person { public: string m_name; int m_age; int m_height; Person(string name, int age, int height) { this->m_name = name; this->m_age = age; this->m_height = height; } }; bool comparePerson(Person& p1, Person& p2) { if (p1.m_age != p2.m_age) { return p1.m_age < p2.m_age; } return p1.m_height > p2.m_height; } void list_sortExample() { list<Person> li; li.push_back(Person("刘备", 35, 175)); li.push_back(Person("曹操", 45, 180)); li.push_back(Person("孙权", 40, 170)); li.push_back(Person("赵云", 25, 190)); li.push_back(Person("张飞", 35, 160)); li.push_back(Person("关羽", 35, 200)); for (list<Person>::iterator it = li.begin(); it != li.end(); it++) { cout << "姓名:" << (*it).m_name << "年龄:" << (*it).m_age << "身高:" << (*it).m_height << endl; } cout << "-------------------------------------" << endl; cout << "排序后:" << endl; li.sort(comparePerson); for (list<Person>::iterator it = li.begin(); it != li.end(); it++) { cout << "姓名:" << (*it).m_name << "年龄:" << (*it).m_age << "身高:" << (*it).m_height << endl; } }