#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

    // vector的插入：如果迭代器指向了某一元素，那么插入后将该元素挤到了后面，即插入到该元素之前

    vector<int>v;

    v.push_back(), v.push_back(), v.push_back();

    vector<int>::iterator it;

    it = v.begin();

    it++;

    v.insert(it, );

    for (int i = ; i < v.size(); ++i) printf("%d ", v[i]);

    puts("");

    /*

    Output:

    2 100 3 4

    */ 

    // lower_bound和upper_bound：今天看到这样的一个描述，[lower_bound, upper_bound)之间的元素与查找的元素相等

    // 如果没有该元素，那么lower_bound = upper_bound，在lower_bound位置插入则插入到该元素区间的最前面，在

    // upper_bound位置插入则插入到该元素区间的最后面，如果没有该元素，那么两个位置就想等了

    // 对于upper_bound，如果一个元素大于最大的元素和等于最后的元素其返回的结果相同，这是由于区间大小的限制
    // 当时上述情况下lower_bound的结果会有所不同，很容易理解，前者相减之后的值为0，后者相减之后的值为1

    int a[] = {, , , , };

    int b[] = {, , , , };

    for (int i = ; i < ; ++i) {

        int x = lower_bound(a, a+, b[i]) - a;

        int y = upper_bound(a, a+, b[i]) - a;

        printf("low = %d, up = %d\n", x, y);

    }

    puts("");

    /*

    Output:

    low = 0, up = 0

    low = 0, up = 1

    low = 1, up = 3

    low = 4, up = 5

    low = 5, up = 5

    */

    // equal_range：在一个排序的数组中返回与所查询值相等的区间，注意返回值是pair<iterator, iterator>

    // 其中前一个值为lower_bound的值，后一个数为upper_bound的值

    pair<int *, int *>range;

    for (int i = ; i < ; ++i) {

        range = equal_range(a, a+, b[i]);

        printf("low = %d, up = %d\n", range.first-a, range.second-a);

    }

    /*

    Output:

    low = 0, up = 0

    low = 0, up = 1

    low = 1, up = 3

    low = 4, up = 5

    low = 5, up = 5

    */

    return ;

}