mercredi 2 mars 2016

C++ Time Taken in Map Access and Iteration

I was profiling code using gprof and I observed that -> operator of consuming a significant amount of time.

This is sample definition of map.

map<int, vector<int> > myMap;

I have an iterator,

map<int, vector<int> >::iterator it;

I frequently run loops like:

for(it = myMap.begin(), it != myMap.end(); it++) {
   //Do stuff
}

This is the data from profiling

Function:
std::_Rb_tree_iterator<std::pair<int const, std::vector<ClassType*, std::allocator<ClassType*> > > >::operator->() const
Time Consumed:
20.18%
Number of Times function is called:
15285739415

Function:
std::_Rb_tree_iterator<std::pair<int const, std::vector<ClassType*, std::allocator<ClassType*> > > >::operator++(int)
Time Consumed:
2.90%
Number of Times function is called:
3825378111

From my understanding, ++ operator calculates next element which taken O(log(n)) and -> gives the element which should take O(1) time. Even though -> operator is called more than ++ operator, I think it should not consume that amount of time. Shouldn't ++ consume more time than -> operator?

Aucun commentaire:

Enregistrer un commentaire