Ways to iterate over Vector in C++ STL

In this article, we have explored different ways to iterate over Vector in C++ STL. These include techniques like indexing, iterators, range based for loop and much more.

Vectors are sequence conatiners similar to dynamic arrays. Vectors have ability to resize themselves. The dat in vectors are stored in contigous fashion. Hence the data can not only be accessed through iterators and but also through indices.

When we write code in C++ we are in a constant dilemma in which way we should iterate over a collection. Obviously it depends on the type of data structure we are trying to iterte over. But, most of them anyway follow the same structure. Now we will see various ways to iterate over a vector in C++ STL. Then we will try to print out the contents of array using the ways that we explore.

The Different Ways to iterate over Vector in C++ STL are:

• Iterate using Indexing
• Using Iterators
• Using Range Based for loop
• Using std::for_each

Iterate using Indexing

Using indexing is the textbook way for iterating over a vector using normal loops. It allows us to know the exact index position of the elements that we are accessing. The for loop can be used to access the vector from one postion to a latter position.

Pseudocode

1. initialize and populate a vector
2. loop from i = 0 to size of vector
3. do print element of vector at index i

Complexity

• Some people might hesistate to use this code due to calling of vector::size on each iteration however it has constant time complexity hence it is nothing to wory about
• Worst case time complexity: Θ(n)
• Average case time complexity: Θ(n)
• Best case time complexity: Θ(n)
• Space complexity: Θ(1)

Implementation

#include <iostream>
#include <vector>

using namespace std;

int main(){
    vector<int> v = {7, 5, 2, 9, 4, 1};
    for(int i = 0 ; i < v.size(); i++){
        cout << v[i] << " " ;
    }
}

Applications

• This method can be helpful when you need to use the index (eg. accessing next/previous element, using the index iside the loop)
• This method is also great when you need a stride other than 1 this can be changed by replacing updation part of for loop with something like i += 2 for accessing only alternate elements.

Using Iterators

Iterators are used to iterate over a collection of data. When we think of iterators we use usually think of collection of data and ways to iterate over it. Using vector::begin() and vector::end() allow us to access pointers to start and end of vector respectively. Also vector::rbegin() and vector::rend() can also be used in similar fashion.

Pseudocode

1. initialize and populate a vector
2. loop from iter = vector beginning to vector end
3. inside the loop you can access individual elements by dereferencing iter

Complexity

• vector::begin() and vector::end() have complexity of Θ(1) hence they do not affect the time complexity.
• Worst case time complexity: Θ(n)
• Average case time complexity: Θ(n)
• Best case time complexity: Θ(n)
• Space complexity: Θ(1)

Implementation

#include <iostream>
#include <vector>

using namespace std;

int main(){
    vector<int> v = {7, 5, 2, 9, 4, 1};
    // here I used auto to declare it instead of std::vector::iterator
    // to make the code easy to read and understand
    for(auto it = v.begin(); it != v.end(); it++)
        cout << *it << " ";
}

Applications

• Similar to usind indeces here also we can control the stride in a similar fashion to what was discussed earlier.
• Using iterators gives us a significant advantage: it allows abstraction. It will enable us to write generic code that can be used with various containers and not necessarily be limited to only vectors, making our code more reusable.

Using Range Based for loop

Range-based for loops were introduced in C++11 and executes for loop over a range. Range-based for loops help to make our code more readable. It provides an elegant and clean way to access the elements. Once you look at the code, it might look like sorcery to you, but under the hood, it is using the logic that we saw above.

Pseudocode

for ( declaration : range )
loop expression

• declaration is a variable of the same type as data type of the vector that is assigned values
• range is the expression that shows the range the for loop is to be run over
• loop expression here refers to the loop body

Complexity

• Worst case time complexity: Θ(n)
• Average case time complexity: Θ(n)
• Best case time complexity: Θ(n)
• Space complexity: Θ(1)

Implementations

#include <vector>
#include <iostream>

using namespace std;

int main(){
    vector<int> v = {7, 5, 2, 9, 4, 1};
    for(int i : v){
        cout << i << " " ;
    }
}

Applications

• If you dont need to access the index and dont need to iterate over the vector in a particular order. RAnge based for loops make our code easier to understand
• when we need to iterate the whole vector these help us write less verbose.

Using std::for_each

Apart from the generic looping algorithms namely for loop, while loops and do while loop. for_each allows us to iterate over an array or collection and execute an block of statements over each element of the collection.

Pseudocode

1. Initialise and populate a vector
2. for_each( begin, end, statements)

begin signifies the start of the range
end signifies end of range
statements refer to functions to be performed on each element

Complexity

• Worst case time complexity: Θ(nx)
• Average case time complexity: Θ(nx)
• Best case time complexity: Θ(nx)
• Space complexity: Θ(ny)
• Here x is best/average/worst case time complexity of statements
• Here y is space complexity of the statements

Implementations

For single code use markdown as follows:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    vector<int> v = {7, 5, 2, 9, 4, 1};
    for_each(v.begin(), v.end(), [](int const& val){
        cout << val << " " ;
    });

    return 0;
}

Applications

• It is generic and hence not limited to one type of container hence swapping the type of container it iterates on is painless
• Allows us to apply side-effects on function object.