[C++] Sequence Container (Vector, Deque, List, Queue, Stack)

iterator

 

• 포인터와 상당히 비슷하며, 컨테이너에 저장되어 있는 원소들을 참조할 때 사용
• 알고리즘 마다 각기 다른 방식으로 컨테이너를 훑어가기 때문에, 반복자에도 여러가지 종류가 있음.
• iterator는 실제 값이 없는 end() 위치를 가질 수 있다.

 

• iterator를 기반으로 하는 insert, erase 함수는 iterator 값을 반환한다

vector<int> a;
auto it = a.end();

for(int i = 0; i < 10; i++) {
	it = a.insert(it, i); // 요소 삽입 후 해당 지점의 iterator값을 반환
    }
    
for(it x: a) {
	cout << x << ',';
    }
cout << endl;

compile result) 9, 8 ,7, 6, 5, 4, 3, 2, 1

insert 함수는 입력받은 좌측에 요소를 삽입한다.

 

 

Container별 차이점

 

• vector, deque에서의 insert, erase는 O(n) (시간초과 가능성↑)
• list에서의 insert, erase는 O(1)
• list에서의 iterator는 증감연산자(++/--) 만 지원 한다.

 

vector<int> a(2);
deque<int> b(2);
list<int> c(2);

vector<int>::iterator ia;
deque<int>::iterator ib;
list<int>::iterator ic;

ia = a.begin();
ib = b.begin();
ic = c.begin();

ia++;
ib++;
ic++;

--ia;
--ib;
--ic;

ia = a.begin() + 1;
ib = b.begin() + 1;
//ic = c.begin() + 1; << ERROR;

 

list 에서 iterator의 +/- 주소 연산이 불가능하다.

 

why?) list는 논리적 연결 구조이기 때문에 물리적 주소 이동 개념인 주소 연산이 불가능.

 

 

vector<int> a = {1,2,3,4,5};
deque<int> b = {5,4,3,2,1};
list<int> c = {10,20,30,40,50};

int i;
for(i = 0; i < a.size(); i++) cout << a[i] << ',';
cout << '\n';

for(i = 0; i < b.size(); i++) cout << b[i] << ',';
cout << '\n';

//for(i=0; i < c.size(); i++) cout << c[i] << ','; << ERROR

• vector, deque는 일반 배열 형태로 표현 가능.
• list는 일반 배열 형태로 표현 불가능

 

 

 

Vector

• #include <vector>
• 자동으로 메모리가 할당되는 배열
• 길이를 변경할 수 있는 배열

 

선언 >> vector<data type> 변수명;

vector<int> v1; // 길이가 0인 벡터
vector<int> v2(10); // 길이가 10인 벡터
vector<int> v3(15, 1); // 길이가 15이고, 초기값이 '1'인 벡터
vector<int> v4 = {1, 2, 3, 4, 5};

 

Vector 멤버 함수

• vector<int> v 라고 가정.
• n은 임의의 숫자.

 

v.front() : 0번째 요소의 값 참조.

v.back() : 마지막 요소의 값 참조.

v.push_back(n) :  마지막 원소 뒤에 n 삽입.

v.pop_back() : 배열 마지막 요소 제거. 

v.claer() : 모든 원소를 제거. 메모리는 남아 있음.

v.resize(n) : 크기를 n으로 변경함. 더 커졌을 경우 디폴트 값 0 으로 초기화.

v.size() : 원소 갯수를 리턴함.

v.empty() : vector의 empty 유무를 리턴함.

 

v.begin() : 첫번째 원소를 가리킴 (iterator)

v.end() : 마지막의 다음을 가리킴 (iterator)

v.insert(x,y,z) : x번째 위치에 y개의 z값을 삽입함.

v.erase(iterator) : iterator가 가리키는 원소를 제거함.

v.erase(start,end) : start이상 부터 end 미만까지 원소 제거함.

 

 

vector<int> v = {1,2,3,4,5};  // [1,2,3,4,5]
v.push_back(6)                // [1,2,3,4,5,6]
v.pop_back()                  // [1,2,3,4,5]
v.clear()                     // []
v.resize(5)                   // [0,0,0,0,0]

vector<int> v = {1,2,3,4,5};               // [1,2,3,4,5]
cout << "size = " << v.size() << endl;     // size = 5
cout << "empty = " << v.empty() << endl;   // empty = 0 (false)

v.claer();
cout << "empty = " << v.empty() << endl;   // empty = 1 (true)

vector<int> v = {1,2,3,4,5};               // [1,2,3,4,5]
cout << "front = " << v.front() << endl;   // front = 1
cout << "v[1] = " << v[1] << endl;         // a[1] = 2 : 일반 배열처럼 사용 가능
cout << "back = " << v.back() << endl;     // back = 5

