1. STL(Standard Template Library)
C++ 의 표준 템플릿 라이브러리 (STL) 은 간단하며 효율적인 도구이다. 보통 C++의 STL은 임의 타입의 객체를 보관할 수 있는 컨테이너(Container)와 컨테이너에 보관된 원소에 접근할 수 있는 반복자(Iterator), 그리고 반복자들을 가지고 일련의 작업을 수행하는 알고리즘(algorithm)을 의미한다.
여기서 컨테이너는 객체가 어떤 타입이든 자유롭게 사용할 수 있다는 것이다. int나 string 같은 일반적인 타입이 아니라 임의로 만든 클래스의 객체들이여도 라이브러리의 기능들을 모두 활용할 수 있다.
2. 벡터(Vector)
그 컨테이너 중에서도 오늘은 벡터(Vector)에 대해서 알아본다. 먼저, 벡터는 배열 처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너(Sequence Container)의 한 종류이다. 다른 예로는 list, deque가 있다.
벡터는 가변길이 배열로 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있고 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게 수행할 수 있다.
사용법은 다음과 같다. 먼저, vector 라이브러리를 include 시켜줘야 한다. 그리고, vector<타입> 변수 명; 과 같이 선언해준다. 임의의 원소에 접근하는 것은 배열처럼 [] 를 사용한다. 또한, 맨 뒤에 원소를 추가하거나 제거하기 위해서는 push_back 과 pop_back 함수를 사용하면 된다. 임의의 위치에 있는 원소에 접근은 로 수행하고 맨 뒤에 새로운 원소를 추가하거나 제거하는 것 역시 에 수행한다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
for(vector<int>::size_type i = 0; i < v.size(); i++) {
cout << "vector 의 " << i + 1 << " 번째 원소 : " << v[i] << endl;
}
return 0;
}
11번째 줄을 보면 size_type의 변수 i가 존재한다. 이는 벡터의 크기를 리턴하는 함수인 size가 리턴하는 값의 타입이 size_type 멤버 타입으로 정의되어있기 때문이다.
3. 벡터의 특성
맨 뒤에 원소를 추가하는 작업(push_back)은 정확히 시간복잡도로 따지면 분할상환의 뜻을 가진 amortized O(1)이라고 한다. 보통 벡터의 경우 현재 가지고 있는 원소의 개수 보다 더 많은 공간을 할당해 놓고 있기 때문이다. 예를 들어, 위의 예에서 원소의 개수가 3개지만 벡터는 이미 10가 정도 저장할 수 있는 공간을 미리 할당해 놓는 다는 것이다. 따라서, 새로운 원소를 추가해도 그냥 이미 할당된 공간에 그 원소를 쓰기만 하면 된다.
따라서 대부분의 경우에 원소의 추가, 삭제는 O(1)으로 이루어진다. 하지만, 할당된 공간을 다 채웠을 때는 얘기가 달라진다. 이 때는 새로운 큰 공간을 다시 할당하고, 기존의 원소들을 복사하는 수 밖에 없다.
이 경우 n 개의 원소를 모두 복사해야 하기 때문에 O(n)의 시간복잡도가 발생한다. 하지만 으로 수행되는 경우가 매우 적기 때문에, 전체적으로 평균을 내보았을 때 O(1)로 수행이 된다. 그림으로 설명하면 다음과 같다.
또한, 맨 뒤에 원소를 추가하거나 제거하는 것(O(1))은 빠르지만, 임의의 위치에 원소를 추가하거나 제거하는 것은 O(N)으로 느리다. 왜냐하면 어떤 자리에 새로운 원소를 추가하거나 뺄 경우 그 뒤에 오는 원소들을 한 칸 씩 이동시켜 줘야하기 때문이다. 따라서 이는 N번의 복사가 필요하다.
따라서, 어떠한 작업을 하냐에 따라서 속도차가 매우 크기 때문에 C++ 표준 라이브러리를 잘 사용하기 위해서는 내가 이 컨테이너를 어떠한 작업을 위해 사용하는지 정확히 인지해 적절한 컨테이너를 골라야 한다.
4. 순회(for)로 원소 접근하기
컨테이너를 순회(for)문으로 접근하는 경우가 많은데 이는 포인터와 같은 객체인 반복자(Iterator)를 사용하는 경우도 있고 C++ 11버전 부터는 범위 기반 for문을 제공한다. 순회문에 들어갈 매개변수는 컨테이너의 원소를 받을 변수와 컨테이너를 정의해주면 된다. 이것은 e 변수에 v[i]를 한 것과 같다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
for(int e : v) {
cout << "원소 : " << e << endl;
}
return 0;
}
5. 벡터의 생성자
#include <iostream>
#include <vector>
using namespace std;
int main() {
1. 빈 벡터 생성
vector<int> v;
2. 0으로 초기화 된 10개의 원소를 가지는 벡터 생성
vector<int> v(10);
3. 5로 초기화 된 10개의 원소를 가지는 벡터 생성
vector<int> v(10, 5);
4. v1 벡터를 복사해서 벡터 생성
vector<int> v(v1);
}
6. 벡터의 멤버변수
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
vector<int> v1;
1. v.front(); ==> 벡터의 첫 번째 원소를 참조한다.
2. v.end(); ==> 벡터의 마지막 원소를 참조한다.
3. v.push_back(2); ==> 벡터의 마지막 원소 뒤에 2를 추가한다.
4. v.pop_back(); ==> 벡터의 마지막 원소를 삭제한다.
5. v.size(); ==> 벡터의 원소의 개수를 리턴한다.
6. v.capacity(); ==> 벡터의 할당된 메모리의 크기를 리턴한다.
7. v.insert(2, 3); ==> 벡터의 2번째 위치에 3을 삽입하고 삽입한 곳의 iterator를 반환한다.
8. v.insert(2, 3, 4); ==> 벡터의 2번째 위치에 3개의 4를 삽입하고 삽입한 곳의 iterator를 반환한다.
9. v.swap(v1); ==> v 벡터와 v1 벡터의 요소와 capacity를 모두 바꿔준다.
}
7. 벡터 여러개 생성하기
#include <iostream>
#include <vector>
using namespace std;
int main() {
1. 벡터를 N개 생성
vector<int> v[3]; // v라는 벡터를 3개 생성
[비교] 벡터를 하나만 생성
vector<int> v1(3); // size가 3인 벡터를 1개 생성
2. 벡터 원소 넣기
v[0].push_back(1);
v[0].push_back(2);
v[1].push_back(1);
v[2].push_back(1);
v[2].push_back(2);
v[2].push_back(3);
3. 원소 접근
cout << v[0][2] << endl;
cout << v[1][1] << endl;
8. 벡터 Pair
#include <iostream>
#include <vector>
using namespace std;
int main() {
1. 동시에 Int 값을 넣을 수 있는 Pair 벡터 선언
vector<pair<int, int> > v[3]; // [주의] <pair<int, int> > 이 부분에서 끝에 띄어써야 함
2. 벡터 원소 넣기
v[0].push_back({3, 5});
v[0].push_back({2, 7});
v[1].push_back({1, 3});
v[1].push_back({5, 6});
v[2].push_back({2, 7});
3. 원소 접근
cout << v[1][1].first << " " << v[1][1].second << endl;
cout << v[0][0].first << " " << v[0][0].second << endl;
'알고리즘 & 자료구조 > C, C++ 공부' 카테고리의 다른 글
| 5. STL - 해시(map vs hash_map) (0) | 2020.09.24 |
|---|---|
| 4. C++ 프로그래밍 환경 구성하기 (0) | 2020.09.18 |
| 2. 동적 배열 할당하기(malloc) (0) | 2020.09.06 |
| 1. char형 데이터 int형으로 바꾸기 & char 배열 활용 (0) | 2020.09.02 |