C++ 기초 - Vector, Map

#include <string> 을 안 해도 사용 가능?

• IDE나 여러 요소에 따라 사용할 수 있을수도 있지만, <string>을 명시해주는 것이 좋다.

 

vector 컨테이너

• 동적 배열 역할을 함
• 필요할 때 힙에 자동으로 메모리 할당
  • 힙에 한 줄로 저장됨
  • CPU는 메모리에서 데이터를 가져올 때 주변 데이터도 함께 가져옴(캐시 라인, 보통 64바이트)
    • Vector처럼 붙어있으면 캐시 히트가 빠름. 흩어져 있으면 느림.
• 범위를 벗어나면 자동 소멸
• 배열처럼 v[i]로 접근 가능
  • 주소 + i로 O(1)로 접근 가능
• UE5의 Tarray, Java의 ArrayList도 동일 구조
• push_back, pob_back, size, empty, insert, erease 등의 편의 기능 제공
  • push_back() :벡터 끝에 원소 추가.
  • pop_back() : 벡터 끝 원소 제거
  • size() : 현재 들어있는 원소 개수
  • capacity() : 할당된 공간. 원소가 늘어나면 2배 혹은 1.5배로 재할당된다.
  • empty() : 벡터가 비었는지 확인
  • clear() : 모든 원소 제거
  • reserve(n) : 미리 메모리를 할당하여 capacityf를 n 이상으로 설정
  • resize(n, value) : 벡터 크기(size)를 n으로 변경. 사이즈 늘릴 경우 기본값으로 초기화. 줄일 경우 뒤에서부터 사라짐.
  • front() / back() : 벡터 첫 번째 / 마지막 원소 반환
  • at(index) : 안전하게 원소 접근
  • insert(pos, value) : 원하는 위치에 원소 삽입 ex) v.insert(v.begin +2, 3);
  • erase(pos) : 원하는 위치의 원소 삭제 ex) v.erase(v.begin() +1);
  • erase(first, last) : 범위[first, last) 원소 제거
  • swap() : 두 벡터 내용 교체 vector<int> a = {1,2}, b = {3,4}; a.swap(b); // a={3,4}, b={1,2}
  • data() : 내부 배열 포인터 반환(T*)
  • shrink_to_fit() : size에 capacity를 맞춤

 

vector<T> 사용 시

• 길이는 v.size()로 구한다.
  • size()의 반환 타입은 size_t다. 그러므로 반복문 등에서 for (size_t i = 0; i < v.size(); i++) 처럼 쓴다.
• to_string(변수)로 다른 타입의 변수를 string으로 변환 가능하다
  • string s = "a" + i와 같은 형식은 불가. to_string으로 변환해줘야함.
• iterator는 컨테이너 안의 원소 위치를 가리키는 객체.
  • vector<int>::iterator it
  • v.begin() :첫번째 요소
  • v.end() : 마지막 다음 위치
  • 벡터에서 위치 지정은 인덱스가 아니라 iterator이기 때문에, insert나 erase할 때 배열의 순서는 v.begin(), v.end()로 관리한다.

 

순회 방법

for( int i; i < v.size(); i++ )	인덱스 자체가 필요할 때
for( int x : v)	읽기만 할 때
for( int& x : v)	원소를 직접 수정할 때

 

 

효율성

push_back : O(1)

insert : O(n)

erase : O(n)

 

선언 방법

1. vector<int> v1; // 빈 vector
2. vector (Count: 5);

 

erase를 하는 것은 O(n^2)이 될 수 있으므로, erase보다는 새로운 배열을 만들어 push_back을 해주는 것이 효과가 좋다.

 

 

Map

• 키-값 쌍으로 이루어진 컨테이너
• 들어온 순서에 상관없이 오름차순 정렬로 유지됨
• Map<string, int> map 형식 
• map.first는 키, map.second는 값
• make_pair()를 이용하여 pair 객체를 생성하고 insert 함수를 사용할 수 있다.
  • myMap.insert(make_pair("banana",3));
• insert({"apple", 1}) 처럼 중괄호를 사용하여 추가할 수도 있다.
• 또는 myMap["a"]=10처럼 새로운 키에다 값을 넣으면 자동으로 추가된다.
• find는 키가 존재하면 해당 키의 이터레이터를 반환하고, 존재하지 않으면 map.end()를 반환한다.
• size(): 맵 사이즈를 반환
• erase(key) : key를 가진 요소를 삭제
• clear() : 맵의 모든 요소 삭제