Iterate over a deque in C++ (Forward and backward direction)
This post will discuss how to iterate over a deque in C++ in the forward and backward directions.
A deque (or Double-ended queue) is a sequence container that can be expanded or contracted on both ends and usually implemented as a dynamic array by most libraries.
1. Using array indices
Since deque is implemented as a dynamic array, we can easily get the element present at any index using the [] operator. The idea is to iterate a queue using a simple for-loop, and for every index, we print the corresponding element.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> #include <queue> #include <algorithm> void print_forward(std::deque<int> const &deque) { for (int i = 0; i < deque.size(); i++) { std::cout << deque[i] << " "; } std::cout << std::endl; } void print_backwards(std::deque<int> const &deque) { for (int i = deque.size() - 1; i >= 0; i--) { std::cout << deque[i] << " "; } std::cout << std::endl; } int main() { std::deque<int> deque = { 1, 2, 3, 4, 5 }; print_forward(deque); print_backwards(deque); return 0; } |
Output:
1 2 3 4 5
5 4 3 2 1
2. Using iterators
We can use deque::cbegin and deque::cend to iterate deque in forward direction and deque::crbegin and deque::crend to iterate deque in backward direction.
Please note that the use of const_iterators is recommended since the iteration is read-only.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> #include <queue> #include <algorithm> void print_forward(std::deque<int> const &deque) { for (auto it = deque.cbegin(); it != deque.cend(); ++it) { std::cout << *it << ' '; } std::cout << std::endl; } void print_backwards(std::deque<int> const &deque) { for (auto it = deque.crbegin(); it != deque.crend(); ++it) { std::cout << *it << ' '; } std::cout << std::endl; } int main() { std::deque<int> deque = { 1, 2, 3, 4, 5 }; print_forward(deque); print_backwards(deque); return 0; } |
Output:
1 2 3 4 5
5 4 3 2 1
3. Using STL std::copy function
Another good alternative is to use the std::copy for copying deque contents to the output stream using the output iterator.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <queue> #include <algorithm> #include <iterator> void print_forward(std::deque<int> const &deque) { std::copy(deque.begin(), deque.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; } void print_backwards(std::deque<int> const &deque) { std::copy(deque.rbegin(), deque.rend(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; } int main() { std::deque<int> deque = { 1, 2, 3, 4, 5 }; print_forward(deque); print_backwards(deque); return 0; } |
Output:
1 2 3 4 5
5 4 3 2 1
With C++17, we can use std::copy with std::experimental::ostream_joiner defined in <experimental/iterator> header.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <queue> #include <algorithm> #include <experimental/iterator> void print_forward(std::deque<int> const &deque) { std::copy(deque.begin(), deque.end(), std::experimental::make_ostream_joiner(std::cout, " ")); std::cout << std::endl; } void print_backwards(std::deque<int> const &deque) { std::copy(deque.rbegin(), deque.rend(), std::experimental::make_ostream_joiner(std::cout, " ")); std::cout << std::endl; } int main() { std::deque<int> deque = { 1, 2, 3, 4, 5 }; print_forward(deque); print_backwards(deque); return 0; } |
Output (g++ -std=c++17):
1 2 3 4 5
4. Using std::for_each algorithm
We can also use the STL algorithm std::for_each, which applies a specified function to every deque element. We can also replace the function call with a lambda in C++11, which is another way of defining an inline, anonymous functor.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> #include <queue> #include <algorithm> /* void fn(int const &i) { std::cout << i << ' '; } void print_forward(std::deque<int> const &deque) { std::for_each(deque.begin(), deque.end(), fn); std::cout << std::endl; } void print_backwards(std::deque<int> const &deque) { std::for_each(deque.rbegin(), deque.rend(), fn); std::cout << std::endl; } */ void print_forward(std::deque<int> const &deque) { std::for_each( deque.begin(), deque.end(), [](int const &i) { std::cout << i << ' '; }); std::cout << std::endl; } void print_backwards(std::deque<int> const &deque) { std::for_each( deque.rbegin(), deque.rend(), [](int const &i) { std::cout << i << ' '; }); std::cout << std::endl; } int main() { std::deque<int> deque = { 1, 2, 3, 4, 5 }; print_forward(deque); print_backwards(deque); return 0; } |
Output:
1 2 3 4 5
5 4 3 2 1
5. Overloading operator>> and operator<<
The idea is to overload the operator>> to print std::deque in the output stream in the forward direction. Similarly, we can overload the operator<< to print std::deque in the backward direction, as shown below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <queue> #include <algorithm> template<typename T> std::ostream &operator>> (std::ostream &out, const std::deque<T> &deque) { for (int i = 0; i < deque.size(); i++) { std::cout << deque[i] << " "; } std::cout << std::endl; return out; } template<typename T> std::ostream &operator<< (std::ostream &out, const std::deque<T> &deque) { for (int i = deque.size() - 1; i >= 0; i--) { out << deque[i] << " "; } out << std::endl; return out; } int main() { std::deque<int> deque = { 1, 2, 3, 4, 5 }; std::cout >> deque; std::cout << deque; return 0; } |
Output:
1 2 3 4 5
5 4 3 2 1
6. Using range-based for-loop
Finally, we can use a range-based for-loop in C++11 to print the deque contents in the forward direction, but it doesn’t support backward iteration.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> #include <queue> #include <algorithm> #include <iterator> void print_forward(std::deque<int> const &deque) { for (int const &i: deque) { std::cout << i << " "; } } int main() { std::deque<int> deque = { 1, 2, 3, 4, 5 }; print_forward(deque); return 0; } |
Output:
1 2 3 4 5
That’s all about iterating over a deque in C++.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)