index vs iterator - which would be more efficient?

Question

I was wondering which one of the following ways would be more efficient, if I would like to iterate through a vector. First option:

int i;
for(i = 0; i<vector.size(); i++)
{
cout << vector[i];
}

OR

Second option:

vector<type>::iterator it;
for(it = vector.begin(); it != vector.end(); it++)
{
cout << *it;
}

Using the `vector` as both the type and identifier for your container can be confusing. Specially since it looks like you are using `using std::vector;` or `using namespace std;`. — François Andrieux, Jan 25 '18 at 18:43
If one is more efficient than the other, you should file a compiler bug — Justin, Jan 25 '18 at 18:43
Probably neither by the time the optimizer's done with it. And there is a third option: `for (auto & val: vector) cout < — user4581301, Jan 25 '18 at 18:43
You may want to use `const_iterator` in the second case, if all you want is to read the values and not modify them. — Rishi, Jan 25 '18 at 18:45
In any case, the cost of I/O will dwarf the cost of iterating the container by orders of magnitude. — Igor Tandetnik, Jan 25 '18 at 18:54
"efficient" was not defined, so I'd call @user4581301's solution the most efficient because it's less typing for the programmer, and it's more refactorable with the use of `auto`. In terms of processing time, they're probably all the same. — aj.toulan, Jan 25 '18 at 18:56
"Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%." Knuth — Slava, Jan 25 '18 at 19:26
Use iterators. You should consider calculating end before the loop. You can check yourselves with the compiler and optimization levels. https://godbolt.org/g/aAmGf9 — balki, Jan 25 '18 at 19:28
Possible duplicate of [What's faster, iterating an STL vector with vector::iterator or with at()?](https://stackoverflow.com/questions/776624/whats-faster-iterating-an-stl-vector-with-vectoriterator-or-with-at) — xskxzr, Jan 26 '18 at 06:14

score 2 · Answer 1 · answered Jan 25 '18 at 21:56

The road to hell is paved with good intentions; or in our case premature optimizations. The optimizations done by the compiler should make each of your loops equivalent. Let the compiler work for you and focus on readability and maintainability in this case. As others have pointed out, the std::cout is the bottleneck in your example, not the loop itself.

If you are using C++11 or later the range-based for loops are great for ease of use and readability.

for (const auto & element : myVector)
{
    cout << element;
}

Otherwise if I need to know the position of the element I find it easier to just use the vector::size() and index approach. If I don't care about that, then I almost always use vector<type>::iterator. In my opinion readability is equivalent for either approach and iterators are the more standard approach for all the various STL containers.

score 1 · Accepted Answer · answered Jan 25 '18 at 23:03

One way to verify efficiency is by timing your code, and running an stress test in each aproceedure. To time your code, use <chorno> header file (C++11).

First, create a vector, then add a high number of entries:

#include <vector>

// Create a stressed vector 
std::vector<int> myVector;

for (int i = 0; i < 10000; i++)
    myVector.push_back(i);

For code simplicity, i'll add each of your methods into a function:

Method 1

#include <vector>
#include <iostream>

void methodOne(std::vector<int> vector)
{
    for (int i = 0; i < int(vector.size()); i++)
        std::cout << vector[i] << std::endl; // don't forget to add a separation
}

Method 2

#include <vector>
#include <iostream>

void methodTwo(std::vector<int> vector)
{
    for (auto it = vector.begin(); it != vector.end(); it++)
        std::cout << *it << std::endl; // don't forget to add a separation
}

I also like to sugest a third method, using for each:

Method 3

#include <vector>
#include <iostream>

void methodThree(std::vector<int> vector)
{
    for (auto element : vector)
        std::cout << element << std::endl;
}

Now, include <chrono> header, and run this routine into your main(), and create the Timer class, as indicated in Learn Cpp:

Timer Class

#include <chorno> 

class Timer
{
private: 
    // Type aliases to make accessing nested type easier
    using clock_t = std::chrono::high_resolution_clock;
    using second_t = std::chrono::duration<double, std::ratio<1> >;

std::chrono::time_point<clock_t> m_beg;

public:
    Timer() : m_beg(clock_t::now())
    {
    }

    void reset()
    {
        m_beg = clock_t::now();
    }

    double elapsed() const
    {
        return std::chrono::duration_cast<second_t>(clock_t::now() - m_beg).count();
    }
};

Now, for the main function, just run this code:

Main

#include <vector>
#include <iostream>
#include <chrono>

int main()
{
    //Create a stressed vector
    std::vector<int> myVector;

    for (int i = 0; i < 10000; i++)
        myVector.push_back(i);

    Timer t;
    t.reset();
    t.reset();

    methodOne(myVector);
    auto t1 = t.elapsed();
    t.reset();

    methodTwo(myVector);
    auto t2 = t.elapsed();
    t.reset();

    methodThree(myVector);
    auto t3 = t.elapsed();

    std::cout << "\n";
    std::cout << "Time for Method 1 = " << t1 << " seconds\n";
    std::cout << "Time for Method 2 = " << t2 << " seconds\n";
    std::cout << "Time for Method 3 = " << t3 << " seconds\n";

    return 0;
}

Here is the output of the code for diferent stressed vectors:

Number of entries = 100:

Time for Method 1 = 0.146709 seconds 
Time for Method 2 = 0.176648 seconds  
Time for Method 3 = 0.16161 seconds

Number of entries = 1000

Time for Method 1 = 1.67696 seconds
Time for Method 2 = 1.63569 seconds
Time for Method 3 = 1.64162 seconds

Number of entries = 3000

Time for Method 1 = 5.07384 seconds
Time for Method 2 = 5.01691 seconds
Time for Method 3 = 5.00742 seconds

Number of entries = 7000

Time for Method 1 = 11.8177 seconds
Time for Method 2 = 5.91258 seconds
Time for Method 3 = 3.52884 seconds

Number of entries = 15000

Time for Method 1 = 18.7798 seconds
Time for Method 2 = 8.2039 seconds
Time for Method 3 = 8.25364 seconds

All these tests were executed with Release version, x86.

After looking at these numbers, we can conclude that for few entries, either method works just fine. But as the number of entries increases, Method 1 seems to take more time to complete the same task, although we are speking of ints. Perhaps other variable types could lead to different results.

With that said, I see that Method 2 and proposed Method 3 are more efficient, when dealing with huge loops and vectors.

index vs iterator - which would be more efficient?

2 Answers2