關于upper_bound,和lower_bound

在有序的空間查找一個元素的位置，并且在插入該元素之後，仍舊維持該空間的有序。

例如：一個vec,其中存在元素：0,3,5,8；

如果試圖插入元素4，

兩個元素傳回的都是5所對應的位置，執行insert在該位置插入4後，該vec是這個樣子：0,3,4,5,8；

如果試圖插入元素5，

則lower_bound傳回元素5的位置，而upper_bound傳回元素8的位置。

此時如果執行插入5後，vec看起來的樣子是一樣的。但實際上，對lowwer插入的5在原先的5之前，而對upper_bound插入的5在原先的5之後。

綜合起來說，lowwer_bound傳回第一個可以插入的位置，而upper_bound傳回的最後一個可以插入的位置。

備注：這兩個函數的比較是基于等價的比較，而不是相等的比較，何為等價，何為相等，請參閱《effective stl》。

關于lowwer_bound和upper_bound的測試代碼如下：

// alg_upper_bound.cpp

// compile with: /EHsc

#include <vector>

#include <algorithm>

#include <functional>      // For greater<int>( )

#include <iostream>

// Return whether modulus of elem1 is less than modulus of elem2

struct Print

{

template <typename T>

void operator () (const T &val)

{

std::cout << val << "\t";

}

};

int main( )

{

typedef std::vector<int> VecInt;

typedef VecInt::iterator It;

const int VECSIZE = 10;

srand(0);

VecInt vi, vi2;

vi.reserve(VECSIZE);

for (int i = 0; i < VECSIZE; ++i)

{

vi.push_back(int(double(rand())/RAND_MAX * 100));

}

vi2.assign(vi.begin(), vi.end());

sort(vi.begin(), vi.end(), std::less<int>());

sort(vi2.begin(), vi2.end(), std::greater<int>());

std::cout << "value in vi: " << std::endl;

std::for_each(vi.begin(), vi.end(), Print());

std::cout << "value in vi2: " << std::endl;

std::for_each(vi2.begin(), vi2.end(), Print());

It iter = std::lower_bound(vi.begin(), vi.end(), 23);

std::cout << "lower_boudn of vi for 23 is: " << *iter << std::endl;

iter = std::upper_bound(vi.begin(), vi.end(), 23);

std::cout << "upper_boudn of vi for 23 is: " << *iter << std::endl;

iter = std::lower_bound(vi2.begin(), vi2.end(), 23, std::greater<int>());

std::cout << "lower_boudn of vi2 for 23 is: " << *iter << std::endl;

iter = std::upper_bound(vi2.begin(), vi2.end(), 23, std::greater<int>());

std::cout << "upper_boudn of vi2 for 23 is: " << *iter << std::endl;

iter = std::lower_bound(vi.begin(), vi.end(), 24);

std::cout << "lower_boudn of vi for 24 is: " << *iter << std::endl;

iter = std::upper_bound(vi.begin(), vi.end(), 24);

std::cout << "upper_boudn of vi for 24 is: " << *iter << std::endl;

iter = std::lower_bound(vi2.begin(), vi2.end(), 24, std::greater<int>());

std::cout << "lower_boudn of vi2 for 23 is: " << *iter << std::endl;

iter = std::upper_bound(vi2.begin(), vi2.end(), 24, std::greater<int>());

std::cout << "upper_boudn of vi2 for 24 is: " << *iter << std::endl;

system("pause..");

}