정수를 컨테이너로 사용하기

주의: undefined behavior를 다룹니다.

C++20 이후에는 ranges::lower_bound, ranges::upper_bound를 사용하면 됩니다.

 

ps에서, 정수를 자체를 반복자로 사용할 수 있다면 정수 영역에 대한 이분 탐색을 한다던가, 복사를 할 수 있다.

그럼 이에 맞게 반복자 클래스를 만들어서 정수를 적당히 감싸면 되지 않을까? 소스를 보자

class VI
{
    ll _N;
public:
    using iterator_category = random_access_iterator_tag;
    using difference_type   = ll;
    using value_type        = ll;
    using pointer           = ll*;
    using reference         = ll&;
    VI(ll N):_N(N) {}
    ll operator*() { return _N * (_N+1) / 2; }
    operator ll&() { return _N; }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll S;
    cin >> S;

    cout << --upper_bound(VI(1),VI(1<<17),S);
}

하지만 이건 너무 길다. ps만 아니었다면 이걸 좀 더 일반화하여 라이브러리로 만들 수 있겠지만, 외우기도 어렵고 그저 이분 탐색을 기억하는 게 낫다.

 

좀 더 생각해보자면, 반복자를 사용하는 함수들중 일부는 어떻게 평가하면 좋을지 함수를 인자로 받고 있다. 예를 들면

upper_bound(begin, end, compare_function);
transform(begin, end, dest_begin, transform_function);
all_of(begin, end, predicate_function);
max_element(begin, end, compare_function);

.. 등등의 마지막 인자 처럼

즉, 꼭 평가 함수를 객체에 정의할 필요는 없다.

제공하는 람다에서, 역참조된 값을 다시 참조하여 반복자를 구한 후, 평가하면 된다.

f(begin(container), end(container), process);

를

f(
	(char*)integer_begin,
	(char*)integer_end,
	// 람다에서 기존 process 함수를 캡쳐
	[process](char& dereferenced){
		return process((integer_type)&dereferenced);
	}
);

로 바꿔보자. 다음은 실제로 적용해본 예시들이다.

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    using ll = long long;

    // [0, 10) 에서 x^2 출력하기
    transform(
        (char*)0,
        (char*)10,
		// back_inserter을 이용하면, 벡터에 넣는 것도 가능하다.
        ostream_iterator<ll>(cout, " "),
        [](char& pv){
			// 이터레이터를 참조(*)한 값이 나오므로, 역참조(&)를 통해 값을 복원한다.
            auto v = (ll)&pv;
            return v*v;
        }
    );

    cout << "\n=========\n";

    // 제곱이 26이상인 최소 n 이분 탐색
    cout << (ll)lower_bound(
        (char*)0,
        (char*)10,
        0, // 더미값, 원래는 찾고자하는 값이 들어가야 하지만 람다가 탐색 조건을 알기 때문에 괜찮다.
        [](char& pv, int){
            auto v = (ll)&pv;
            return v*v < 26;
        }
    );
}

#if 0
output
0 1 4 9 16 25 36 49 64 81 
=========
6
#endif

문제에 적용한 것들

http://boj.kr/1866af063f2841fb80aa828b9f769c54

http://boj.kr/9fd6dd42e0a1481c9dc06335ba8407eb

공유 소스 보기

 

주의사항

정수를 포인터로 변환하므로, 포인터에서도 begin < end를 만족해야 STL의 함수들이 잘 작동한다.

즉, 포인터가 8바이트인 환경이라면, long long처럼 쓰면 되지만 4바이트인 환경에서는 long long처럼 쓰면 포인터에서 오버플로가 발생하므로 안된다.