Home > C++ > Effective iteration over STL container.

Effective iteration over STL container.

Today I had a chance to recall a little bit, what is STL and how should it be used effectively.
Let’s take a brief look of the next code in C++, which makes iteration over STL’s map:

std::map<int, std::string> 		myMap;
std::map<int, std::string>::iterator	myIter;

for (myIter = myMap.begin(); myIter != myMap.end(); myIter++) //bad performance
{
	std::cout << *myIter << std::endl;
}

Can you see the performance problem? Actually there are 2:

1) The loop checks the stop condition every iteration, i.e. compares iterator to the value returned by “myMap.end()”.
The “end” function is called in every iteration, even though the return value doesn’t change during the loop.

2) Using postfix operator++ is more expensive then prefix operator, because postfix operator must make a local copy of the object. Object is created by the copy constructor, and if the object is “heavy” enough, this additional action could harm the performance. Lets compare implementations of both operators:

iterator& operator++()
{
	_Ptr = _Acc::_Next(_Ptr);
	return (*this);
}

iterator operator++(int)
{
	iterator _Tmp = *this; // Calling the copy constructor
	++*this;
	return (_Tmp);
}

Hence, we should do very easy changes, and the improved code looks like this:

std::map<int, std::string> 		myMap;
std::map<int, std::string>::iterator	myIter, endIter = myMap.end() ;

for (myIter = myMap.begin(); myIter != endIter; ++myIter) //good  performance
{
	std::cout << *myIter << std::endl;
}

Remark:
Many good advices about effective using STL library are described in a book “Effective STL” by Scott Meyers.

Categories: C++ Tags: ,
  1. No comments yet.
  1. No trackbacks yet.