vector upper_bound, lower_bound 사용 (C++)

배열에서, 특정 원소의 개수를 파악하는 것을 upper_bound 그리고 lower_bound를 활용해서 할 수 있다.

sort(x.begin(), x.end());
 
    vector<ll>::iterator low, high;
    for (int i = 0; i < x.size(); i++) {
        if (mp.find(x[i]) == mp.end()) {
            low = lower_bound(x.begin(), x.end(), x[i]);
            high = upper_bound(x.begin(), x.end(), x[i]);
            mp.insert({ x[i], high - low });
        }
    }

당연하게도 두 bound의 특징을 활용해서 특정 원소의 개수를 파악하기 위해서는 정렬이 필수적이다.

위 코드의 경우, low에는 처음으로 벡터의 원소가 x[i] 이상이 되는 원소의 iterator가 반환되고,

high에는 벡터의 원소중, 처음으로 x[i] 초과가 되는 원소의 iterator가 저장된다.

이때 high 혹은 low에서 x.begin()을 빼주면 몇번째 위치인지를 파악할 수 있는 것이고,

이 과정을 생략하고 high와 low의 차이를 구하면, 두 iterator의 위치 차이를 구할 수 있기 때문에, x[i]의 개수가 구해지는 것이다.