Iterating C++ vector from the end to the beginning
One way is:
for (vector<my_class>::reverse_iterator i = my_vector.rbegin();
i != my_vector.rend(); ++i ) {
}
rbegin()
/rend()
were especially designed for that purpose. (And yes, incrementing a reverse_interator
moves it backward.)
Now, in theory, your method (using begin()
/end()
& --i
) would work, std::vector
's iterator being bidirectional, but remember, end()
isn't the last element — it's one beyond the last element, so you'd have to decrement first, and you are done when you reach begin()
— but you still have to do your processing.
vector<my_class>::iterator i = my_vector.end();
while (i != my_vector.begin())
{
--i;
/*do stuff */
}
UPDATE: I was apparently too aggressive in re-writing the for()
loop into a while()
loop. (The important part is that the --i
is at the beginning.)
Iterate through a C++ Vector using a 'for' loop
Is there any reason I don't see this in C++? Is it bad practice?
No. It is not a bad practice, but the following approach renders your code certain flexibility.
Usually, pre-C++11 the code for iterating over container elements uses iterators, something like:
std::vector<int>::iterator it = vector.begin();
This is because it makes the code more flexible.
All standard library containers support and provide iterators. If at a later point of development you need to switch to another container, then this code does not need to be changed.
Note: Writing code which works with every possible standard library container is not as easy as it might seem to be.
How should I loop over the elements of a C++ container in reverse order?
Well, first of all, about your two snippets: Part of the problem is that they're a bit bug prone for actual newbies - the integer underflow, off-by-one in the comparison, forgetting what i
signifies and using it as a plain index etc. So I would definitely recommend something else. Also, those snippets may invoke vec.size()
many times, which, if the compiler isn't optimizing well enough, would mean a bunch of redundant work.
Option 1: Use iterators
You can reverse-iterate over a container using a pair of iterators (std::rbegin
and std::rend
, and their constant variants) which represent the reversal of the container's order of elements. Here's what that looks like:
for(auto it = std::crbegin(vec); it != std::crend(vec); it++) {
std::cout << *it << '\n';
}
I made this option the first because it's (mostly) compatible with C++98. We didn't have std::rbegin()
and std::crbegin()
then, but we did have an rbegin()
method for std::vector
. std::crbegin()
was introduced in C++11
Option 2: Using C++11 (and later) ranged-for loops
You can massage your container - without making a copy of it (although possibly with some payment of time), so that you can use the result in ranger for loop. The answers to this SO question describe several ways to do so, enabling the following code:
auto reverse_view = /* magic involving vec; and not making a copy */
for(auto x : reverse_view) {
std::cout << *it << '\n';
}
They involve either using an "infrastructural" library (namely Boost), or writing a few lines of code which return an iterator pair in an std::pair
- which is enough for C++ to use in a ranged-for loop.
Option 3: Using ranged-for and C++20's ranges support
Finally, in C++20, this all becomes easier - with ranges support and std::ranges::reverse_view
:
auto reverse_view = std::ranges::reverse_view{vec};
for (const auto& x : reverse_view) {
std::cout << x << '\n';
}
Performance note
Reverse-iterating can in some cases be expensive - because moving backwards, or finding the end of the container, is not always trivial or free. Think of a unidirectional list (where each element comes with a pointer to the next one) - whenever you want to go backwards, you need to traverse the whole list up to your current element to know where the previous element is located. Not all containers are like vectors...
Start iterating vector from the nth element
The if
condition inside the nested loop will never be true, because it conflicts with the loop condition:
for (vector<string>::iterator a = vecA.begin(); a != vecA.end() ; a++) {
// This check ----------------------------------^^^^^^^^^^^^^^^
// guarantees that this will never succeed:
// vvvvvvvvvvvvvvv
if (a == vecA.end()) {
...
}
}
You should rewrite the code like this:
vector<string>::iterator b = vecB.begin();
// Check that vecB has sufficient number of elements before entering the loop.
for (int i = 1 ; i < 2 ; i++) {
for (vector<string>::iterator a = vecA.begin(); a != vecA.end() ; ++a, ++b) {
...
}
// At this point we know for sure that a == vecA.end(),
// because it is a post-condition of the for loop above.
b = std::next(vecB.begin(), 11);
}
The call of ++b
can be moved into the loop header.
Note the use of std::next
: although
b = vecB.begin() + 10;
compiles for vectors, it is not guaranteed for all kinds of containers. Use std::next
instead:
b = std::next(vecB.begin(), 11);
Note: This code makes an assumption that vecB
has at least 11 elements more than vecA
does. This may be OK if you check that assumption before entering the loop. If this assumption is broken, the code would have undefined behavior.
Iterating a vector from end to somewhere (not begin)
Here is a demonstrative program
#include <iostream>
#include <algorithm>
#include <vector>
int main()
{
std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto it = std::find( v.begin(), v.end(), 5 );
if ( it != v.end() )
{
std::vector<int>::reverse_iterator last( it );
for ( auto first = v.rbegin(); first != last; ++first ) std::cout << *first << ' ';
std::cout << std::endl;
}
}
The program output is
9 8 7 6 5
If you do not want to include the found iterator in the range then you can write
std::vector<int>::reverse_iterator last( ++it );
Iterating over a vector in reverse direction
As you've noted, the problem with a condition of i >= 0
when it's unsigned is that the condition is always true. Instead of subtracting 1 when you initialize i
and then again after each iteration, subtract 1 after checking the loop condition:
for (unsigned i = v.size(); i-- > 0; )
I like this style for several reasons:
- Although
i
will wrap around toUINT_MAX
at the end of the loop, it doesn't rely on that behavior — it would work the same if the types were signed. Relying on unsigned wraparound feels like a bit of a hack to me. - It calls
size()
exactly once. - It doesn't use
>=
. Whenever I see that operator in afor
loop, I have to re-read it to make sure there isn't an off-by-one error. - If you change the spacing in the conditional, you can make it use the "goes to" operator.
How to iterate through a vector of vector in C++?
auto iit = it.begin();
doesn't compile because it
is an iterator, not a vector. You should use the overloaded value-of operator to get the vector pointed to by it
.
auto iit = (*it).begin();
Then you can use the iterators as normal.
You can also use range-based for-loops:
for(auto &row : vec) {
for(auto &col : row) {
// do things
}
}
What is the correct way to iterate backward through an std::array or std::vector?
If for some reason iterators don't work, and you must use indexes for some reason:
for (auto k = t.size(); k > 0; )
{
--k;
// The rest of your loop
}
Related Topics
C++: Argument Passing "Passed by Reference"
Win32 Programming Hiding Console Window
Cpp - Valgrind - Invalid Read of Size 8
How to Cin Values into a Vector
How Does C++ Stl Unordered_Map Resolve Collisions
How to Define a Template Function Within a Template Class Outside of the Class Definition
How to Find the Actual Path Found by Bfs
Are Multiple Mutations Within Initializer Lists Undefined Behavior
What Is the Meaning of "Operator Bool() Const"
What's This C++ Syntax That Puts a Brace-Surrounded Block Where an Expression Is Expected
How to Use Createfile, But Force the Handle into a Std::Ofstream
Receiving Chunked Http Data with Winsock
How to Disassemble a Binary Executable in Linux to Get the Assembly Code
Faster Bulk Inserts in SQLite3
Move-Only Version of Std::Function