date: 2020/01/10

vector, list, deque均为顺序容器

vector

http://www.cplusplus.com/reference/vector/vector/

http://c.biancheng.net/view/348.html

#include <vector> 

可变长动态数组,随机访问快、尾部增删快,随机增删慢,超出容量需要重新分配内存

基本使用

#include <vector>
std::vector<int> vec;

构造

vector();   // 默认
vector(int n, const T &val = T());   // 用n个val填充
vector(iterator first, iterator last);   // 用迭代器构造
vector(const vector &v);   // 拷贝

属性

bool empty();   // 是否为空(size为0)
size_type size();     // 获取当前长度
size_type capacity(); // 获取当前已分配的内存空间大小
size_type max_size(); // 获取操作系统或底层实现所允许的最大长度(注意与capacity区分)
void resize(size_type n, T val = T());  // 修改size为n,若n小于当前size则丢弃尾部多余数据,若大于当前size则在尾部填充val
void reserve(size_type n);   // 要求容器的capacity必须大于等于n

访问与修改

// 访问
T &front();                  // 获取第一个元素
T &back();                   // 获取最后一个元素
T &at(size_type n);          // 访问第n个元素
T &operator[](size_type n);  // 同at

// 单次修改(也可以直接对at或[]获取的引用修改)
void push_back(const T& val);  // 尾部追加
void pop_back();    // 尾部弹出(注意,不返回值)
iterator insert(iterator position, const T& val);    // 指定位置插入(必须用迭代器)
iterator erase(iterator position);   // 删除指定位置元素(必须用迭代器)

// 批量修改
void insert(iterator position, size_type n, const T& val);   // 指定位置插入重复元素
void insert(iterator position, iterator first, iterator last);   // 用另一个迭代器来插入到指定位置
void clear();     // 清空
iterator erase(iterator first, iterator last);   // 在指定位置批量删除
void swap(vector<T> &v);    // 跟另一个vector交换空间(本质是直接交换指针,而不需要拷贝内存)

遍历

std::vector<int> vec(10);
int sum = 0;

// 迭代器遍历
for(std::vector<int>::iterator it = vec.begin(); it != vec.end(); it++){
    sum += *it;
}

// 索引遍历(不适用于list)
for(int i = 0; i < vec.size(); i++){
    sum += vec[i];   
}


list

#include <list> 

http://www.cplusplus.com/reference/list/list/

http://c.biancheng.net/view/351.html

双向链表,不支持随机访问(不支持STL-sort,但有独立的sort方法),随机增删快。用法与vector类似,头文件 #include <list> 。

对应的也有单向链表结构 forward_list 

(以下省略与vector相同的接口)

void push_front(const T &val);  // 在头部添加元素
void pop_front();    // 删除头部元素
void sort();    // 排序
void remove (const T &val);     // 删除值为val的所有元素
void remove_if(bool (*pred)(const T &val));    // 删除满足条件的所有元素
void unique();    // 删除连续的重复元素(只保留第一个)
void merge(list <T> &x);    // 在自身有序的前提下,与另一个有序链表x合并,并保持有序
void splice(iterator i, list <T> &x, iterator i);   // 在指定位置插入链表x的一个结点(剪切操作而不是拷贝)
void splice(iterator i, list <T> &x, iterator first, iterator last);   // 在指定位置插入链表x的一部分(剪切操作而不是拷贝)


示例:设计题:LRU Cache


deque

http://www.cplusplus.com/reference/deque/deque/

http://c.biancheng.net/view/353.html

#include <deque> 

双向开口的vector,支持vector的所有操作,额外支持头部的增删操作——

void push_front(const T &val);  //将val插入头部
void pop_front();  //删除头部元素


示例: