lower_bound по вектору пары после проверки одного значения пары - PullRequest
Новая
       54

lower_bound по вектору пары после проверки одного значения пары

0 голосов
/ 09 июня 2018

У меня есть вектор пар vector< pair< string,int> > в C++, и я хочу, чтобы lower_bound для строкового значения, но с дополнительным ограничением, что второе значение пары должно быть меньше или равно заданному значению.В настоящее время я делаю это, используя шаблон сравнения 

bool compare(const T &a,const T &b){
if (a.first<=b.first&&b.second<=a.second) return true;
}

, но он не работает должным образом.Вектор сортируется по первому значению пары.Пример-> Вектор имеет следующее содержимое: 

abcd,1
abcde,4
abcdex,3
abce,2

, и я хочу, чтобы lower_bound на abc,3, поэтому он должен возвращать abcd,1, но возвращает abcdex,3. Пожалуйста, помогите.

1 Ответ

0 голосов
/ 09 июня 2018

std::lower_bound принадлежит семейству алгоритмов binary search, где элементы сравниваются с использованием operator <для первой версии и comp для второй.Элементы в диапазоне <strong>уже должны быть отсортированы по этому же критерию (оператор <или comp) или, по крайней мере, разделены по значению val. </p>

Это означает, что вам нужносначала отсортировать вектор, как вы упомянули в пути, чтобы действовать std::lower_bound так, как вы ожидаете.

После того, как вы отсортировали вектор массива таким образом, вы упомянули использование compare functor /(Я сделал это как лямбда), вы можете использовать std::lower_bound.

СМОТРИТЕ В ЖИЗНИ ЗДЕСЬ 

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

int main()
{
   using Pair = std::pair< std::string, int> ;
   std::vector< Pair > vec =
   {
      {"abcd", 1},
      {"abcde", 4},
      {"abcdex", 3},
      {"abce", 2}
   };
   // define the compare lambda/ functor accordingly
   auto  compare = [](const Pair &lhs, const Pair &rhs)->bool
   { return (rhs.second > lhs.second) ? false: lhs.first <= rhs.first;  };

   // sorted the vector according to the custom compare
   std::sort(vec.begin(), vec.end(), compare);

   auto getLower = std::lower_bound(vec.begin(), vec.end(), Pair("abc",3), compare);

   if(getLower != vec.cend()) std::cout << getLower->first << " " << getLower->second;

  return 0;
}

Выход: 

abcd 1

ПРИМЕЧАНИЕ : чтобы использовать std::lower_bound, вам нужно отсортировать вектор в соответствии с тем, как вы хотите применить нижнюю границу первой (чтоявляется основным).

Однако в вашем шаблоне сортировки std::lower_bound не знает второго значения пары (int), если массив правильно отсортирован или нет.Другими словами, даже если вы отсортируете соответственно то, что упомянули заранее, std::lower_bound не сможет дать вам желаемого результата, поскольку вы сортируете Pair s таким образом, что Pair.first и Pair.second в обратном порядке.

Поэтому я предлагаю вам использовать std::find_if, который будет выполнять линейный поиск элементов и должен использовать тот же алгоритм сравнения, что и предикат.Если вектор отсортирован соответствующим образом заранее (как вы упомянули), тогда он должен дать вам правильный результат.

// sort before
checkPair =  Pair("abc",3);
auto getLower = std::find_if( vec.begin(), vec.end(), [&checkPair](const Pair &ele) -> bool
{
   if(currPair == ele ) return true;

   return (checkPair.first >= ele.first      //--> "whose value is greater than or equal to the given string
          && ele.second < checkPair.second); //--> second value is less than a number
});

(getLower != vec.cend()) ? 
         std::cout << getLower->first << " " << getLower->second:
         std::cout << "Nothing found";
...