vector<int> v = {1,2,3};               // [1,2,3]
auto it = v.begin();				   // it = v.begin (맨 앞 요소 가리킴)
v.insert(it, 4);					   // [4,1,2,3]
it = v.begin() + 1;                    // it = v.begin + 1 (맨 앞에서 +1 가리킴)
v.insert(it, 5, 0);                    // [4,0,0,0,0,0,1,2,3]
it = v.begin() + 2;                    // it = v.begin + 2 (맨 앞에서 +2 가리킴)
vector<int> a = {10, 20}               // 임의의 새로운 벡터 생성.
v.insert(it, b.begin(), b.end());      // [4,0,10,20,0,0,0,0,1,2,3]

vector<int> v = {1,2,3,4,5};               // [1,2,3,4,5]
v.erase(v.begin()+2);                      // [1,2,4,5]
v.erase(v.begin()+1, v.begin()+3);         // [1,5]

 

 

deque(덱)

 

• #include <deque>
• vector의 단점을 보완하기 위해 만들어진 container
• 배열기반의 구조이며, 여러개의 메모리 블록을 할당하고 하나의 블록처럼 여기는 기능 제공.
• 데이터의 삽입과 삭제가 front와 back에서 이루어 질 수 있음.
• vector의 멤버 변수와 거의 유사함. vector에서도 90% 이상 사용

 

선언 >> deque<data  type> 변수명;

deque <int> d; // 비어있는 deque를 생성.
deque <int> d(10); // default 값으로 초기화 된 10개의 원소를 가진 d 생성.
deque <int> d(10,4); // 4의 값으로 초기화 된 10개의 원소를 가진 d 생성.

 

deque의 멤버 함수

deque<int> d 라고 가정.

n은 임의의 숫자

 

• d.push_front(n) :  d의 첫 번째 원소 앞에 n을 삽입
• d.pop_front() : d의 첫 번째 원소를 제거
• d.push_back(n) : d의 마지막 원소 뒤에 n을 삽입
• d.pop_back() : d의 마지막 원소를 제거
• d.assign(x,y) : x의 값으로 y개의 원소 할당
• d.at(index) : index번째 원소를 참조 *유효범위 점검 o, 속도 느림
• d[index] : index번째 원소를 참조 *유효범위 점검 x, 속도 빠름
• d.front() : 첫 번째 원소를 참조
• d.back() : 마지막 원소를 참조
• d.clear() : 모든 원소를 제거.
• d.size() : 원소의 개수를 리턴
• d.insert(x,y,z) : x번째 위치에 y개의 z를 삽입. 삽입 시 앞 뒤 원소 개수를 비교하여 적은 쪽으로 미루어 삽입.
• d.insert(x,y) : x번째 위치에 y값을 삽입. 삽입한 곳의 iterator 반환
• d.erase(iter) : iter가 가리키는 원소 제거. 제거 후 앞 뒤 원소 개수 판단하여 적은쪽으로 원소를 당겨 채움
• d.empty() : d의 empty 여부 반환 (true or false)
• d.rbegin() : 맨 마지막원소를 첫번째 원소 처럼 가리킴. iterator와 사용.
• d.rend() : 맨 첫번째 원소의 "앞"을 마지막 원소의 "다음" 처럼 가리킴. iterator와 사용
• d2.swap(d1) : d1과 d2를 바꿈.

deque<int> d;
d.push_back(1);   // [1]
d.push.front(2);  // [2,1]
d.push.back(3);   // [2,1,3]
d.pop_back();     // [2,1]
d.pop_front();    // [1]

 

 

List

• 각각의 요소가 연결된 자료 구조
• array, vector, deque는 중간에 데이터 삽입/삭제 시 데이터 재정렬 때문에 O(n)
• list는 중간 고리(link) 만 변경 연결하면 되는 구조 O(1)
• 원소를 탐색할 때 임의접근 반복자는 불가능, 양방향 반복자(++, --) 를 이용하여 탐색
• 멤버 함수를 사용하여 양방향 삽입, 삭제 가능, 노드 중간에 삽입, 삭제도 가능.

 

선언 >> list<data type> 변수 이름;

list<int> l;
list<string> l;

 

멤버 함수

-  list<int> l 로 선언 했다고 가정.

-  n은 임의의 숫자

- 이전 게시물의 중복되는 함수들은 작성하지 않았음. 유용한 함수 위주

• l.remove(n) : n과 같은 원소를 모두 제거
• l.remove_if(bool) : 단항 조건자 bool에 해당하는 원소를 모두 제거
• l.reverse : 원소들의 순차열을 뒤집음.
• l.sort() : 모든 원소를 오름차순으로 정렬. 파라미터로 이항조건자가 오면 그 기준으로 정렬

 

