Finding "best matching key" for a given key in a sorted STL container

I would use equal_range too for such a thing.

If you are using sort() every time on your vector it might be better to use a map (or set), as that's always sorted automatically, and use the member equal_range

But that depends on the the amount of inserts / queries / amount of data. (although for something that always needs to be sorted when I query, a map would be my first choice, and I'd only use a vector if there was a very good reason)

I would use set::lower_bound to find the matching or greater value, then decrement the iterator to check the next lower value. You should use std::set rather than std::map since your key is embedded in the object - you'll need to provide a functor that compares the timestamp members.

struct TimestampCompare
{
    bool operator()(const STimestampedData & left, const STimestampedData & right) const
    {
        return left.m_timestamp < right.m_timestamp;
    }
};
typedef std::set<STimestampedData,TimestampCompare> TimestampedDataSet;

TimestampedDataSet::iterator FindClosest(TimestampedDataSet & data, STimestampedData & searchkey)
{
    if (data.empty())
        return data.end();
    TimestampedDataSet::iterator upper = data.lower_bound(searchkey);
    if (upper == data.end())
        return --upper;
    if (upper == data.begin() || upper->m_timestamp == searchkey.m_timestamp)
        return upper;
    TimestampedDataSet::iterator lower = upper;
    --lower;
    if ((searchkey.m_timestamp - lower->m_timestamp) < (upper->m_timestamp - searchkey.m_timestamp))
        return lower;
    return upper;
}