c++标准库顺序容器vector,deque,list

时间:2022-02-11 17:38:43

顺序容器

Vector

deque

List

内存形式

类似加强版的队列

分配一块连续的内存,元素被顺序存储当数值内存不够时,vector会重新申请一块足够大的连续内存,把原来的数据拷贝到新的内存里面当向vector插入或者删除一个元素时,需要复制移动待插入元素右边的所有元素

双向队列

分配内存的时候,使用了MAP的结构和方法。化整为零,分配了许多小的连续空间deque两端添加、删除元素十分方便同时支持随机访问

 

 

 

 

双向连接表

在内存中不一定连续list因为不用考虑内存的连续,因此新增开销比vector小。list只能通过指针访问元素,随机访问元素的效率特别低

特点

支持快速随机访问

双端队列

 

支持快速插入/删除

容器对象初始化

通用

C<T> c;C c(c2);C c(b,e);C c(n,t);C c(n);

迭代器和迭代器范围

通用

*iteriter->mem++iter/iter++--iter/iter--iter1 ==

iter2/iter1 !=iter2

特有

iter + n

iter - n

iter1 +=iter2

iter1 -=iter2

iter1 - iter2

>, >=,<, <=

 

容器操作

通用

迭代器:c.begin()c.end()c.rbegin()c.rend()

访问元素:c.push_back(t)c.push_front(t)c.insert(p,t)c.insert(p,n,t)c.insert(p,b,e)

容器大小:c.size()c.max_size()c.empty()c.resize(n)c.resize(n,t)

访问元素:c.back()c.front()

删除元素:c.erase(p)c.erase(b,e)c.clear()c.pop_back()

赋值:c1 = c2c1.swap(c2)c.assign(b,e)c.assign(n,t)

特有

访问元素:c[n]c.at(n)

删除元素:c.pop_front()

容器的选择

通常来说,除非找到选择使用其他容器的更好理由,否则 vector 容器都是最佳选择。

1. 如果程序要求随机访问元素,则应使用 vector 或 deque 容器。

2. 如果程序必须在容器的中间位置插入或删除元素,则应采用 list 容器。

3. 如果程序不是在容器的中间位置,而是在容器首部或尾部插入或删除元

素,则应采用 deque 容器。

4. 如果只需在读取输入时在容器的中间位置插入元素,然后需要随机访问元

素,则可考虑在输入时将元素读入到一个 list 容器,接着对此容器重新

排序,使其适合顺序访问,然后将排序后的 list 容器复制到一个 vector容器。