lower_boundの使い方 - NO ENGINEER NO CRY

自戒記事です

先日、こちらの問題を解いていて頭がバグってしまったのでvectorとlower_boundの出力についてまとめておきます。

ターゲットとしては、最近競プロを始めてcからc++に乗り換えたけどc++のライブラリとかよくわからん！ vectorがあんまり分かってない！って人になるかも。

lower_boundの出力

lower_boundとは、指定された要素以上の値が現れる最初の位置のイテレータを取得する関数であり、ソート済みの範囲に使用することで任意の値を二分探索で見つけることができます。
lower_bound(range,key)で、key以上の値の所在地やその値自体を返すことができます。
また、vectorはそれ単独で配列のような動きをするので、vectorを配列にすると多次元配列のような動きができます。
下記の例では、array[0]に偶数、array[1]に奇数を格納することで、array[0][n],array[1][n]というような動作をしています。

例

#include<bits/stdc++.h>
using namespace std;

int main(){
  vector<int>array[2];
  for(int i=0;i<10;i++){
    if(i%2==0){
      array[0].push_back(i);
    }else{
      array[1].push_back(i);
    }
  //array[0]=0,2,4,6,8
  //array[1]=1,3,5,7,9
  }

//指定されたキーが先頭から何番目か出力される
  for(int i=0;i<10;i++){
    printf ("%d\n",lower_bound(array[0].begin(),array[0].end(),i)-array[0].begin());
   //目的の数字の番地 - 先頭の番地 = 目的の数字が何番目か
   //1 1 2 2 3 3 4 4 5
  }

//指定されたキー以上の値が保持されているメモリ番地が出力される
  for(int i=0;i<10;i++){
    printf ("%d\n",lower_bound(array[0].begin(),array[0].end(),i));
    //下記参照
  }

//指定されたキー以上の値が出力される
  for(int i=0;i<10;i++){
    printf ("%d\n",*lower_bound(array[0].begin(),array[0].end(),i));
   // 0 2 2 4 4 6 6 8 8
  // 注：lower_boundのポインタを参照すること
  }
}

出力結果

<span style="font-size: 80%">0
1
1
2
2
3
3
4
4
5
16345760
16345764
16345764
16345768
16345768
16345772
16345772
16345776
16345776
16345780
0
2
2
4
4
6
6
8
8
0</span>

array[0]をarray[1]に変えた場合の出力結果