Requirements:

1. container which sorts itself based on numerically comparing the keys (e.g. std::map)
2. check existence of key based on float tolerance (e.g. map.find() and use custom comparator )
3. and the tricky one: the float tolerance used by the comparator may be changed by the user at runtime!

The first 2 can be accomplished using a map with a custom comparator:

struct floatCompare : public std::binary_function<float,float,bool>
{
    bool operator()( const float &left, const float &right ) const
    {
        return (fabs(left - right) > 1e-3) && (left < right);
    }
};

typedef std::map< float, float, floatCompare > floatMap;

Using this implementation, floatMap.find( 15.0001 ) will find 15.0 in the map.

However, let's say the user doesn't want a float tolerance of 1e-3. What is the easiest way to make this comparator function use a variable tolerance at runtime? I don't mind re-creating and re-sorting the map based on the new comparator each time epsilon is updated.

Other posts on modification after initialization here and using floats as keys here didn't provide a complete solution.

You can't change the ordering of the map after it's created (and you should just use plain old operator< even for the floating point type here), and you can't even use a "tolerant" comparison operator as that may vioate the required strict-weak-ordering for map to maintain its state.

However you can do the tolerant search with lower_bound and upper_bound. The gist is that you would create a wrapper function much like equal_range that does a lower_bound for "value - tolerance" and then an upper_bound for "value + tolerance" and see if it creates a non-empty range of values that match the criteria.