Russian Qt Forum

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

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

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

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

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

Есть 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

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

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

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

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

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

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

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

Дело в том, что функция то уже есть, но она Си-шная и там тупо перебор каждого значения. Я хотел бы портировать ее на 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;
}
 

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

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

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

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

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

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

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

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

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

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

 

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 ф-ций.

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

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

Вывод:

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

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

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

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

Спасибки :)