[Решено][STL] Найти ближайшее меньшее или большее значение.

[kuzulis]

Доброго всем времени.

Задача: Есть отсортированный вектор целых значений.
Необходимо вернуть ближайшее больше или ближайшее меньшее значение относительно заданного, т.е.:

Код

C++ (Qt)
int main(int argc, char *argv[])
{
    int myints[] = {16,32,64,128,256,512,1024,2048};
    std::vector<int> v(myints,myints + 8);
 
    std::vector<int>::iterator low, up;
    low = std::near_lower(v.begin(), v.end(), 230); //
    up = std::near_upper(v.begin(), v.end(), 230); //
 
    std::cout << "near lower " << (*low) << '\n';
    std::cout << "near upper" << (*up) << '\n';
 
    return 0;
}
 

Должно вывести:

near lower 128
near upper 256

Есть ли в STL готовое решение (что-то типа near_lower(), near_upper())? Интересует стандарт C++98.. Или нужно самому городить огород?  

[m_ax]

Есть find_if

Код

C++ (Qt)
    int myints[] = {16,32,64,128,256,512,1024,2048};
    std::vector<int> v(myints,myints + 8);
 
    std::vector<int>::iterator low;
 
    int val = 230;
 
    if ((low = std::find_if(v.begin(), v.end(), std::bind1st(std::less_equal<int>(), val))) != v.end()) {
        if (low != v.begin()) --low;
        std::cout << *low << std::endl;
    }
 
 

Аналогично и для near_upper

[m_ax]

Нет, лучше так не делать..

Наверное проще свою функцию написать.. Не намного больше кода получится..

Edit:
(Это будет корректно работать, только если список отсортирован!)

[_OLEGator_]

Например, методом деления пополам искать.

[m_ax]

Например, методом деления пополам искать.

