赞
踩
deque 是 double-ended queue 的缩写,又称双端队列容器。 deque 容器和 vecotr 容器有很多相似之处,比如:
和 vector 不同的是,deque 还擅长在序列头部添加或删除元素,所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是,deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。
当需要向序列两端频繁的添加或删除元素时,应首选 deque 容器。
deque 容器以模板类 deque<T>(T 为存储元素的类型)的形式在 <deque> 头文件中,并位于 std 命名空间中。因此,在使用该容器之前,代码中需要包含下面两行代码:
#include <deque>
using namespace std;
基于 deque 双端队列的特点,该容器包含一些 array、vector 容器都没有的成员函数,如下表所示:
成员函数 | 功能 |
---|---|
begin() | 返回指向容器中第一个元素的迭代器。 |
end() | 返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。 |
rbegin() | 返回指向最后一个元素的迭代器。 |
rend() | 返回指向第一个元素所在位置前一个位置的迭代器。 |
cbegin() | 和 begin() 功能相同,只不过在其基础上增加了 const 属性,不能用于修改元素。 |
cend() | 和 end() 功能相同,只不过在其基础上增加了 const 属性,不能用于修改元素。 |
crbegin() | 和 rbegin() 功能相同,只不过在其基础上增加了 const 属性,不能用于修改元素。 |
crend() | 和 rend() 功能相同,只不过在其基础上增加了 const 属性,不能用于修改元素。 |
size() | 返回实际元素个数。 |
max_size() | 返回容器所能容纳元素个数的最大值。这通常是一个很大的值,比如 2^32-1,我们很少会用到这个函数。 |
resize() | 改变实际元素的个数。 |
empty() | 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。 |
shrink _to_fit() | 将内存减少到等于当前元素实际所使用的大小。 |
at() | 使用经过边界检查的索引访问元素。 |
front() | 返回第一个元素的引用。 |
back() | 返回最后一个元素的引用。 |
assign() | 用新元素替换原有内容。 |
push_back() | 在序列的尾部添加一个元素。 |
push_front() | 在序列的头部添加一个元素。 |
pop_back() | 移除容器尾部的元素。 |
pop_front() | 移除容器头部的元素。 |
insert() | 在指定的位置插入一个或多个元素。 |
erase() | 移除一个元素或一段元素。 |
clear() | 移出所有的元素,容器大小变为 0。 |
swap() | 交换两个容器的所有元素。 |
emplace() | 在指定的位置直接生成一个元素。 |
emplace_front() | 在容器头部生成一个元素。和 push_front() 的区别是,该函数直接在容器头部构造元素,省去了复制移动元素的过程。 |
emplace_back() | 在容器尾部生成一个元素。和 push_back() 的区别是,该函数直接在容器尾部构造元素,省去了复制移动元素的过程。 |
和 vector 相比,额外增加了实现在容器头部添加和删除元素的成员函数,同时删除了 capacity()、reserve() 和 data() 成员函数。
和 array、vector 相同,C++ 11 标准库新增的 begin() 和 end() 这 2 个全局函数也适用于 deque 容器。这 2 个函数的操作对象既可以是容器,也可以是普通数组。当操作对象是容器时,它和容器包含的 begin() 和 end() 成员函数的功能完全相同;如果操作对象是普通数组,则 begin() 函数返回的是指向数组第一个元素的指针,同样 end() 返回指向数组中最后一个元素之后一个位置的指针(注意不是最后一个元素)。
deque 容器还有一个std::swap(x , y)
非成员函数(其中 x 和 y 是存储相同类型元素的 deque 容器),它和 swap() 成员函数的功能完全相同,仅使用语法上有差异。
创建 deque 容器,根据不同的实际场景,可选择使用如下几种方式。
std::deque<int> d;
和空 array 容器不同,空的 deque 容器在创建之后可以做添加或删除元素的操作,因此这种简单创建 deque 容器的方式比较常见。
std::deque<int> d(10);
此行代码创建一个具有 10 个元素(默认都为 0)的 deque 容器。
std::deque<int> d(10, 5)
如此就创建了一个包含 10 个元素(值都为 5)的 deque 容器。
std::deque<int> d1(5);
std::deque<int> d2(d1);
注意,采用此方式,必须保证新旧容器存储的元素类型一致。
// 拷贝普通数组,创建 deque 容器
int a[] = { 1,2,3,4,5 };
std::deque<int> d(a, a + 5);
// 适用于所有类型的容器
std::array<int, 5> arr{ 11,12,13,14,15 };
std::deque<int> d(arr.begin() + 2, arr.end()); // 拷贝 arr 容器中的{13,14,15}
deque 容器迭代器的类型为随机访问迭代器,deque 模板类提供了下表所示这些成员函数,通过调用这些函数,可以获得表示不同含义的随机访问迭代器。
成员函数 | 功能 |
---|---|
begin() | 返回指向容器中第一个元素的正向迭代器;如果是 const 类型容器,在该函数返回的是常量正向迭代器。 |
end() | 返回指向容器最后一个元素之后一个位置的正向迭代器;如果是 const 类型容器,在该函数返回的是常量正向迭代器。此函数通常和 begin() 搭配使用。 |
rbegin() | 返回指向最后一个元素的反向迭代器;如果是 const 类型容器,在该函数返回的是常量反向迭代器。 |
rend() | 返回指向第一个元素之前一个位置的反向迭代器。如果是 const 类型容器,在该函数返回的是常量反向迭代器。此函数通常和 rbegin() 搭配使用。 |
cbegin() | 和 begin() 功能类似,只不过其返回的迭代器类型为常量正向迭代器,不能用于修改元素。 |
cend() | 和 end() 功能相同,只不过其返回的迭代器类型为常量正向迭代器,不能用于修改元素。 |
crbegin() | 和 rbegin() 功能相同,只不过其返回的迭代器类型为常量反向迭代器,不能用于修改元素。 |
crend() | 和 rend() 功能相同,只不过其返回的迭代器类型为常量反向迭代器,不能用于修改元素。 |
C++ 11 新添加的 begin() 和 end() 全局函数也同样适用于 deque 容器。即当操作对象为 deque 容器时,其功能分别和上表中的 begin()、end() 成员函数相同。
同样的,这些成员函数通常也是成对使用的,即 begin()/end()、rbegin()/rend()、cbegin()/cend()、crbegin()/crend() 各自成对搭配使用。其中,begin()/end() 和 cbegin/cend() 的功能是类似的,同样 rbegin()/rend() 和 crbegin()/crend() 的功能是类似的。
值得一提的是,以上函数在实际使用时,其返回值类型都可以使用 auto 关键字代替,编译器可以自行判断出该迭代器的类型。
deque 容器迭代器常用来遍历容器中存储的各个元素。
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d{1,2,3,4,5};
// 从容器首元素,遍历至最后一个元素
for (auto i = d.begin(); i < d.end(); i++) {
cout << *i << " ";
}
return 0;
}
运行结果为:
1 2 3 4 5
前面提到,STL 还提供有全局的 begin() 和 end() 函数,当操作对象为容器时,它们的功能是上面的 begin()/end() 成员函数一样。例如,将上面程序中的第 8~10 行代码可以用如下代码替换:
for (auto i = begin(d); i < end(d); i++) {
cout << *i << " ";
}
重新编译运行程序,会发现输出结果和上面一致。
举个例子:
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d{1,2,3,4,5}; auto first = d.cbegin(); auto end = d.cend(); // 常量迭代器不能用来修改容器中的元素值 //*(first + 1) = 6; // 尝试修改容器中元素 2 的值 //*(end - 1) = 10; // 尝试修改容器中元素 5 的值 // 常量迭代器可以用来遍历容器、访问容器中的元素 while(first<end){ cout << *first << " "; ++first; } return 0; }
运行结果:
1 2 3 4 5
程序中,由于 first 和 end 都是常量迭代器,因此第 10、11 行修改容器内元素值的操作都是非法的。
需要注意的是,在使用反向迭代器进行
++
或--
运算时,++
指的是迭代器向左移动一位,--
指的是迭代器向右移动一位,即这两个运算符的功能也“互换”了。
反向迭代器用于以逆序的方式遍历容器中的元素。例如:
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d{1,2,3,4,5};
for (auto i = d.rbegin(); i < d.rend(); i++) {
cout << *i << " ";
}
return 0;
}
运行结果为:
5 4 3 2 1
首先需要注意的一点是,迭代器的功能是遍历容器,在遍历的同时可以访问(甚至修改)容器中的元素,但迭代器不能用来初始化空的 deque 容器。
例如,如下代码中注释部分是错误的用法:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> values;
auto first = values.begin();
//*first = 1;
return 0;
}
对于空的 deque 容器来说,可以通过 push_back()、push_front() 或者 resize() 成员函数实现向(空)deque 容器中添加元素。
除此之外,当向 deque 容器添加元素时,deque 容器会申请更多的内存空间,同时其包含的所有元素可能会被复制或移动到新的内存地址(原来占用的内存会释放),这会导致之前创建的迭代器失效。
举个例子:
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d;
d.push_back(1);
auto first = d.begin();
cout << *first << endl;
// 添加元素,会导致 first 失效
d.push_back(1);
cout << *first << endl;
return 0;
}
程序中第 12 行代码,会导致程序运行崩溃,其原因就在于在创建 first 迭代器之后,deque 容器做了添加元素的操作,导致 first 失效。
在对容器做添加元素的操作之后,如果仍需要使用之前以创建好的迭代器,为了保险起见,一定要重新生成。
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d{ 1,2,3,4 };
cout << d[1] << endl;
// 修改指定下标位置处的元素
d[1] = 5;
cout << d[1] << endl;
return 0;
}
运行结果为:
2
5
可以看到,容器名[n]
的这种方式,不仅可以访问容器中的元素,还可以对其进行修改。但需要注意的是,使用此方法需确保下标 n 的值不会超过容器中存储元素的个数,否则会发生越界访问的错误。
如果想有效地避免越界访问,可以使用 deque 模板类提供的 at() 成员函数,由于该函数会返回容器中指定位置处元素的引用形式,因此利用该函数的返回值,既可以访问指定位置处的元素,如果需要还可以对其进行修改。
不仅如此,at() 成员函数会自行判定访问位置是否越界,如果越界则抛出std::out_of_range
异常。例如:
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d{ 1,2,3,4 };
cout << d.at(1) << endl;
d.at(1) = 5;
cout << d.at(1) << endl;
// 下面这条语句会抛出 out_of_range 异常
//cout << d.at(10) << endl;
return 0;
}
运行结果为:
2
5
我们可能会有这样一个疑问,即为什么 deque 容器在重载 [] 运算符时,没有实现边界检查的功能呢?答案很简单:因为性能。如果每次访问元素,都去检查索引值,无疑会产生很多开销。当不存在越界访问的可能时,就能避免这种开销。
举个例子:
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d{ 1,2,3,4,5 }; cout << "deque 首元素为:" << d.front() << endl; cout << "deque 尾元素为:" << d.back() << endl; // 修改首元素 d.front() = 10; cout << "deque 新的首元素为:" << d.front() << endl; // 修改尾元素 d.back() = 20; cout << "deque 新的尾元素为:" << d.back() << endl; return 0; }
运行结果为:
deque 首元素为:1
deque 尾元素为:5
deque 新的首元素为:10
deque 新的尾元素为:20
注意,和 vector 容器不同,deque 容器没有提供 data() 成员函数,同时 deque 容器在存储元素时,也无法保证其会将元素存储在连续的内存空间中,因此尝试使用指针去访问 deque 容器中指定位置处的元素,是非常危险的。
另外,结合 deque 模板类中和迭代器相关的成员函数,可以实现遍历 deque 容器中指定区域元素的方法。例如:
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d{ 1,2,3,4,5 }; // 从元素 2 开始遍历 auto first = d.begin() + 1; // 遍历至 5 结束(不包括 5) auto end = d.end() - 1; while (first < end) { cout << *first << " "; ++first; } return 0; }
运行结果为:
2 3 4
deque 容器中,无论是添加元素还是删除元素,都只能借助 deque 模板类提供的成员函数。下表中罗列的是所有和添加或删除容器内元素相关的 deque 模板类中的成员函数。
成员函数 | 功能 |
---|---|
push_back() | 在容器现有元素的尾部添加一个元素,和 emplace_back() 不同,该函数添加新元素的过程是,先构造元素,然后再将该元素移动或复制到容器的尾部。 |
pop_back() | 移除容器尾部的一个元素。 |
push_front() | 在容器现有元素的头部添加一个元素,和 emplace_back() 不同,该函数添加新元素的过程是,先构造元素,然后再将该元素移动或复制到容器的头部。 |
pop_front() | 移除容器尾部的一个元素。 |
emplace_back() | C++11 新添加的成员函数,其功能是在容器尾部生成一个元素。和 push_back() 不同,该函数直接在容器头部构造元素,省去了复制或移动元素的过程。 |
emplace_front() | C++ 11 新添加的成员函数,其功能是在容器头部生成一个元素。和 push_front() 不同,该函数直接在容器头部构造元素,省去了复制或移动元素的过程。 |
insert() | 在指定的位置直接生成一个元素。和 emplace() 不同的是,该函数添加新元素的过程是,先构造元素,然后再将该元素移动或复制到容器的指定位置。 |
emplace() | C++ 11 新添加的成员函数,其功能是 insert() 相同,即在指定的位置直接生成一个元素。和 insert() 不同的是,emplace() 直接在容器指定位置构造元素,省去了复制或移动元素的过程。 |
erase() | 移除一个元素或某一区域内的多个元素。 |
clear() | 删除容器中所有的元素。 |
在实际应用中,常用 emplace()、emplace_front() 和 emplace_back() 分别代替 insert()、push_front() 和 push_back()。
以上这些成员函数中,除了 insert() 函数的语法格式比较多,其他函数都只有一种用法(erase() 有 2 种语法格式),下面这段程序演示了它们的具体用法:
#include <deque> #include <iostream> using namespace std; int main() { deque<int> d; // 调用push_back()向容器尾部添加数据。 d.push_back(2); // {2} // 调用pop_back()移除容器尾部的一个数据。 d.pop_back(); // {} // 调用push_front()向容器头部添加数据。 d.push_front(2); // {2} // 调用pop_front()移除容器头部的一个数据。 d.pop_front(); // {} // 调用 emplace 系列函数,向容器中直接生成数据。 d.emplace_back(2); // {2} d.emplace_front(3); // {3,2} // emplace() 需要 2 个参数,第一个为指定插入位置的迭代器,第二个是插入的值。 d.emplace(d.begin() + 1, 4); // {3,4,2} for (auto i : d) { cout << i << " "; } // erase()可以接受一个迭代器表示要删除元素所在位置 // 也可以接受 2 个迭代器,表示要删除元素所在的区域。 d.erase(d.begin()); // {4,2} d.erase(d.begin(), d.end()); // {},等同于 d.clear() return 0; }
运行结果为:
3 4 2
这里重点讲一下 insert() 函数的用法。insert() 函数的功能是在 deque 容器的指定位置插入一个或多个元素。该函数的语法格式有多种,如下表所示:
语法格式 | 功能 |
---|---|
iterator insert(pos,elem) | 在迭代器 pos 指定的位置之前插入一个新元素 elem,并返回表示新插入元素位置的迭代器。 |
iterator insert(pos,n,elem) | 在迭代器 pos 指定的位置之前插入 n 个元素 elem,并返回表示第一个新插入元素位置的迭代器。 |
iterator insert(pos,first,last) | 在迭代器 pos 指定的位置之前,插入其他容器(不仅限于vector)中位于 [first,last) 区域的所有元素,并返回表示第一个新插入元素位置的迭代器。 |
iterator insert(pos,initlist) | 在迭代器 pos 指定的位置之前,插入初始化列表(用大括号{}括起来的多个元素,中间有逗号隔开)中所有的元素,并返回表示第一个新插入元素位置的迭代器。 |
下面的程序演示了 insert() 函数的这几种用法:
#include <iostream> #include <deque> #include <array> using namespace std; int main() { std::deque<int> d{ 1,2 }; // 第一种格式用法 d.insert(d.begin() + 1, 3); // {1,3,2} // 第二种格式用法 d.insert(d.end(), 2, 5); // {1,3,2,5,5} // 第三种格式用法 std::array<int, 3>test{ 7,8,9 }; d.insert(d.end(), test.begin(), test.end()); // {1,3,2,5,5,7,8,9} // 第四种格式用法 d.insert(d.end(), { 10,11 }); // {1,3,2,5,5,7,8,9,10,11} for (int i = 0; i < d.size(); i++) { cout << d[i] << " "; } return 0; }
运行结果为:
1,3,2,5,5,7,8,9,10,11
有关 emplace()、emplace_front() 和 emplace_back() 分别和 insert()、push_front() 和 push_back() 在运行效率上的对比,可以通过下面的程序体现出来:
#include <deque> #include <iostream> using namespace std; class testDemo { public: testDemo(int num) :num(num) { std::cout << "调用构造函数" << endl; } testDemo(const testDemo& other) :num(other.num) { std::cout << "调用拷贝构造函数" << endl; } testDemo(testDemo&& other) :num(other.num) { std::cout << "调用移动构造函数" << endl; } testDemo& operator=(const testDemo& other); private: int num; }; testDemo& testDemo::operator=(const testDemo& other) { this->num = other.num; return *this; } int main() { // emplace和insert cout << "emplace:" << endl; std::deque<testDemo> demo1; demo1.emplace(demo1.begin(), 2); cout << "insert:" << endl; std::deque<testDemo> demo2; demo2.insert(demo2.begin(), 2); // emplace_front和push_front cout << "emplace_front:" << endl; std::deque<testDemo> demo3; demo3.emplace_front(2); cout << "push_front:" << endl; std::deque<testDemo> demo4; demo4.push_front(2); // emplace_back()和push_back() cout << "emplace_back:" << endl; std::deque<testDemo> demo5; demo5.emplace_back(2); cout << "push_back:" << endl; std::deque<testDemo> demo6; demo6.push_back(2); return 0; }
运行结果为:
emplace:
调用构造函数
insert:
调用构造函数
调用移动构造函数
emplace_front:
调用构造函数
push_front:
调用构造函数
调用移动构造函数
emplace_back:
调用构造函数
push_back:
调用构造函数
调用移动构造函数
可以看到,相比和它同功能的函数,emplace 系列函数都只调用了构造函数,而没有调用移动构造函数,这无疑提高了代码的运行效率。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。