C++ std :: set upper_bound поведение итератора

Question

У меня была проблема с поиском кода и я не уверен в правильной интерпретации тестирования итератора. Проблема заключается в следующем: у меня есть набор и выполняю поиск с использованием upper_bound, а затем хочу найти следующий нижний элемент. Как это:

#include <iostream> 
#include <set> 
#include <algorithm> 

void exploreSet(std::set<int> &int_set, int key); 

int main() 
{ 
    std::set<int> int_set { 5, 10, 12, 17, 19 }; 
    exploreSet(int_set, 15); 
    exploreSet(int_set, 4); 
    return 0; 
} 


void exploreSet(std::set<int> &int_set, int key) 
{ 
    auto it = int_set.upper_bound(key); 
    if (it==int_set.end()) 
    { 
     std::cout << "Nothing found.\n"; 
    } 
    else 
    { 
     std::cout << "Found " << *it << ".\n"; 
     // Now find the next lowest value -- how? 
     auto it_back = it; 
     --it_back; 
     if (it_back==int_set.end()) 
     { 
      std::cout << "Nothing prior.\n"; 
     } 
     else 
     { 
      std::cout << "Prior value: " << *it_back << ".\n"; 
     } 
    } 
} 

Результирующий вывод работает это на GCC 4.9.2 с станд = C++ 14:

Found 17. 
Prior value: 12. 
Found 5. 
Nothing prior. 

Это работает. Но почему?

Правильно ли сравнивать с std :: set :: end() при обратном движении на итераторе, полученном через upper_bound? Почему или почему нет?

Answer 1

Нет, это неправильно. Уменьшение итератора, равное begin(), является неопределенным поведением. См [bidirectional.iterators]/1, Таблица 110:

Expression
--r
утверждение/примечание до/после условие
предварительно: существует s такое, что r == ++s.
пост: r является разыменованным.

Так правильный путь, чтобы сравнить it с int_set.begin():

// Now find the next lowest value -- how? 
if (it == int_set.begin()) 
{ 
    std::cout << "Nothing prior.\n"; 
} 
else 
{ 
    auto it_back = it; 
    --it_back; 
    std::cout << "Prior value: " << *it_back << ".\n"; 
} 

То есть, я бы вместо этого советую использовать std::set<int, std::greater<int>> вместе с lower_bound:

template <typename Set> 
void exploreSet(const Set& int_set, int key) { 
    auto it = int_set.lower_bound(key); 
    if (it == int_set.end()) 
     std::cout << "Nothing found.\n"; 
    else 
     std::cout << "Found " << *it << ".\n"; 
} 

int main() { 
    std::set<int, std::greater<int>> int_set { 5, 10, 12, 17, 19 }; 
    exploreSet(int_set, 15); 
    exploreSet(int_set, 4); 
}