In the Visual Studio 2015 standard library, the implementation of std::map::find is unnecessarily slow.

The underlying reason seems to be similar to that for bug #2 - using operations on a generic tree class that doesn't take advantage of the restrictions places on std::map - that entry keys are unique.

The issue in detail: std::map::find() calls std::_Tree::lower_bound, which calls _Lbound, which looks like

_Nodeptr _Lbound(const _Other& _Keyval) const
{	// find leftmost node not less than _Keyval
	_Nodeptr _Pnode = _Root();
	_Nodeptr _Wherenode = this->_Myhead();	// end() if search fails

	while (!this->_Isnil(_Pnode))
		if (_Compare(this->_Key(_Pnode), _Keyval))
			_Pnode = this->_Right(_Pnode);	// descend right subtree
		else
		{	// _Pnode not less than _Keyval, remember it
			_Wherenode = _Pnode;
			_Pnode = this->_Left(_Pnode);	// descend left subtree
		}

	return (_Wherenode);	// return best remembered candidate
}

Which is a traversal down a binary tree. The issue is that the traversal doesn't stop when an interior node has a key that is the same as the target key. This is presumably because if you allow multiple entries with the same key, you need to keep traversing to get the leftmost of them. However since we know that entry keys are unique in std::map, the traversal could stop as soon as it traverses to an interior node with matching key.

Proposed fix

The fix is to check the interior nodes keys for equality with the target key, and return from the traversal immediately in that case.

_Nodeptr _Lbound(const _Other& _Keyval) const
{	// find leftmost node not less than _Keyval
	_Nodeptr _Pnode = _Root();
	_Nodeptr _Wherenode = this->_Myhead();	// end() if search fails

	while(!this->_Isnil(_Pnode))
		if(_Compare(this->_Key(_Pnode), _Keyval))
			_Pnode = this->_Right(_Pnode);	// descend right subtree
		else
		{	
			// NEW: else node >= keyval
			if(!_Compare(_Keyval, this->_Key(_Pnode))) // NEW: if !(keyval < node):
				return _Pnode; // NEW: then keyval == node, so return it
				
			// _Pnode not less than _Keyval, remember it
			_Wherenode = _Pnode;
			_Pnode = this->_Left(_Pnode);	// descend left subtree
		}

	return (_Wherenode);	// return best remembered candidate
}

This doesn't change the asymptotic time complexity of the find call, it's still O(log(n)). But it does somewhat decrease the number of nodes that need to be traversed on average.

It does require additional key comparisons, which could result in a net slowdown in some cases, but the cost of unneeded memory accesses are likely to be higher than the cost of the additional comparisons in most cases, I believe, especially as the number of entries in the map increases and cache misses become more common.

Results with the proposed fix

I implemented the proposed fix above in a class copied from std::map, called modified_std::map.

Doing 1M lookups in a map and modified map with 2^16 unique int keys:

modified_std::map find: 0.045002 s, num_found: 1000000
std::map find:          0.052951 s, num_found: 1000000

The modified map find method is approximately 15% faster. This isn't a huge amount, but is worth optimising/fixing, for such a commonly-used operation!

There is a similar issue in _Eqrange.