[ComputerScience] c++의 vector

이 게시글은

서울대학교 데이터사이언스대학원

조요한 교수님의

데이터사이언스 응용을 위한 컴퓨팅 강의를

학습을 위해 재구성하였습니다.

---

Container

 

element들을 담고있는 data structure들을

c++에서 지원하는데 이런 것들을 container라고 부른다

보통 vector, list, map, set, deque 등등이 있다

 

 

이 게시글에서 배워볼 것은 vector

 

vector

 

vector는 python의 list와 비슷하다

element들이 array처럼

연속적인 저장소에 저장되어있으며

random access가 가능하다

(index로 접근 가능)

 

그리고 요소들의 중간에

insertion과 deletion은 어렵겠지만

맨 뒤에 insert와 delete하는 것은 쉽다

 

element들이 계속 들어와서 현재 갖고있는

array공간에 넣을 수 없을 때

자동으로 resize되는데

이런 점은 string과 굉장히 비슷한 구조라고 할 수 있다

 

 

 

vector의 메모리 구조는 이렇다

데이터들은 heap에 저장되며

제일 처음을 가리키는 begin pointer와

제일 뒤를 가리키는 end pointer가 있고

size와 capacity 정보가 있다

 

 

벡터를 초기화하는 방법은 위와같다

#include <vector>로 헤더 선언해주고

vector에 담을 데이터들의 타입을

정의해줘야한다

 

int데이터들의 vector를 선언하려면

std::vector<int> vec1 = {1, 2, 3, 4, 5};

와 같이 선언해주면된다

 

그다음에 미리 정의되어있는

array로부터 vector를 생성하려면

std::vector<int> vec2(std::begin(arr), std::end(arr));

와 같이 선언해주면 된다

arr이라는 array의 처음값과 마지막값의

주소를 담는 vector인 vec2를 만들겠다는 뜻이다

 

std::vector<int> vec3(5, 100);

은 사이즈가 5인 벡터를 만든 뒤

100으로 초기화를 시켜라는 뜻이다

따라서 vec3은

{100, 100, 100, 100, 100}이 된다

 

 

vector에 element를 insertion하는 방법이다

push_back 메소드를 통해 vector의 가장 끝에

element를 추가할 수 있다

 

at(index)을 통해 특정 Index에 있는

원소를 가져올 수도 있다

 

 

 

vector에 element를 deletion하는 법이다

pop_back()을 하면 가장 마지막 element를 지울 수 있다

erase(index)를 하면 index에 위치한

element를 지울 수 있다

 

begin()은 하면 가장 첫번째 element를 가리키는데

거기서 +2를 해주면 첫번째에서

두개를 더 간 곳에 위치한 element를 가리킨다

 

따라서 vec.erase(vec.begin() + 2);라고하면

3번째에 있는 element가 지워지는 것이다

 

 

vector에서의 iteration이다

python의 for .. in 문이랑 비슷하다

for (int val : vec)으로 해주면

vec안에 있는 요소를 val로

접근할 수 있다

 

데이터 타입을 auto로 선언해주면

컴파일러가 알아서 추론해준다

 

 

vector에서 iterator를 사용하는 법이다

vector<int>::iterator it = vec.begin()

으로 iterator변수인 it을 선언해주고

for문을 통해 vec.end()와 같아지는 순간까지

it을 한개씩 커지게 해준다

 

따라서 ppt 사진에 있는 for문의 뜻은

vector의 처음부터 마지막까지 돌면서

element를 한 개씩 증가시킬거고

그 iterator가 가리키는 값의 주소로 들어가서

출력을 하겠다는 뜻이다

 

 

 

iterator는 pointer 변수와

비슷한 개념이라고 생각하면 좋다

 

vector, list, map과 같은

container들은 그들만의

iteratior type을 갖고있다

 

그래서 vector의 iterator를 선언할 때는

vector<int>::iterator라고

vector의 Iterator임을 선언해주는 것이다

 

iterator는 클래스일 때도 있고 raw pointer일 때도 있다고 한다

하지만 abstraction(추상화) 때문에

c++ 개발자가 어떨 때 Iterator인지

raw pointer인지 알 수 없도록 구현해놓은 것이라고 한다

 

결론적으로 iterator는 클래스일때도

raw pointer일 때도 있지만

c++를 이용하는 입장에서는 그걸 몰라도

작동이 되도록 구현이 되어있으니

그냥 pointer를 쓰는 방식과 비슷하게

사용하면 큰 문제는 없다고 한다

 

 

 

auto로 데이터타입을 지정해도 컴파일러는

it이 Iterator란 것을 자동으로 추론할 수 있따

it = vec.begin()이므로

it은 vec의 첫번쨰 원소를 가리키는 iterator이다

 

vec.end()는 vec의 마지막인 5가 아닌

5 다음의 주소를 가리킨다

따라서 위 for문에서

it != vec.end()까지 증가시키라고하면

마지막 원소인 5까지 출력한 뒤

for문을 끝낼 수 있는 것이다

 

 

 

vector에서 특정 element를 찾아보자

우선 헤더에 #include <algorithm>을 선언해준다

 

3이라는 element를 찾고싶으면

std::find(vec.begin(), vec.end(), 3)

이렇게 해주면 된다

그럼 iterator를 이용해 vec을

처음부터 끝까지 돌면서 3이라는 원소를 찾는다

 

만약에 3을 찾으면 3을 가리키는

iterator를 반환하고

3을 찾지 못하면

vec.end()를 반환한다

 

그래서 3이라는 원소가 vec에 있는지없는지

확인하기 위해서는

if (it != vec.end())문을 통해서

체크해줘야한다

 

또한 find문을 통해서 3이라는 원소를

가리키는 iterator를 찾았을 때

vec에서 3이라는 원소의 index를 앙ㄹ고싶다면

std::distance(vec.begin(), it)

을 사용하면 index를 찾을 수 있다

 

vec의 가장 처음 iterator부터

3이 있는 Iterator까지의

거리를 리턴하기 때문이다

 

vec에서 3은 처음보다 2번째

떨어진 곳에 있고

따라서 std::distance(vec.begin(), it)은

2를 반환하고 이는 vec에서 3의 인덱스이다

 

 

 

std::accumulate를 vector에서 이용하는 법을 알아보자

accumulate는 말 그대로 축적해주는 함수이다

축적을 하면서 무언가를 더할수도, 곱할수도, 나눌 수도 있고

어떤 특정 연산을 할 수도 있다

 

std::accumulate(vec.begin(), vec.end(), 0)

을 해주면

vec의 begin부터 end까지

원소가 쭉 더해져서 sum이 나온다

여기서 0은 seed값으로

초기값같은 느낌이라고 생각하면된다

 

0이 아닌 3이 있다면

전부 더한거에 3이 더해진 값이

sum에 저장되게 될 것이다

 

sum이 아닌 다른 연산을 해주고싶다면

accumulate의 네번째 인자로

custom함수를 넣어주면 된다