Performance issue in find function.

[Febbe]

flat_map/implementation/flat_map

Lines 1231 to 1248 in 428ee6f

	__key_iter_t __key_find(const _K & __k)
	{
	auto __it = __key_lower_bound(__k);
	if (__it != __c.keys.end() &&
	(__compare(*__it, __k) || __compare(__k, *__it)))
	__it = __c.keys.end();
	return __it;
	}
	template<typename _K>
	__key_const_iter_t __key_find(const _K & __k) const
	{
	auto __it = __key_lower_bound(__k);
	if (__it != __c.keys.end() &&
	(__compare(*__it, __k) || __compare(__k, *__it)))
	__it = __c.keys.end();
	return __it;
	}
	};

I've made a benchmark of a manual flat map via a vector of pairs vs your implementation and discovered, that searching for an element is significantly slower. The cause of this is, that find checks (__compare(*__it, __k), __key_lower_bound already checked that. So you are checking it twice. Both gcc and clang doesn't found this possible implementation.