list<int> l = {2, 1, -5, 4, -3, 6, -7};   // 2 1 -5 4 -3 6 -7

l.sort();                                 // -7, -5, -3, 1, 2, 4, 6
l.sort(greater<int>());                   // 6, 4, 2, 1, -3, -5, -7
l.sort([](int &u, int &v) {               // 1, 2, -3, 4, -5, 6, -7
	return abs(u) < abs(v);
});

l.reverse();                              // -7, 6, -5, 4, -3, 2, 1

 

Stack

 

- #include <stack>

- LIFO(Last in First out) 방식. (먼저 들어간 자료가 나중에 나옴)

- 재귀적 함수를 호출할 때 사용

- 그래프의 깊이 우선 탐색(DFS)에서 사용

 

선언)) stack<Data Type> 변수이름;

내부 컨테이너 구조를 바꾸는 형식은 stack<Data Type, Container Type> 변수이름;

stack<int> st;
stack<string> st;

stack<int, list<int>> st;
stack<stack, vector<string>> st;

 

주요 함수

 

• stack.push(value) : value를 삽입함.
• stack.top() : 맨 위에 있는 인자 반환.
• stack.pop() : top이 가리키는 value를 삭제 함
• stack.empty() : 스택의 empty 여부를 true or false로 반환함.

stack<int> s1;

for(int i = 1; i <= 5; i++) s1.push(i);

for(int i = 0; i < s1.size(); i++) {
	cout << s1.top() << ',';                ///  5,4,3,
    s1.pop();
}
cout << endl;

cout << "s1.size() = " << s1.size() << endl; //  s1.size() = 2

for(int i = 10; i >= 6; i--) s1.push(i);
cout << "size = " << s1.size() << endl;      //size = 7
cout << "empty = " << s1.empty() << endl;    //empty = 0

while(!s1.empty() {
	cout << s1.top() << ',';
    s1.pop();                                // 6,7,8,9,10,2,1,
}

cout << endl;

cout << "size = " << s1.size() << endl;      // size = 0
cout <, "empty = " << s1.empty() << endl;    // empty = 1

 

기본 자료형

- stack의 기본 자료 구조(defalut)는 deque.

 

deque<int> d = {1,2,4,5,3};
stack<int> s1(d);
for(int i = 0; i < 5; i++)  {
	cout << s1.top() << ',';              // 3,5,4,2,1
    s1.pop();
}
cout << endl;

vector<int> v = {5,4,3,2,1};
stack<int, vector<int>> s2(v);
for(int i = 0; i < 5; i++) {
	cout << s2.top() << ',';              // 1,2,3,4,5
    s2.pop();
}
cout << endl;

list<int> l = {1,3,2,4,5};
stack<int, list<int>> s3(l);
for(int i = 0; i < 5; i++) {
	cout << s3.top() << ',';              // 5,4,2,3,1
    s3.pop();
}
cout << endl;

 

Queue

• #include <queue>
• FIFO(First in, First out) 방식으로 동작
• deque와 list container에 붙어서 사용. (vector 는 불가능 / 앞에서 빼주는 기능 지원 x)
• BFS(너비우선탐색)

 

선언)) queue <Data Type> 변수이름;

내부 컨테이너 구조를 바꾸는 형식은 queue <Data Type, Container Type> 변수이름;

queue<int> q;
queue<string, list<string>> q;

 

주요 함수

 

• queue.push(value) : 맨 뒤에 value를 집어 넣는다.
• queue.front() : 맨 앞의 원소를 참조
• queue.back() : 마지막 원소를 참조
• queue.pop() : 맨 앞에 있는 원소를 삭제

deque<int> d = {1,2,4,5,3};
queue<int> q(d);

for(int i = 0 ; i < 2; i++) {
	cout << q.front() << ',' >> q.back() << endl;    /// 1,3
    q.pop();										 /// 2,3			
}

cout << "size = " << q.size() << endl;               /// size = 3
cout << "size = " << q.empty() << endl;              /// empty = 0

 

priority_queue (우선순위 큐)

• #include <queue>
• 정렬기준 기본값은 내림차순 ( 높은 수를 위에 배치)
• vector container 기반으로 설정 되어 있음.

 

기본 생성자 )) priority_queue <Data Type> 변수이름;

내부 컨테이너 변경)) priority_queue <Data Type, Container Type> 변수이름;

정렬 기준 변경 )) priority_queue <Data Type, Container Type, 정렬기준> 변수 이름;

 

priority_queue<int> pq;
priority_queue<int, deque<int>> pq;
priority_queue<int, vector<int>, greater<int>> pq;