Только вот не для всех контейнеров это прокатит.. ( Точнее сказать, не для всех это будет эффективно..

[kuzulis]

Да, спасибо, парни.

> Например, методом деления пополам искать.

Дело в том, что функция то уже есть, но она Си-шная и там тупо перебор каждого значения. Я хотел бы портировать ее на C++ с использованием шаблонов.

> Наверное проще свою функцию написать.. Не намного больше кода получится..

А если делать шаблонными near_lower() и near_upper() - То как будет выглядеть код? А то я в шаблонах не очень то..

Переписал на шаблонах:

Код

C++ (Qt)
template<class InputIterator, class T>
InputIterator near_lower(InputIterator first, InputIterator last, const T& val)
{
    InputIterator lower;
    if ((lower = std::find_if(first, last, std::bind1st(std::less_equal<T>(), val))) != last) {
        if (lower != first)
            --lower;
    }
    return lower;
}
 
int main(int argc, char *argv[])
{
    int myints[] = {16,32,64,128,256,512,1024,2048};
    std::vector<int> v(myints,myints + 8);
    std::vector<int>::iterator low;
    int val = 230;
    low = near_lower(v.begin(), v.end(), val);
    std::cout << "lower " << (*low);
    return 0;
}
 

[m_ax]

А если делать шаблонными near_lower() и near_upper() - То как будет выглядеть код? А то я в шаблонах не очень то..

Не, всё нормально.. Если вы гарантируете, что список будет отсортирован..

И ещё, конечно, нужно проверять: не вернула ли near_lower end:

Код

C++ (Qt)
if ((low = near_lower(v.begin(), v.end(), val) != v.end()) {
    std::cout << *low << std::endl;
}
 

[kuzulis]

Блин, что-то тяжко с шаблонами у меня. Нужно например так реализовать, чтобы при:

val = 1 -> low=-xxxx, up=-xxxx // выход за границы, it::end
val = 16 -> low=16, up=16
val = 17 -> low=16, up=32
val = 31 -> low=16, up=32
val = 2048 -> low=2048, up=2048
val = 2049 -> low=-xxxx, up=-xxxx // выход за границы, it::end

Такое возможно?

[m_ax]

Вот для произвольной последовательности:

Код

C++ (Qt)
template<class InputIterator, class T>
InputIterator near_lower(InputIterator first, InputIterator last, const T& val)
{
    InputIterator lower = first;
    while (first != last) {
        if ((val - *first >= 0) && (val - *first <= fabs(val - *lower)))
            lower = first;
        ++first;
    }
    return lower;
}
 
int main()
{
    std::vector<int> v = {161,-32,64,128,-256,512,1024,2048};
    int val = 0;
    std::vector<int>::iterator low;
 
    if ((low = near_lower(v.begin(), v.end(), val)) != v.end())
        std::cout << *low << std::endl;
 
    return 0;
}
 

[m_ax]

Кстати, есть же стандартные std::lower_bound  и std::upper_bound 
Работают только для отсортированных последовательностей..

Код

C++ (Qt)
template<class InputIterator, class T>
InputIterator near_lower_s(InputIterator first, InputIterator last, const T& val)
{
    if ((val < *first) || (first == last)) return last;
    InputIterator lower = std::lower_bound(first, last, val);
 
    return (lower == last) ? --lower : lower;
}
 

 

[Igors]

Код

C++ (Qt)
int main(int argc, char *argv[])
{
    int myints[] = {16,32,64,128,256,512,1024,2048};
    std::vector<int> v(myints, myints + sizeof(myints) / sizeof(myints[0]));
 
    int resLo, resHi, match = 230;
    int * bound = std::lower_bound(v.begin(), v.end(), match); 
    if (bound == v.end()) 
     resLo = resHi = v.back();
    else { 
     if (*bound == match)
       resLo = resHi = match;
     else {
      resHi = *bound;
      resLo = (bound == v.begin()) ? resHi : *(bound - 1);
     }
    }
 
    std::cout << "near lower " << resLo << '\n';
    std::cout << "near upper" << resHi << '\n';
 
    return 0;
}
 

lower_bound (upper_bound) - одни из немногих действительно нужных std ф-ций.

[kuzulis]

Спасибо парни, в итоге наваял это:

Код

C++ (Qt)
#include "stdafx.h"
 
#include <iostream>
#include <algorithm>
#include <vector>
 
template<class InputIterator, class T>
T near_lower(const InputIterator first, const InputIterator last, const T& val)
{
    InputIterator lower = std::lower_bound(first, last, val);
    if ((val <= *first) || (lower == last) || (first == last)) return val;
    if (val != *lower) --lower;
    return (*lower);
}
 
template<class InputIterator, class T>
T near_upper(const InputIterator first, const InputIterator last, const T& val)
{
    InputIterator upper = std::lower_bound(first, last, val);
    return ((val <= *first) || (upper == last) || (first == last)) ? val : (*upper);
}
 
void tst_lower(std::vector<int>::const_iterator &first, std::vector<int>::const_iterator &last)
{
    int test_sequence[] = {1,16,17,230,256,2000,2048,2049,60000};
    std::vector<int> tst(test_sequence, test_sequence + 9);
    std::vector<int>::const_iterator it = tst.begin();
    std::vector<int>::const_iterator end = tst.end();
    std::cout << std::endl << "Lower test: " << std::endl;
    for (it; it != end; ++it) {
        int low = near_lower(first, last, *it);
        std::cout << "val " << (*it) << ", lower " << low << std::endl;
    }
}
 
void tst_upper(std::vector<int>::const_iterator &first, std::vector<int>::const_iterator &last)
{
    int test_sequence[] = {1,16,17,230,256,2000,2048,2049,60000};
    std::vector<int> tst(test_sequence, test_sequence + 9);
    std::vector<int>::const_iterator it = tst.begin();
    std::vector<int>::const_iterator end = tst.end();
    std::cout << std::endl << "Upper test: " << std::endl;
    for (it; it != end; ++it) {
        int low = near_upper(first, last, *it);
        std::cout << "val " << (*it) << ", upper " << low << std::endl;
    }
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    int myints[] = {16,32,64,128,256,512,1024,2048};
    std::vector<int> v(myints, myints + 8);
 
    tst_lower(v.begin(), v.end());
    tst_upper(v.begin(), v.end());
 
    return 0;
}
 

Вывод:

Lower test:
val 1, lower 1
val 16, lower 16
val 17, lower 16
val 230, lower 128
val 256, lower 256
val 2000, lower 1024
val 2048, lower 2048
val 2049, lower 2049
val 60000, lower 60000

Upper test:
val 1, upper 1
val 16, upper 16
val 17, upper 32
val 230, upper 256
val 256, upper 256
val 2000, upper 2048
val 2048, upper 2048
val 2049, upper 2049
val 60000, upper 60000

Вроде то что нужно, правда немного изменил алгоритм при выходе за границы.. 

[Igors]

Засовывать в вектор необязвтельно, можно просто для массива. И обычно

Код

C++ (Qt)
typedef std::vector<int>::const_iterator TIter;

а то сопля длинная получается 

[kuzulis]

Спасибки