[C++] STL 벡터(vector), 리스트(list), 덱(deque) 그리고 반복자

본 글은 씹어먹는 C++(https://modoocode.com/223)를 참고하여 여기서 내가 모르고 새로운 부분을 정리하는 용도로 작성했다.

나중에 c++ 문제 풀 때 또 모르면 참고하려고!!!

 

 

 

 

반복자

: 반복자는 컨테이너에 iterator 멤버 타입으로 정의되어 있습니다. 

 

begin() 함수는 예상했던 대로, vector 의 첫번째 원소를 가리키는 반복자를 리턴합니다. 
그런데, 흥미롭게도 end() 의 경우 vector 의 마지막 원소 한 칸 뒤를 가리키는 반복자를 리턴하게 됩니다. 

 

이에 여러가지 이유가 있겠지만, 가장 중요한 점이 이를 통해 빈 벡터를 표현할 수 있다는 점입니다. 만일 begin() == end() 라면 원소가 없는 벡터를 의미하겠지요. 
만약에 vec.end() 가 마지막 원소를 가리킨다면 비어있는 벡터를 표현할 수 없게 됩니다.

 

 

벡터(vector)

참조 : https://yeunhwa.tistory.com/entry/%ED%95%84%EC%9E%90%EA%B0%80-C-%EC%97%90%EC%84%9C-%EC%A3%BC%EB%A1%9C-%EC%82%AC%EC%9A%A9%ED%95%98%EB%8A%94-Vector-%EB%A7%B4%EB%B2%84-%ED%95%A8%EC%88%98-%EB%8C%80%ED%95%9C-%EC%84%A4%EB%AA%85

vector 초기화

• vector<자료형> 변수명 : 벡터 생성

• vector<자료형> 변수명(숫자)  :  숫자 크기만큼 벡터 생성(0으로 초기화)

• vector<자료형> 변수명 = {변수1, 변수2, 변수3...} : 백터 생성 후 변수들로 초기화

• vector<자료형> 변수명[] =  {{변수1, 변수2}, {변수3, 변수4}} : 벡터 배열(2차원 배열) 선언과 초기화(열은 고정, 행은 가변)

• vector<vector<자료형> 변수명 : 2차원 배열 생성(열, 행 모두 가변)

• vector<자료형>변수명.assign(범위, 초기화할 값) : 벡터

vector 접근(조회)하는 방법

std::vector vec;
// < 벡터 접근하는 방법 >
// 1. 반복자
for (std::vector::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
  std::cout << *itr << std::endl;
}
// 2. size_type
for (std::vector::size_type i = 0; i < vec.size(); i++) {
	std::cout << *itr << std::endl;
}
// 3. int
for (int i = 0; i < vec.size(); i++) {
	std::cout << *itr << std::endl;
}

여기서 반복자 itr은 실제 포인터가 아니고 * 연산자를 오버로딩해서 마치 포인터 처럼 동작하게 만든 것입니다. 
* 연산자는 itr 이 가리키는 원소의 레퍼런스를 리턴합니다.

 

vector 추가(삽입), 삭제

// vec[2] 앞에 15 추가
  vec.insert(vec.begin() + 2, 15);
// vec[3] 제거
  vec.erase(vec.begin() + 3);

각 컨테이너별로 내부적인 구조가 다르기 때문에 삽입, 삭제 방식도 컨테이너별로 다를 수밖에 없다. 그래서 삽입, 삭제 함수는 일반 알고리즘으로 제공되기보다는 컨테이너의 멤버 함수로 제공된다. vector에 멤버 타입으로 insert(), erase()가 정의되어 있다.

물론 vector 라고 만능은 아닙니다. 맨 뒤에 원소를 추가하거나 제거하는 것은 빠르지만, 임의의 위치에 원소를 추가하거나 제거하는 것은 O(n)으로 느립니다. 왜냐하면 어떤 자리에 새로운 원소를 추가하거나 뺄 경우 그 뒤에 오는 원소들을 한 칸 씩 이동시켜 주어야만 하기 때문이지요. 

 

▶ 임의의 위치 원소 접근 ([], at) : O(1)

▶ 맨 뒤에 원소 추가 및 제거 (push_back/pop_back) : amortized O(1); (평균적으로 O(1) 이지만 최악의 경우 O(n) )

▶ 임의의 위치 원소 추가 및 제거 (insert, erase) : O(n)

 

for (; itr != end_itr; itr++) {
  if (*itr == 20) {
    vec.erase(itr);
  }
}

※ 위 코드는 문제가 있다. 컨테이너에 원소를 추가하거나 제거하게 되면 기존에 사용하였던 모든 반복자들을 사용할 수 없게된다.

 

vector 기본 함수

참고)) https://twpower.github.io/77-how-to-use-vector-in-cpp

 

