CODEWITHSUNDEEP
c++
Nikita Zaliven
Nikita Zaliven

Reputation: 21

index vs iterator - which would be more efficient?

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;
}

Upvotes: 1

Views: 153

Answers (2)

JeanLColombo
JeanLColombo

Reputation: 160

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.

Upvotes: 1

Justin Randall
Justin Randall

Reputation: 2278

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.

Upvotes: 2

Related Questions