[C++] 컨테이너, vector, iterator

컨테이너 (Container)

• 여러 개의 데이터를 저장하고 관리하는 클래스 또는 데이터 구조

순차 컨테이너 (Sequence Containers)

• 데이터를 순차적으로 저장하는 컨테이너
• 요소들의 저장 순서가 유지된다.
• 대표 컨테이너
  • vector → 동적 배열 (일반적으로 가장 많이 사용)
  • deque → 양방향 큐 (앞뒤로 빠르게 삽입/삭제 가능)
  • list → 이중 연결 리스트 (중간 삽입/삭제가 빠름)
  • array → 정적 배열 (고정 크기)
  • foward_list → 단일 연결 리스트 (메모리 절약)

연관 컨테이너 (Associative Containers)

• 데이터를 특정한 규칙 (정렬 또는 해시 기반)으로 저장하는 컨테이너
• 요소들의 저장 순서가 보장되지 않는다.
• 대표 컨테이너
  • set → 중복 없는 정렬된 집합 (레드 블랙 트리 기반)
  • map → 키-값 쌍을 저장하는 정렬된 연관 컨테이너 (레드 블랙 트리 기반)
  • multiset → 중복 허용 집합
  • multimap → 중복 키를 허용하는 맵
  • unordered_set → 정렬되지 않은 집합 (해시 기반)
  • unordered_map → 정렬되지 않은 맵 (해시 기반)

컨테이너 어댑터 (Container Adapters)

• 특정 컨테이너의 인터페이스를 제한하거나 변형하여 사용하도록 만든 컨테이너
• 내부적으로 vector, deque, list등을 사용한다.
• 대표 컨테이너
  • stack → 후입선출 (LIFO)
  • queue → 선입선출 (FIFO)
  • priority_queue → 우선순위 큐 (최대 힙 or 최소 힙)

컨테이너 특징

• 템플릿 기반 → 다양한 데이터 타입을 저장할 수 있다.
• 자동 메모리 관리 → 요소를 추가하면 자동으로 크기가 조정된다.
• STL 알고리즘과 함께 사용 가능 → sort, find 등과 조합하여 활용한다.
• 성능 차이 → vector vs list vs map 등 사용 목적에 따라 선택해야 한다.

Vector

• STL에서 제공하는 동적 배열 컨테이너
• 크기 조정 가능 → 동적 메모리 할당을 통해 크기가 자동으로 증가/감소
• 연속된 메모리 사용 → 빠른 임의 접근 / O(1)
• 끝에서 삽입/삭제 빠름
• 중간 삽입/삭제 비효율적 / O(N)
• STL 알고리즘과 쉽게 결합 가능 (sort, find등)
• 크기가 부족할 때 자동으로 크기를 2배씩 증가 → 불필요한 재할당 발생 가능성으로 인해
  reserve로 메모리 미리 할당 가능

#include <iostream>
#include <vector>

using namespace std;

int main() {
	vector<int> v;
	v.reserve(5);
	
	vector<int> v2(5); // 5개의 요소를 0으로 초기화
	vector<int> v3(5, 100) // 5개의 요소를 100으로 초기화
	
	vector<int> v4 = {1, 2, 3, 4, 5};
	vector<int> v5{10, 20, 30, 40};
	
	vector<int> v6(v5);
	vector<int> v7;
	v7 = v6;
}

요소 추가 및 제거

함수	설명
push_back(value)	끝에 요소 추가
pop_back()	끝 요소 제거
insert(it, value)	특정 위치에 요소 삽입
erase(it)	특정 위치 요소 삭제
clear()	모든 요소 제거
resize(n, value)	크기 변경 및 초기값 설정

#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    
    v.push_back(4); // {1, 2, 3, 4}
    v.pop_back();   // {1, 2, 3}
    
    v.insert(v.begin() + 1, 10); // {1, 10, 2, 3}
    v.erase(v.begin());          // {10, 2, 3}

    v.clear(); // 모든 요소 삭제
}

요소 접근

함수	설명
at(index)	안전하게 요소 접근 (범위 검사 O)
operator[]	빠르게 요소 접근 (범위 검사 X)
front()	첫 번째 요소 반환
back()	마지막 요소 반환

#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> v = {10, 20, 30};
    
    cout << v[1] << "\n";   // 20
    cout << v.at(1) << "\n"; // 20 (범위 검사 O)
    
    cout << v.front() << "\n"; // 10
    cout << v.back() << "\n";  // 30
}

크기 및 용량

함수	설명
size()	현재 요소 개수 반환
capacity()	할당된 메모리 크기 반환
empty()	비어 있는지 확인
shrink_to_fit()	capacity를 size에 맞게 줄임

#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> v = {10, 20, 30};
    
    cout << "Size: " << v.size() << "\n"; // 3
    cout << "Capacity: " << v.capacity() << "\n"; // 3
    cout << "Is empty? " << (v.empty() ? "Yes" : "No") << "\n"; // No
    
    v.clear();
    
    cout << "Size: " << v.size() << "\n"; // 0
    cout << "Capacity: " << v.capacity() << "\n"; // 3
    cout << "Is empty? " << (v.empty() ? "Yes" : "No") << "\n"; // Yes

    v.shrink_to_fit(); // 필요 없는 메모리 줄이기
}

vector.clear() 후에도 capacity()가 변하지 않는 이유

• vector::clear()는 벡터의 모든 요소를 제거하지만, 할당된 메모리는 그대로 유지하기 때문
• 메모리를 해제하지 않는 이유는 다시 데이터를 추가할 때 재할당 비용을 줄이기 위함.

Iterator

• C++의 STL에서 컨테이너 요소들을 순회할 수 있도록 하는 객체이다.
• 배열과 유사하지만, 포인터처럼 동작하며 더 강력한 기능을 제공한다.

#include <iosream>
#include <vector>

using namespace std;

int main() {
	vector<int> v{1,2,3,4,5};
	
	vector<int>::iterator it = v.begin();
	vector<int>::iterator itEnd = v.end();
	
	while(it != itEnd) {
		cout << *it << endl;
		it++;
	}
	
	// 혹은 for문으로 사용
	vector<int>::iterator it2;
	for (it2 = v.begin(); it != v.end(); it++) {
		int data = *it;
		if (data == 3) {
			break;
		}
	}
	
	if (it != v.end()) {
		cout << "찾았음" << endl;
	}
}