iterator(반복자)

• begin() : beginning iterator를 반환

• end() : end iterator를 반환

추가 및 삭제

• push_back(element) : 벡터 제일 뒤에 원소 추가

• pop_back() : 벡터 제일 뒤에 원소 삭제

조회

• [i] : i번째 원소를 반환

• at(i) : i번째 원소를 반환

• front() : 첫번째 원소를 반환

• back() : 마지막 원소를 반환

기타

• empty() : 벡터가 비어있으면 true 아니면 false를 반환

• size() : 벡터 원소들의 수를 반환

 

범위 기반 for 문 (range based for loop)

위와 같이 컨테이너의 원소를 for 문 으로 접근하는 패턴은 매우 많이 등장하는데, C++ 11 에서 부터는 이와 같은 패턴을 매우 간단하게 나타낼 수 있는 방식을 제공하고 있다.

// range-based for 문
  for (int elem : vec) {
    std::cout << "원소 : " << elem << std::endl;
  }

 

---

리스트(list)

참조 : https://modoocode.com/223

리스트(list) 의 경우 양방향 연결 구조를 가진 자료형이라 볼 수 있다.

따라서 vector 와는 달리 임의의 위치에 있는 원소에 접근을 바로 할 수 없습니다. list 자체에서는 시작 원소와 마지막 원소의 위치만을 기억하기 때문에, 임의의 위치에 있는 원소에 접근하기 위해서는 하나씩 링크를 따라가야 합니다.

 

• vector와 다른 장점: 원소 추가/삭제 할 때  O(1) 으로 매우 빠르게 수행될 수 있다.

• vector와의 또 다른 점은 반복자는 오직 한 칸 씩 밖에 움직일 수 없습니다.(반복자 연산이 제한된다)

  itr++    // itr ++
  itr--  // --itr 도 됩니다.
  
  itr + 5  // 불가능!

또한 리스트는 vector와 다르게, 원소를 지워도 반복자가 무효화 되지 않습니다. 왜냐하면, 각 원소들의 주소값들은 바뀌지 않고 그대로 있기 때문이죠!!

 

list 기본 함수

참고)) https://twpower.github.io/78-how-to-use-list-in-cpp

 

iterator(반복자)

• begin() : beginning iterator를 반환

• end() : end iterator를 반환

추가 및 삭제

• push_front(element) : 리스트 제일 앞에 원소 추가

• pop_front() : 리스트 제일 앞에 원소 삭제

• push_back(element) : 리스트 제일 뒤에 원소 추가

• pop_back() : 리스트 제일 뒤에 원소 삭제

• insert(iterator, element) : iterator가 가리키는 부분 “앞”에 원소를 추가

• erase(iterator) : iterator가 가리키는 부분에 원소를 삭제

조회

• *iterator : iterator가 가리키는 원소에 접근

• front() : 첫번째 원소를 반환

• back() : 마지막 원소를 반환

기타

• empty() : 리스트가 비어있으면 true 아니면 false를 반환

• size() : 리스트 원소들의 수를 반환

---

덱(deque)

 

참조 : http://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS3942847236

deque의 자료구조

 덱의 자료구조는 Queue와 다른 점으로 삽입과 삭제를 한쪽이 아닌 앞, 뒤 양쪽에서 할 수 있다는 것이다. 일종의 Queue와 같습니다. 따라서 Deque는 Stack과 Queue의 장점을 모은 것으로 FIFO 방식과 LIFO 방식 둘 다 사용할 수 있습니다.

 

deque의 기본 원리

const int MX = 1000005;
int dat[2 * MX + 1];
int head = MX, tail = MX;

 

MX = 3인 경우

 

초기화 모습

 

push_front()를 한 모습

 

push_back()를 한 모습

 

push_front()와 push_back()를 하여 가득찬 모습

위의 그림을 보면 왜 head와 tail이 0이 아닌 MX에서 출발해야하는지 이유를 알 수 있다.

덱은 양옆으로 추가/삭제가 되므로 MX만큼 추가/삭제를 하고 싶다면 head와 tail을 0이 아닌 MX에서 출발해야 한다.

또한 배열의 길이를 MX*2 + 1로 한 이유는 다 찼을 때 tail이 있을 마지막 한 칸이 필요하기 때문이다(그림에서는 6번째 칸에 해당한다)

 

deque의 특징

1. 크기가 가변적이다.

 : 리스트와 같이 데이터를 담을 수 있는 크기가 가변적이다.

-> 그 이유는 덱의 내부적 원리를 이해해야하는데 https://modoocode.com/223 를 참고하여 이해해보도록 하자. (다소 어렵다. 처음에 와닿지가 않는다.)

2. 앞과 뒤에서 삽입과 삭제가 좋다.

