lower_bound関数とupper_bound関数

http://www.geocities.jp/ky_webid/cpp/library/020.html

ソート済みの配列に値を挿入する場合、例えばpush_back等で追加した後にまたソートしなおさないといけないので冗長です。

lower_boundとupper_boundを使えば、値の挿入位置を適切に検出できます。

lower_bound関数は指定した値"以上"の要素が最初に現れる位置を返し、upper_bound関数は指定した値より"大きい"の要素が最初に現れる位置を返します。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main () {
    vector<int> data;
    
    // 0〜18まで2の倍数を格納
    for(int i=0;i<10;++i) {
        data.push_back(i*2);
    }
    
    vector<int>::iterator it1 = lower_bound(data.begin(),data.end(),7);
    vector<int>::iterator it2 = upper_bound(data.begin(),data.end(),7);
    
    vector<int>::iterator it3 = lower_bound(data.begin(),data.end(),8);
    vector<int>::iterator it4 = upper_bound(data.begin(),data.end(),8);
    
    cout << "lower_bound(7) " << *it1 << endl;
    cout << "upper_bound(7) " << *it2 << endl;
    cout << "lower_bound(8) " << *it3 << endl;
    cout << "upper_bound(8) " << *it4 << endl;
    
    return 0;
}

$ main
lower_bound(7) 8
upper_bound(7) 8
lower_bound(8) 8
upper_bound(8) 10

値が7の場合は両方とも8になりますが、値が8の場合はupper_boundが10になりますね。

後はこれで得たiteratorからinsert等の関数を呼んで値を挿入すればよいだけですね。