std :: set，lower_bound和upper_bound如何工作？

Question

我有這樣簡單的代碼：

#include <iostream> 
#include <set> 

using std::set; 

int main(int argc, char argv) { 
    set<int> myset; 
    set<int>::iterator it_l, it_u; 
    myset.insert(10); 
    it_l = myset.lower_bound(11); 
    it_u = myset.upper_bound(9); 

    std::cout << *it_l << " " << *it_u << std::endl; 
} 

這將打印1爲下界11和10作爲上界9.

我不理解爲什麼打印1。我希望使用這兩種方法來獲得給定上限/下限的一系列值。

Answer 1

從cppreference.com上的std ::設置:: LOWER_BOUND：

返回值

迭代器，指向不是少低於關鍵的第一要素。如果沒有找到這樣的元素，則返回一個前端迭代器（參見end()）。

在你的情況下，因爲你在你的集合沒有元件，其不小於11以下（即大於或等於），過去最結束迭代返回並分配給it_l。然後在您的線路：

std::cout << *it_l << " " << *it_u << std::endl; 

你deferencing過去的這個最末端迭代器it_l：這是未定義的行爲，以及（可能導致任何1在您的測試，0或任何其他值與其他編譯器，或者程序甚至可能崩潰）。

你的下限應小於或等於所述上界，並且，你不能解除引用的環或任何其他測試環境之外的迭代：

#include <iostream> 
#include <set> 

using std::set; 

int main(int argc, char argv) { 
    set<int> myset; 
    set<int>::iterator it_l, it_u; 
    myset.insert(9); 
    myset.insert(10); 
    myset.insert(11); 
    it_l = myset.lower_bound(10); 
    it_u = myset.upper_bound(10); 

    while(it_l != it_u) 
    { 
     std::cout << *it_l << std::endl; // will only print 10 
     it_l++; 
    } 
} 

Answer 2

這是UB。您的it_l = myset.lower_bound(11);返回myset.end()（因爲它無法在該集合中找到任何內容），您沒有檢查，然後您基本上打印出過去最終迭代器的值。

Answer 3

的LOWER_BOUND（）返回迭代器的第一個元素是不少於比一個關鍵。當找不到這樣的元素時，返回end（）。

請注意，用end（）返回的迭代器指向集合中過去結束的元素。這是標準容器的正常行爲，表明出現了問題。作爲一個經驗法則，您應該始終檢查並做出相應處理。

你的一段代碼就是上述情況的例子，因爲在集合中沒有不少於11個的元素。打印的'1'只是來自end（）迭代器的垃圾值。

與下面的代碼段看到它自己：

#include <iostream> 
#include <set> 

using std::set; 

int main(int argc, char argv) { 
    set<int> myset; 
    set<int>::iterator it_l, it_u; 
    myset.insert(10); 

    it_l = myset.lower_bound(11); 
    if (it_l == myset.end()) { 
     std::cout << "we are at the end" << std::endl; 
    } 

    it_u = myset.upper_bound(9); 

    std::cout << *it_l << " " << *it_u << std::endl; 
}