Нахождение в какую корзину попадают значения

Question

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

A 1.0
B 2.5
C 7.0 

, который должен интерпретироваться следующим образом

"A": 0 < x <= 1.0
"B": a < x <= 2.5
"C": b < x <= 7.0

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

std::string findCategory(categories_t categories, double x) {
    ...insert magic here
}

, поэтому для этого примера я бы ожидал

findCategory(categories, 0.5) == "A"
findCategory(categories, 1.9) == "B"
findCategory(categories, 6.0) == "C"

Так что мой вопрос а) как написать функцию и б) что лучшевыбор category_t может быть (используя stl в pre 11 C ++).Я сделал несколько попыток, все из которых были ... менее чем успешными.

Answer 1

Одним из вариантов будет использование контейнера std::map с двойными значениями в качестве ключей и значений, соответствующих тому, какое значение назначено диапазону, верхней конечной точкой которого является данное значение.Например, учитывая ваш файл, у вас будет такая карта:

std::map<double, std::string> lookup;
lookup[1.0] = "A";
lookup[2.5] = "B";
lookup[7.0] = "C";

Затем вы можете использовать функцию std::map::lower_bound, учитывая некоторую точку, чтобы вернуть пару ключ / значение, ключ (верхняя конечная точка) - это первый ключ на карте, который по крайней мере такой же большой, как рассматриваемая точка.Например, с приведенной выше картой lookup.lower_bound(1.37) вернет итератор, значение которого равно "B."lookup.lower_bound(2.56) вернет итератор со значением "C".Эти поиски быстрые;они занимают O (log n) времени для карты с n элементами.

Выше я предполагаю, что все значения, которые вы ищете, неотрицательны.Если допускаются отрицательные значения, вы можете добавить быстрый тест, чтобы проверить, является ли значение отрицательным, прежде чем выполнять какие-либо поиски.Таким образом, вы можете устранить ложные результаты.

Для чего бы это ни стоило, если вы случайно узнаете что-то о распределении ваших поисков (скажем, они распределены равномерно), можно создать специальную структуру данных, которая называется оптимальное двоичное дерево поиска , которое даст лучшее время доступа, чем std::map.Кроме того, в зависимости от вашего приложения, возможны еще более быстрые варианты.Например, если вы делаете это, потому что хотите случайным образом выбрать один из результатов с различными вероятностями, я бы посоветовал изучить эту статью о методе псевдонима , которая позволяетвы генерируете случайные значения за O (1) раз.

Надеюсь, это поможет!

Answer 2

Вы можете использовать тип пары и 'lower_bound' из <алгоритма> http://www.cplusplus.com/reference/algorithm/lower_bound/.

Давайте определим ваши категории в терминах верхнего края: typedef pair category_t;

Тогда просто сделайте вектор из этих ребер и найдите его с помощью бинарного поиска. Смотрите полный пример ниже.

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

using namespace std;
typedef pair<double,string> category_t;

std::string findCategory(const vector<category_t> &categories, double x) {
   vector<category_t>::const_iterator it=std::lower_bound(categories.begin(), categories.end(),category_t(x,""));
   if(it==categories.end()){
      return "";
   }
   return it->second;
}

int main (){

   vector< category_t > edges;
   edges.push_back(category_t(0,"bin n with upper edge at 0 (underflow)"));
   edges.push_back(category_t(1,"bin A with upper edge at 1"));
   edges.push_back(category_t(2.5,"bin B with upper edge at 2.5"));
   edges.push_back(category_t(7,"bin C with upper edge at 7"));
   edges.push_back(category_t(8,"bin D with upper edge at 8"));
   edges.push_back(category_t(9,"bin E with upper edge at 9"));
   edges.push_back(category_t(10,"bin F with upper edge at 10"));

   vector< double > examples ;
   examples.push_back(1);
   examples.push_back(3.3);
   examples.push_back(7.4);
   examples.push_back(-5);
   examples.push_back(15);

   for( vector< double >::const_iterator eit =examples.begin();eit!=examples.end();++eit)
      cout << "value "<< *eit << " : " << findCategory(edges,*eit) << endl;   
}

Сравнение работает так, как мы хотим, поскольку double является первым в паре, а пары сравниваются сначала путем сравнения первого, а затем второго компонента. В противном случае мы определяем предикат сравнения, как описано на странице, на которую я ссылался выше.