Поиск «наиболее подходящего ключа» для данного ключа в отсортированном контейнере STL

Question

Задача

У меня есть данные с метками времени, которые мне нужно искать на основе метки времени, чтобы получить одну из существующих меток времени, которая соответствует моей входной метке времени, самой близкой.
Предпочтительно это должно быть решено с STL. boost :: * или stl :: tr1 :: * (из VS9 с Featurepack) также возможны.
Пример данных с меткой времени:

struct STimestampedData
{
 time_t m_timestamp; // Sorting criterion
 CData m_data;       // Payload
}

Подход с stl::vector, sort() и equal_range()

Так как map или set позволяет мне только находить точные совпадения, я не могу больше использовать один из них. Итак, теперь у меня есть vector, к которому я добавляю данные по мере их поступления. Перед поиском я использую <algorithm> s sort() и снабжаю его пользовательской функцией сравнения.
После этого я использую <algorithm> equal_range(), чтобы найти двух соседей указанного значения x. Из этих двух значений я проверяю, какое из них ближе всего к x, а затем у меня самое лучшее совпадение.

Хотя это не слишком сложно, мне интересно, есть ли более элегантные решения для этого.
Может быть, у STL уже есть алгоритм, который делает именно это, так что я не изобретаю что-то здесь?

Обновление: линейный или двоичный поиск

Я забыл упомянуть, что у меня достаточно много данных для обработки, поэтому я не хочу выполнять линейный поиск.
Причина, по которой я сортирую вектор с sort(), заключается в том, что у него есть итераторы с произвольным доступом, чего нет у map. Использование map не позволит equal_range() выполнить поиск с двойной логарифмической сложностью.
Я прав?

Answer 1

Я бы тоже использовал equal_range для такой вещи.

Если вы используете метод sort () каждый раз для своего вектора, может быть лучше использовать карту (или набор), поскольку она всегда сортируется автоматически, и использовать член equal_range

Но это зависит от количества вставок / запросов / количества данных. (хотя для чего-то, что всегда нужно сортировать, когда я запрашиваю, карта была бы моим первым выбором, и я бы использовал вектор, только если была очень веская причина)

Answer 2

Я бы использовал set :: lower_bound, чтобы найти соответствующее или большее значение, затем уменьшил бы итератор, чтобы проверить следующее более низкое значение. Вы должны использовать std :: set, а не std :: map, так как ваш ключ встроен в объект - вам нужно предоставить функтор, который сравнивает члены отметки времени.

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;
}

Answer 3

//the function should return the element from iArr which has the least distance from input
double nearestValue(vector<double> iArr, double input)
{
    double pivot(0),temp(0),index(0);
    pivot = abs(iArr[0]-input);
    for(int m=1;m<iArr.size();m++)
    {           
        temp = abs(iArr[m]-input);

        if(temp<pivot)
        {
            pivot = temp;
            index = m;
        }
    }

    return iArr[index];
}

void main()
{
    vector<double> iArr;

    srand(time(NULL));
    for(int m=0;m<10;m++)
    {
        iArr.push_back(rand()%20);
        cout<<iArr[m]<<" ";
    }

    cout<<"\nnearest value is: "<<lib.nearestValue(iArr,16)<<"\n";
}

Answer 4

В зависимости от того, что вы используете, вы можете сделать простой линейный поиск вместо сортировки. Придумайте функцию «расстояние», проследите за лучшим совпадением и его расстоянием. Когда вы найдете лучшее совпадение, забудьте о предыдущем и сохраните новое и его расстояние. Когда вы прошли через все, у вас есть ваш матч.

Это получается O (N * S), где N - количество элементов в векторе, а S - количество поисков.

Ваш текущий путь O ((N + S) * LogN), который больше, если количество поисков мало и ограничено. В противном случае сортировка / бинарный поиск лучше.