c++ - What does this std::upper bound exactly do in this code?

Question

Grade School - Excercism

There is a test suite attached to the exercise as well.

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

---

roster_ is defined as std::map<int, std::vector<std::string>> roster_;.

Answer 1

I find this definition easier to remember/visualize:

• it = std::upper_bound(beg, end, x) gives you the iterator to the last position where you can insert x in the container [beg, end) such that the container remains sorted if it is sorted;
• it = std::lower_bound(beg, end, x) gives you the iterator to the first position where you can insert x in the container [beg, end) such that the container remains sorted if it is sorted.

Therefore, given std::vector<int> v{0,2,2,2,3};,

• std::upper_bound(v.begin(), v.end(), 2) returns the iterator to the 3, because inserting 2 just before the 3 doesn't break the sorting;
• std::lower_bound(v.begin(), v.end(), 1) returns the iterator to the first 2 because inserting 1 just before it doesn't break the sorting.

Therefore, that code (adding some new line for clarity) inserts name at the last place it can go without breaking a pre-existing sorting.

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

The definitions you find on cppreference are useful and necessary if you assume the container is not sorted, in which case these functions are still useful, but it in a less obvious way, imho.