在 C++ 中使用 deque 容器
-
使用
std::deque
容器处理快速队列插入/删除操作 -
使用
std::push_back
/std::push_front
方法在std::deque
中插入元素 -
使用
push_front
方法的封装函数实现固定大小的队列
本文将演示关于如何在 C++ 中使用 std::deque
容器的多种方法。
使用 std::deque
容器处理快速队列插入/删除操作
std::deque
实现了一个双端队列,在队列的两端提供恒定时间的插入和删除操作。因此,这种数据结构应该在这种操作构成大部分事务的情况下使用。缺点是,std::deque
元素不存储在连续的内存位置,它需要一些额外的操作来处理操作,导致对象大小比 std::vector
容器多。下面的例子显示了一个由 vector
对象构造的字符串 deque
。请注意,建议使用 emplace_back
方法从字符串输入中添加一个新元素。
#include <iostream>
#include <deque>
#include <vector>
using std::cout; using std::deque;
using std::endl; using std::string;
using std::vector;
template<typename T>
void printElements(deque<T> &d)
{
cout << "[ ";
for (const auto &item : d) {
cout << item << ", ";
}
cout << "\b\b ]" << endl;
}
int main()
{
vector<string> vec = {"plie", "flie", "blie", "clie"};;
deque<string> deque2(vec.begin(), vec.end());
deque2.emplace_back("hlie");
printElements(deque2);
exit(EXIT_SUCCESS);
}
输出:
[ plie, flie, blie, clie, hlie ]
使用 std::push_back
/std::push_front
方法在 std::deque
中插入元素
std::deque
有多个内置函数,为元素操作提供丰富的功能。其中最常见的是 push_back
和 push_front
方法,它们将给定的对象作为元素添加到 deque
的相应一侧。请注意,这些函数有其相反的方法来删除元素-pop_back
和 pop_front
。下面的例子展示了上述方法的基本用法。
#include <iostream>
#include <deque>
#include <vector>
using std::cout; using std::deque;
using std::endl; using std::string;
using std::vector;
template<typename T>
void printElements(deque<T> &d)
{
cout << "[ ";
for (const auto &item : d) {
cout << item << ", ";
}
cout << "\b\b ]" << endl;
}
int main()
{
vector<string> vec = {"plie", "flie", "blie", "clie"};;
deque<string> deque2(vec.begin(), vec.end());
string str1("alie");
deque2.push_back(str1);
printElements(deque2);
deque2.push_front(str1);
printElements(deque2);
deque2.pop_back();
deque2.pop_front();
printElements(deque2);
exit(EXIT_SUCCESS);
}
输出:
[ plie, flie, blie, clie, alie ]
[ alie, plie, flie, blie, clie, alie ]
[ plie, flie, blie, clie ]
使用 push_front
方法的封装函数实现固定大小的队列
另一种利用 std::deque
容器的方法,将其作为固定大小的堆栈进行操作,存储 n
个元素,当堆栈满了之后,每插入一个新的元素,就会自动从后面删除一个元素。在这种情况下,我们通过将 push_front
和 pop_back
方法包装成一个单独的函数来实现这个功能。请注意,同样的功能也可以通过使用 std::stack
容器适配器来实现,在这个页面上有详细的描述。
#include <iostream>
#include <deque>
using std::cout; using std::deque;
using std::endl; using std::string;
template<typename T>
void printElements(deque<T> &d)
{
cout << "[ ";
for (const auto &item : d) {
cout << item << ", ";
}
cout << "\b\b ]" << endl;
}
template<typename T>
void pushElement(T &elem, deque<T> &d)
{
d.push_front(elem);
d.pop_back();
}
int main()
{
deque<int> deque1 = {3, 5, 7, 9};
int i1 = 11;
printElements(deque1);
pushElement(i1, deque1);
printElements(deque1);
exit(EXIT_SUCCESS);
}
输出:
[ 3, 5, 7, 9 ]
[ 11, 3, 5, 7 ]
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn