list

  • list是可以在常数范围内在任意位置进行插入和删除的序列式容器, 并且该容器可以前后双向迭代
  • list的底层是双向链表结构, 双向链表中每个元素存储在互不相关的独立节点中, 在节点中通过指针指向前一个元素和后一个元素
  • forward_list是单链表, 只能朝前迭代, 更简单高效
  • 与其他的序列式容器相比, list通常在任意位置进行插入, 移除元素的效率更好
  • 与其他的序列式容器相比, list和forward_list最大的缺陷是不支持任意位置的随机访问

list的接口

  • list的构造
    list()				// 构造空的list
    list(size_t n, const val_t& val = val_t())	// 构造的list包含n个值为val的元素
    list(const list& x)			// 构造拷贝函数
    list(Inputlterator first, Inputlterator last)	// 用(first, last)区间的元素构造list
    
    include <iostream>
    include <list>
    
    int main() {
    	std::list<int> l1;		// 构造空的l1
    	std::list<int> l2 (4, 100);		// l2中放4个值为100的元素
    	std::list<int> l3 (l2.begin(), l2.end());	// 用l2的[begin(), end())左闭右开的区间构造l3
    	std::list<int> l4 (l3);		// 用拷贝构造l4
    	
    	// 以数组为迭代器区间构造l5
    	int array[] = {1, 2, 3, 4};
    	std::list<int> l5 (array, array + sizeof(array) / sizeof(int));
    	
    	// 用迭代器方式打印l5的元素
    	for(std::list<int>::iterator it = l5.begin(); it != l5.end(); it++) {
    		std::cout << *it << " ";
    	}
    	std::cout << endl;
    	return 0;
    }
    
  • list iterator的使用
    begin + end			// 返回第一个元素的迭代器 返回最后一个元素下一个位置的迭代器
    rbegin + rend 		// 返回第一个元素的位置 返回第一个元素的前一个位置
    
    1. begin和end为正向迭代器, 对迭代器执行++操作, 迭代器向后移动
    2. rbegin和rend为反向迭代器, 迭代器向前移动
    #include <iostream>
    using namespace std;
    #include <list>
    
    void print_list(const list<int>& l) {
    	for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) {
    		cout << *it << " ";
    	}
    	cout << endl;
    }
    
    int main() {
    	int array[] = {1, 2, 3, 4, 5, 6, 7, 8};
    	list<int> l(array + sizeof(array) / sizeof(array[0]));
    	// 使用正向迭代器正向list中的元素
    	for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
    		cout << *it << " ";
    	}
    	cout << endl;
    	// 使用反向迭代器逆向打印list的元素
    	for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it) {
    		cout << *it << " ";
    	}
    	cout << endl;
    	return 0;
    }
    
  • list capacity
    empty				// 检测list是否为空, 是返回true, 否则返回false
    size				// 返回list中有效节点的个数
    
  • list element access
    front				// 返回list的第一个节点中值的引用
    back				// 返回list的最后一个节点中值的引用
    
  • list modifiers
    push_front			// 在list首元素前插入值为val的元素
    pop_front			// 删除list中第一个元素
    push_back			// 在list尾部插入值为val的元素
    pop_back			// 删除list最后一个元素
    insert				// 在pos位置中插入值为val的元素
    erase				// 删除pos位置的元素
    swap				// 交换两个list中的元素
    clear				// 清空list中的有效元素
    

list和vector的对比

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

 


我们的征途是星辰大海!