Speeding up iterators

[wildfire99]

I've got a program that is storing gobs of pointers to objects, and I want to be able to check them in a linear fashion pretty fast.

To that end, I set up a trial using both vectors and multimaps to test lookup and sequential access speed. The issue I'm running into is iterator speed, actually a huge slowdown when iterators are incremented. I'm using MSVC 2005.

Here's some sample code. It's a simple function that does nothing more complex than insert a pointer so that all records in the vector are in sequential ID order.

void insertv( ObjectPointer* p, std::vector<ObjectPointer*>& vec )
{
	int x, count = (int) vec.size();

	for (x = 0; x < count; x++)
	{
		if ( p->idnumber < vec[x]->idnumber )
		{
			vec.insert( vec.begin() + x, p );
			return;
		}
	}

	vec.push_back(p); //id is largest so push to back
}

This takes a freaking long time once it gets over 50,000 entries in the vector. But it's not the linear search eating up time, not even the insertion, it's adding x to the vector iterator!

If I change the insert to remove the x, the code speeds up by a factor of more than 10.

 vec.insert( vec.begin(), p ); //more than 10x faster than vec.begin + x

This is despite the fact that the vector now (presumably) has to bump over all of its contents every time it inserts.

You might ask why I don't just use a map? Same problem but later in the code. Incrementing the map's iterator to step through all records is over four times slower than simply using the array operator for the vector ( e.g. vector[x] ).

Stepping through the actual code shows the iterator increment is nothing more than a simple internal pointer increment, so why is it so slow? How can I fix this so incrementing an iterator is reasonably fast?

I did check by defining _SECURE_SCL to zero to ensure that was off... makes no difference. All times were from the optimized release build, so there should be no debug oddities.