[C++] std::advance(),std::distance() 임의 접근 생성자

알고리즘 문제를 풀다 재밌는 함수를 발견했습니다

 

vector와 같은 ArrayList 형태의 자료구조의 대표적인 장점은 값에 임의로 접근할 수 있다는 것입니다.

vector<int> a;

a.push_back(1);

a.push_back(2);

a.push_back(3);

 

위 코드에서 a는 {1,2,3}의 형태의 data를 가지고 있습니다.

이때 a[1] 혹은 a.at(1)을 사용한다면 1번째 혹은 마지막 값을 거치지 않고 바로 2번째 값인 2에 접근할 수 있습니다.

 

하지만 map이나 list와 같이 LinkedList 자료형은 이러한 방식으로 data에 접근이 불가능합니다.

 

하지만 오늘 살펴볼 std::advace()을 사용한다면 LinkedList에서도 임의로 값에 접근할 수 있습니다.

 

---

std::advance()은 std::advance(_InIt& _Where, _Diff _Off)와 같은 형태로 사용되며 총 2개의 인자를 받습니다.

각 인자는 어디에서 시작하는지, 그로부터 얼마나 떨어졌는지를 나타냅니다.

std::unordered_set<int> set_element_;

auto start = set_element_.begin();
auto end = set_element_.end();
std::advance(start, 1);
std::advance(end, -3);

 

두 번째 값에는 양수와 음수 모두 사용될 수 있습니다.

---

std::distance()는  std::distance(InIt first, InIt last)와 같은 형태로 사용되며 총 2개의 인자를 받습니다.

이 함수를 호출한다면 first에서 last까지의 거리를 가지는지를 반환해 줍니다.

std::unordered_set<int> set_element_;

auto start = set_element_.begin();
auto end = set_element_.end();
std::distance(set_element_.begin(), set_element_.end());

 

 

함수의 반환값으로는 정수가 나옵니다.

 

한계

LinkedList에서 ArrayList의 장점을 사용할 수 있다면 정말 좋았겠지만

소개해드린 함수는 사용할 수 있는 것처럼 느끼게 해 주는데 그칩니다.

 

이는 advance함수의 내부를 살펴보면 알 수 있습니다.

 

advance 함수는 다음과 같이 구현되어 있습니다.

void advance(_InIt& _Where, _Diff _Off)

{

     for (;_Off > 0;--_Off) { ++_Where; }

     for (;_Off < 0;++_Off) { --_Where; }

}

 

결국 원하는 위치에 접근하기 위해서는 _Off의 크기만큼 반복문이 실행되기에 O(n)의 시간이 소요됩니다.

 

위 함수의 경우 코드를 간결하게 하기 위해 사용할 수 있으나 효율면에서는 좋지 못합니다.

따라서 임의 접근이 자주 필요한 경우에는 기존과 동일하게 ArrayList 형태의 자료구조를 사용해야 합니다.