开发者

C++ deque与vector对比的优缺点

开发者 https://www.devze.com 2023-01-05 10:43 出处:网络 作者: 川入
目录deque容器deque的迭代器deque的成员函数deque容器 deque的相关文档 deque与vector十分的相识。vector是单向开口的连续线性空间(单向扩容),deque则是一种双向开口的连续线性空间(双向扩容)。双向开口:可以在
目录
  • deque容器
  • deque的迭代器
  • deque的成员函数

deque容器

deque的相关文档

deque与vector十分的相识。vector是单向开口的连续线性空间(单向扩容),deque则是一种双向开口的连续线性空间(双向扩容)。双向开口:可以在头尾两端分别做元素的插入和删除操作。区别就在此,vector当然也可以在头尾两端进行操作,但是其头部操作的效率奇差,无法被接受,如:stack与queue的容量适配器就在二者其中,选择deque(当然使用vector也可)。

vector与deque的差异:

  • deque允许于常数时间内对头端进行元素的插入或移除操作。
  • deque没有所谓的容量观念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并连接起来。

C++ deque与vector对比的优缺点

与stack相比deque的优缺点:

优势:

  • 头尾插入删除很方便

劣势:

  • operator[]计算稍显复杂,大量使用,性能下降(下标需要经过计算)。
  • 中间插入删除效率不高(下标需要经过计算,并且需要挪动元素)。
  • 底层角度迭代器会很复杂。

C++ deque与vector对比的优缺点

结论:

  • 头尾的插入删除deque非常适合,相比vector而言,很适合去做stack和queue的默认适配容器。
  • 中间插入删开发者_Go学习除少用deque,可以用:list(因为无需挪动元素)。
  • 随机访问多用vector(因为下标是确定的)。

deque的迭代器

需要注意,deque是连续的空间,但是这只是其逻辑上的,物理上并不是。所以在迭代器上维持其“整体连续”假象的工作,就落在迭代器中的operator++与operator--上了。

首先,连续重要的就是能够指出分段空间在哪里,其次,它必须能够判断自己是否已经处于其所在的存储边缘,如果是,一旦前行或后退时就必须跳跃到下一个或上一个存储空间。

C++ deque与vector对比的优缺点

// __deque_iterator的源码
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator
{
	typedef __deque_iterator<T, T&, T*>             iterator;
	typedef __deque_iterator<T, const T&, const T*> const_iterator;
	static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); }//buffer_sizejs()用于确定缓冲区的大小
	typedef random_Access_iterator_tag iterator_category;
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef size_t size_type; // size_t 是unsigned 类型,通常用来指明数组长度
	typedef ptrdiff_t difference_type; // ptrdiff_t 是 signed 整型,通常用来保存两个指针减法操作的结果
	typedef T** map_pointer;
	typedef __deque_iterator self;
	// 保持与容器的联结,是对某一个缓冲区而言的
	T* cur;       // 此迭代器所指之缓冲区中的现行元素
	T* first;     // 此迭代器所指之缓冲区的头
	T* last;      // 此迭代器所指之缓冲区的尾(含备用空间)
	map_pointer node;    // 指向管控中心
        ...
}
//deque_buf_size()全局函数
inline size_t deque_buf_size(size_t n, size_t sz){
    return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));js
}
//定义:
//1. 如果n不为0,传回n,表示buffer size由使用者自定。
//2. 如果n为0,表示buffer size使用默认值,那么:
//    如果sz不小于 512,返回1。
//    如果sz(元素大小,sizeof(value_type))小于512,传回512/sz。

C++ deque与vector对比的优缺点

void set_node(map_pointer new_node) {
	node = new_node;
	first = *new_node;
	last = first + difference_type(buffer_size());
}
reference operator*() const { return *cur; }
pointer operator->() const { return &(operator*()); }
difference_type operator-(const self& x) const {
	return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur);
}
self& operator++() {
	++cur;        //切换至下个元素
	if (cur == last) {   //如果已达所在缓冲区的尾端,就切换至下一节点(亦即缓冲区)的第一个元素
		set_node(node + 1);
		cur = first;
	}
	return *this;
}
self operator++(int) { //后置式,标准写法
	self tmp = *this;
	++*this;
	return tmp;
}
self& operator--() {
	if (cur == first) {//如果已达所在缓冲区的头端, 就切换至前一节点(亦即缓冲区)的最后一个元素
		set_node(node - 1);
		cur = last;
	}
	--cur; //切换至前一个元素
	return *this;
}
self operator--(int) { //后置式,标准写法
	self tmp = *this;
	--*this;
	return tmp;
}
// 以下实现随机存取。迭代器可以直接跳跃n个距离
self& operator+=(difference_type n) {
	difference_type offset = n + (cur - first);
	if (offset >= 0 &&amhttp://www.devze.comp; offset < difference_type(buffer_size()))
		//标的位置在同一缓冲区内
		cur += n;
	else {
		//标的位置不在同一缓冲区内
		difference_type node_offset =
			offset > 0 ? offset / difference_type(buffer_size()) : -difference_type((-offset - 1) / buffer_size()) - 1;
		// 切换至正确的节点(亦即缓冲区)
		set_node(node + node_offset);
		// 切换至正确的元素
		cur = first + (offset - node_offset * difference_type(buffer_size()));
	}
	return *this;
}
self operator+(difference_type n) const {
    self tmp = *this;
    return tmp += n; //调用operator+=
}
//利用operator+=完成operator-=
self& operator-=(difference_type n) { return *this += -n; }
self operator-(difference_type n) const {
    self tmp = *this;
    return tmp -= n; //调用operator-=
}
//实现随机存取,迭代器可以直接跳跃n个距离
reference operator[] (difference_type n) const { return * (*this + n);)}
bool operator==(const self& x) const { return cur == x.cur; }
bool operator!=(const self& x) const { return !(*this == x); }
bool operator<(const self& x) const {
    return (node == x.node) ? (cur < x.cur) : (node < x.node);
}

deque的成员函数

函数成员函数功能
begin()返回指向容器中第一个元素的迭代器。
end()返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
rbegin()返回指向最后一个元素的迭代器。
rend()返回指向第一个元素所在位置前一个位置的迭代器。
cbegin()和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend()和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin()和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend()和 rend() 功能相同,只不过在其基础上,增加了 consjavascriptt 属性,不能用于修改元素。
size()返回实际元素个数。
max_size()返回容器所能容纳元素个数的最大值。这通常是一个很大的值,一般是 232-1,我们很少会用到这个函数。
resize()改变实际元素的个数。
empty()判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
shrink _to_fit()将内存减少到等于当前元素实际所使用的大小。
at()使用经过边界检查的索引访问元素。
front()返回第一个元素的引用。
back()返回最后一个元素的引用。
assign()用新元素替换原有内容。
push_backandroid()在序列的尾部添加一个元素。
push_front()在序列的头部添加一个元素。
pop_back()移除容器尾部的元素。
pop_front()移除容器头部的元素。
insert()在指定的位置插入一个或多个元素。
erase()移除一个元素或一段元素。
clear()移出所有的元素,容器大小变为 0。
swap()交换两个容器的所有元素。
emplace()在指定的位置直接生成一个元素。
emplace_front()在容器头部生成一个元素。和 push_front() 的区别是,该函数直接在容器头部构造元素,省去了复制移动元素的过程。
emplace_back()在容器尾部生成一个元素。和 push_back() 的区别是,该函数直接在容器尾部构造元素,省去了复制移动元素的过程。

到此这篇关于C++ deque与vector对比的优缺点的文章就介绍到这了,更多相关C++ deque与vector内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号