Блог

Главная - Вопросы по программированию - Что именно делает этот std::верхняя граница в этом коде?

Что именно делает этот std::верхняя граница в этом коде?

#c

#c

Вопрос:

Начальная школа — Упражнения

К упражнению также прилагается набор тестов.

 void school::add(std::string name, int grade)
{
    roster_[grade].insert(std::upper_bound(roster_[grade].begin(), roster_[grade].end(), name), name);
}

roster_ определяется как std::map<int, std::vector<std::string>> roster_; .

Комментарии:

1. Вы посмотрели, что upper_bound делает? Что в этом заставляет вас не знать, что он делает?

2. en.cppreference.com/w/cpp/algorithm/upper_bound

3. Что вы подразумеваете под сравнением с именем внутри функции? Он сравнивает значения в rooster_ с name .

4. Я был немного смущен тем, как это работает, но приведенные ниже пояснения разобрали это. Спасибо

Ответ №1:

Я считаю, что это определение легче запомнить / визуализировать:

  • it = std::upper_bound(beg, end, x) дает вам it указатель на последнюю позицию, которую вы можете вставить x в контейнер [beg, end) , чтобы контейнер оставался отсортированным, если он отсортирован;
  • it = std::lower_bound(beg, end, x) дает вам it указатель на первую позицию, которую вы можете вставить x в контейнер [beg, end) , чтобы контейнер оставался отсортированным, если он отсортирован.

Поэтому, учитывая std::vector<int> v{0,2,2,2,3}; ,

  • std::upper_bound(v.begin(), v.end(), 2) возвращает итератор в 3 , потому что вставка 2 непосредственно перед 3 не нарушает сортировку;
  • std::lower_bound(v.begin(), v.end(), 1) возвращает итератор к первому 2 , потому что вставка 1 непосредственно перед ним не нарушает сортировку.

Следовательно, этот код (добавляющий новую строку для ясности) вставляет name в последнее место, куда он может перейти, не нарушая ранее существовавшую сортировку.

 roster_[grade].insert(
    std::upper_bound(roster_[grade].begin(), roster_[grade].end(), name),
    name);

Определения, которые вы находите в cppreference, полезны и необходимы, если вы предполагаете, что контейнер не отсортирован, и в этом случае эти функции все еще полезны, но это менее очевидно, имхо.

Комментарии:

1. Спасибо. Это было полезно 🙂

2. @fazfactor, веская причина для его принятия, нет? 😛

Ответ №2:

Ваш код вставляет имя в отсортированный список в правильном месте. У вас есть:

 roster_[grade].insert(
    std::upper_bound(roster_[grade].begin(), roster_[grade].end(), name),
    name);

где rooster_[grade] находится std::vector . Что происходит, так это:

  1. вы используете std::upper_bound, чтобы найти первый элемент в списке, который больше name , то есть элемент, имя которого должно быть вставлено раньше, чтобы сохранить список отсортированным. Это зависит от того, что ваш список уже отсортирован, и, вероятно, использует двоичный поиск. Если он не находит больших значений, т.Е. name больше, чем все значения в списке, он вернет конечный итератор.
  2. вы используете std::vector::insert с возвращаемым значением из std::upper_bound, чтобы вставить имя в эту позицию. Если у нас есть конечный итератор, мы добавим name в конец списка.
Метки: