Найти ближайшие точки в векторе

Question

С учетом отсортированного вектора с количеством значений, как в следующем примере:

std::vector<double> f;
f.pushback(10);
f.pushback(100);
f.pushback(1000);
f.pushback(10000);

Я ищу наиболее элегантный способ получить для любого двойного d два значения, которые непосредственно примыкают к нему. Например, учитывая значение «45», я бы хотел, чтобы это возвращало «10» и «100».

Я смотрел на lower_bound и upper_bound, но они не делают то, что я хочу. Вы можете помочь?

РЕДАКТИРОВАТЬ: Я решил опубликовать свой собственный anser, так как это несколько сборник всех полезных ответов, которые я получил в этой теме. Я проголосовал за те ответы, которые мне показались наиболее полезными.

Спасибо всем,

Dave

Answer 1

Вы можете использовать STL lower_bound, чтобы получить желаемое в нескольких строках кода. lower_bound использует бинарный поиск под капотом, поэтому ваша среда выполнения O (log n).

double val = 45;
double lower, upper;
std::vector<double>::iterator it;
it = lower_bound(f.begin(), f.end(), val);
if (it == f.begin()) upper = *it; // no smaller value  than val in vector
else if (it == f.end()) lower = *(it-1); // no bigger value than val in vector
else {
    lower = *(it-1);
    upper = *it;
}

Answer 2

Вы можете получить оба значения (если они существуют) за один вызов с помощью equal_range (). Он возвращает std :: pair итераторов, причем первым является первое местоположение, а вторым - последнее местоположение, в которое можно вставить переданное значение без нарушения порядка. Чтобы строго соответствовать вашим критериям, вам нужно сначала уменьшить значение итератора, убедившись, что он не равен вектору begin ().

Answer 3

Вы можете просто использовать двоичный поиск , который будет работать в O (log (n)).

Вот фрагмент кода Lua (у меня нет времени делать это в C ++, извините), который делает то, что вы хотите, за исключением предельных условий (которые вы так и не определили):

function search(value, list, first, last)
    if not first then first = 1; last = #list end

    if last - first < 2 then
        return list[first], list[last]
    end

    local median = math.ceil(first + (last - first)/2)

    if list[median] > value then
        return search(value, list, first, median)
    else
        return search(value, list, median, last)
    end
end

local list = {1,10,100,1000}

print(search(arg[1] + 0, list))

Требуется значение для поиска из командной строки:

$ lua search.lua 10 # didn't know what to do in this case
10  100
$ lua search.lua 101
100 1000
$ lua search.lua 99
10  100

Answer 4

Я собираюсь опубликовать свой собственный ансер и проголосовать за любого, кто помог мне достичь его, так как это то, что я буду использовать в конце, и вы все помогли мне прийти к такому выводу. Комментарии приветствуются.

std::pair<value_type, value_type> GetDivisions(const value_type& from) const
{
    if (m_divisions.empty())
        throw 0; // Can't help you if we're empty.

    std::vector<value_type>::const_iterator it = 
        std::lower_bound(m_divisions.begin(), m_divisions.end(), from);

    if (it == m_divisions.end())
        return std::make_pair(m_divisions.back(), m_divisions.back());
    else if (it == m_divisions.begin())
        return std::make_pair(m_divisions.front(), m_divisions.front());
    else
        return std::make_pair(*(it - 1), *(it));
}

Answer 5

Что если (в вашем случае) d меньше первого элемента или больше, чем последний? А как бороться с отрицательными значениями? Кстати, гарантируя, что ваше «d» будет находиться между первым и последним значением вашего вектора, вы можете сделать это так:

// Your initializations
std::vector<double>::const_iterator sit = f.begin();
double upper, lower; 

Вот остальные:

while ( *sit < d )         // if the element is still less than your d
    ++sit;                 // increase your iterator

upper = *sit;              // here you get the upper value
lower = *(--sit);          // and here your lower

Достаточно элегантно? : /

Answer 6

Основываясь на коде, опубликованном Tunnuz, у вас есть некоторые улучшения в отношении проверки границ:

template<typename T>
void find_enclosing_values(const std::vector<T> &vec, const T &value, T &lower, T &upper, const T &invalid_value)
{
    std::vector<T>::const_iterator it = vec.begin();

    while (it != vec.end() && *it < value)
        ++it;

    if(it != vec.end())
        upper = *it;
    else
        upper = invalid_value;

    if(it == vec.begin())
        lower = invalid_value;
    else
        lower = *(--it);

}

Пример использования:

std::vector<int> v;

v.push_back(3);
v.push_back(7);
v.push_back(10);

int lower, upper;

find_enclosing_values(v, 4, lower, upper, -1);

std::cout<<"lower "<<lower<<" upper "<<upper<<std::endl;

Answer 7

Я написал эту маленькую функцию, которая, кажется, подходит для более общего случая, который вы хотели. Я не проверял это полностью, но я написал небольшой тестовый код (в комплекте).

#include <algorithm>
#include <iostream>
#include <vector>

template <class RandomAccessIt, class Container, class T>
std::pair<RandomAccessIt, RandomAccessIt> bracket_range(RandomAccessIt begin, RandomAccessIt end, Container& c, T val)
{
    typename Container::iterator first;
    typename Container::iterator second;

    first = std::find(begin, end, val);
    //Find the first value after this by iteration
    second = first;
    if (first == begin){ // Found the first element, so set this to end to indicate no lower values
    first = end;
    }
    else if (first != end && first != begin) --first; //Set this to the first value before the found one, if the value was found
    while (second != end && *second == val) ++second;
    return std::make_pair(first,second);
}

int main(int argc, _TCHAR* argv[])
{
    std::vector<int> values;
    std::pair<std::vector<int>::iterator, std::vector<int>::iterator> vals;

    for (int i = 1; i < 9; ++i) values.push_back(i);

    for (int i = 0; i < 10; ++i){
        vals = bracket_range(values.begin(), values.end(),values, i);
        if (vals.first == values.end() && vals.second == values.end()){ // Not found at all
            std::cout << i << " is not in the container." << std::endl;
        }
        else if (vals.first == values.end()){ // No value lower
            std::cout << i << ": " << "None Lower," << *(vals.second) << std::endl;
        }
        else if (vals.second == values.end()) { // No value higher
            std::cout << i << ": " << *(vals.first) << ", None Higher" << std::endl;
        }
        else{
        std::cout << i << ": " << *(vals.first) << "," << *(vals.second) << std::endl;
        }
    }
    return 0;
}

Answer 8

Я бы написал что-то вроде этого, не проверял, компилируется ли это, но вы поняли:

template <typename Iterator>
std::pair<Iterator, Iterator> find_best_pair(Iterator first, Iterator last, const typename Iterator::value_type & val)
{
    std::pair<Iterator, Iterator> result(last, last);

    typename Iterator::difference_type size = std::distance(first, last);

    if (size == 2)
    {
        // if the container is of size 2, the answer is the two elements 
        result.first = first;
        result.first = first;
        ++result.first;
    }
    else
    {

        // must be of at lease size 3
        if (size > 2)
        {
            Iterator second = first;
            ++second;
            Iterator prev_last = last;
            --prev_last;
            Iterator it(std::lower_bound(second, last, val));

            if (it != last)
            {

                result.first = it;
                result.second = it;


                if (it != prev_last)
                {
                    // if this is not the previous last
                    // then the answer is (it, it + 1)
                    ++result.second;
                }
                else
                {
                    // if this the previous last
                    // then the answer is (it - 1, it)
                    --result.first;
                }

            }

        }

    }

    return result;


}

Answer 9

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

Answer 10

Вы можете выполнить поиск в вашем векторе для вашего значения (которое скажет вам, где будет ваше значение, если бы оно было в векторе), а затем вернуть значение до и после этого местоположения. Таким образом, поиск 45 скажет вам, что он должен быть с index = 1, а затем вы вернете 0 и 1 (в зависимости от вашей реализации поиска вы получите либо индекс меньшего значения, либо индекс большего значения, но это легко проверить с парой граничных условий). Это должно быть в состоянии работать в O (log n), где n - количество элементов в вашем векторе.