3. 중간에 데이터 삽입, 삭제가 용이하지 않다.

 : 데이터를 중간에 삽입하거나 삭제하는 것은 피해야 합니다. 삽입과 삭제를 중간에 한다면 삽입하거나 삭제한 위치 앞뒤 데이터를 모두 이동해야 합니다.

4. 구현이 쉽지 않다.

5. 랜덤 접근이 가능하다.

 

 

아래는 vector와 비교한 덱에 대한 내용이다.

deque는 전체적으로 멤버 함수의 기능이나 사용 방법이 vector와 거의 같습니다.

vector는 삽입과 삭제를 뒤(back)에서만 해야 성능이 좋지만, deque는 삽입과 삭제를 앞과 뒤에서 해도 좋으며 앞뒤 삽입, 삭제 성능도 vector보다 좋습니다.

하지만, deque는 앞뒤에서 삽입, 삭제하는 것을 제외한 다른 위치에서의 삽입과 삭제는 vector보다 성능이 좋지 않습니다.

 

deque의 기본 함수

: vector와 비슷한 함수들

 

iterator(반복자)

• begin() : beginning iterator를 반환

• end() : end iterator를 반환

추가 및 삭제

• push_back(element) : 벡터 제일 뒤에 원소 추가

• pop_back() : 벡터 제일 뒤에 원소 삭제

• push_front(element)

• pop_font()

조회

• [i] : i번째 원소를 반환

• at(i) : i번째 원소를 반환

• front() : 첫번째 원소를 반환

• back() : 마지막 원소를 반환

기타

• empty() : 벡터가 비어있으면 true 아니면 false를 반환

• size() : 벡터 원소들의 수를 반환

 

deque의 기본코드

아래 코드는 전체적인 덱을 이해하기 위해 쳐본 코딩이다. 코딩실력은 눈으로 보는 것보다 치는게 훨씬 빨리 느닌깐!

#include <iostream>
#include <deque>

using namespace std;

int main() {
	deque<int> deque1, deque2;
	deque<int> ::iterator itr;

	deque1.push_front(100);
	deque1.push_back(200);
	deque1.push_back(300);
	deque1.push_front(400);  // 400, 100, 200, 300

	cout << "< push_front & push_back >" << '\n';
	for (int i = 0; i < deque1.size(); i++) {
		cout << deque1[i] << " ";
	}
	cout << '\n';

	cout << "< pop_front & pop_back >" << '\n';
	deque1.pop_front();
	deque1.pop_back();
	for (int i = 0; i < deque1.size(); i++) { //100, 200
		cout << deque1[i] << " ";
	}
	cout << '\n';

	cout << "< 반복자로 접근 >" << '\n';
	cout << deque1[0] << '\n';
	itr = deque1.begin();  //100
	++itr;
	cout << *itr << '\n';  //200

	cout << "< front % back >" << '\n';
	cout << deque1.front() << '\n';  //100
	cout << deque1.back() << '\n';   //200

	cout << '\n' << "< insert >" << '\n';
	itr = deque1.begin();
	deque1.insert(itr, 500);   //500, 100, 200

	itr = deque1.begin();  // !!!중요 : insert()되어서 다시 itr 지정하기!!!
	++itr;
	deque1.insert(itr, 3, 700);  //500, 700, 700, 700, 100, 200
	for (int i = 0; i < deque1.size(); i++) {
		cout << deque1[i] << " ";
	}
	cout << '\n';

	deque2.push_back(20);
	deque2.push_back(30);
	deque2.push_back(40);
	itr = deque1.begin();
	deque1.insert(++itr, deque2.begin(), deque2.end()); //500, 20, 30, 40, 700, 700, 700, 100, 200
	for (int i = 0; i < deque1.size(); i++) {
		cout << deque1[i] << " ";
	}
	cout << '\n';

	cout << '\n' << "< erase >" << '\n';
	deque1.erase(deque1.begin(), deque1.begin() + 4); //700, 700, 100, 200
	for (int i = 0; i < deque1.size(); i++) {
		cout << deque1[i] << " ";
	}
	cout << '\n';

	cout << "< clear >" << '\n';
	deque1.clear();

	cout << "< empty >" << '\n';
	cout << (deque1.empty() ? "true" : "false") << '\n';
}
                                           

 

 

---

컨테이너

그래서 어떤 컨테이너를 어떤 경우에 쓰는게 좋을까?

 

▶일반적인 상황에서는 그냥 벡터를 사용한다 (거의 만능이다!)

만약에 맨 끝이 아닌 중간에 원소들을 추가하거나 제거하는 일을 많이 하고, 원소들을 순차적으로만 접근 한다면 리스트를 사용한다.

▶ 만약에 맨 처음과 끝 모두에 원소들을 추가하는 작업을 많이하면 덱을 사용한다.