[알고리즘/C++/STL] STL 컨닝페이퍼

STL 사용법이 아직 익숙하지 못해서 , 컨닝페이퍼 처럼 블로그에 기록을 해보려고 한다. 알고리즘 문제들은 C언어의 Array[]와 같이 전통적인 배열을 사용해도 대부분은 문제가 없었지만, 코드의 간결함과 빠르게 풀 수 있다는 장점 때문에, 앞으로는 STL을 적극적으로 채용하기로 했다.

내가 직접 짜는것 보다, STL은 이미 많은 사람들이 쓰고 있으며, 신용도가 보장되어있음. 좋은건 갖다쓰자. 그림을 그리는데, 염료부터 만들기 위해 꽃을 키우는 짓은 하지말자. 대신, 어떤 꽃이 더 발색이 잘되고 ,어떤 꽃이 더 좋은 염료를 갖고있는지는 알아야하니까, 특징들은 잘 알아놓자.
(절대로 자신의 머리 탓을 하지말자 !! STL을 이용하는건 당연한거다..! 라고 합리화를 해봅니다)

Vector

• STL에서 가장 많이쓰임.
• 배열의 크기(Capacity)가 동적입니다. Size나 length는 내가 넣어준 요소의 길이에 따라서 정해지고, Capactiy(허용량)은 C++에서 특정 크기가 넘어가면 자동으로 할당 해줍니다.
• Capacity가 넘칠 시, 기존 원소들을 복사하여, 새로운 메모리 공간에 붙여넣기 때문에 O(n)의 연산속도를 가지게 됩니다. 또한, 이 과정에서 iterator도 무효화가 될 수 있음.
• Capacity를 그렇다고, 매번 늘려주는건 아님. 8 -> 10 -> 16 -> 29-> ...와 같이 처음에는 증가하는 폭이 작다가, 그 뒤로는 증가하는 폭을 크게해서, 재할당함.

Vector 선언하기

vector<자료형> 변수명; // 기본사이즈
vector<자료형> 변수명(크기) // 사이즈 지정
vector<자료형> 변수명(크기,초기값) // vector<int> v(5,0)로하면, 5의 크기에 모두 0이 들어간 vector 생성
vector<자료형> 변수명(또 다른벡터) // Deep Copy. 

vector 멤버함수

모든 함수는 vector<int> v를 기준으로 작성하겠습니다.

Vector 값 할당 및 조회

• v.assgin(size,init) : init값으로 size만큼 할당.
• v.at(idx) : idx번째 원소를 참조. v[idx] 보다는 느리지만, 범위를 점검하므로 안전합니다.
• v[idx]: idx번째 원소를 참조. v.at(idx)보다는 빠르지만, 안정성이 떨어집니다. 다른 메모리를 가리킬 수 있습니다. (error를 발생시키지 않음)
• v.front() : 첫번째 원소를 참조합니다.
• v.back(): 마지막 원소를 참조합니다.

Vector 값 삽입 및 삭제

• v.push_back(n) : 마지막 요소 뒤에 원소 N을 삽입합니다.
• v.pop_back() : 마지막 원소를 제거합니다.
• v.push_front(n) : 첫번째 요소에 원소를 삽입합니다. 나머지 요소들을 다 뒤로 미루는 연산이 있으므로, O(N)의 복잡도를 가집니다.
• v.pop_front(): 첫번째 요소에 원소를 pop합니다. 나머지 요소들을 앞으로 땡기기 때문에, O(N)의 복잡도를 가집니다.
• v.insert(idx,value) : idx번째에 value를 삽입합니다. 삽입한 곳의 iterator를 반환합니다.

Vector의 Iterator 관련 명령어

• v.begin() :vector의 시작점에 iterator가 반환됩니다.
• v.end() : vector의 마지막요소 다음에 iterator가 반환됩니다.
• v.rbegin() :vector의 마지막 요소의 iterator가 반환됩니다.
• v.rend(): vector의 시작점 앞의 iterator가 반환됩니다.

그림으로 보면 편합니다.

vector 사이즈와 허용량

• v.size() : 원소의 갯수를 리턴합니다.
• v.capacity() : 현재 벡터의 허용량을 검사합니다.
• v.empty() : 벡터가 비어있다면, true를 리턴, size가 0이면 비어있다고 판단합니다.

Vector를 이용한 2차원 배열

• 벡터안에 벡터를 넣어도 되고, 만약 요소가 2개밖에 없다면, Pair를 넣어도 됩니다.
• 벡터를 배열로 선언해주어도 됩니다.

  vector<vector<int>>  v2; //단, 벡터안에 들어가는것 또한 vector로 해주어야합니다.
  vector<int> v[3]; //vector를 배열로 선언해줍니다. 
  vector<vector<int>> v(10,vector < int >(10,0));  // 10x10 배열 0으로 초기화선언
  vector<pair<int,int>> v ; // [ {1,2},{1,2},{1,2}] 와 같이 요소를 2개만 갖는 2차원 배열을 선언하고 싶을 때

vector 순회하기

for(auto iter = v.begin(); iter !=v.end(); iter++){
		cout<<*(iter)<<'\n';
}

List

• 이중연결 리스트(doubly linked list) 입니다.
• 메모리 공간에 연속적으로 할당되어 있지 않습니다.
• 원소를 탐색할 때, 임의접근이 아니라, iterator를 기반으로 요소를 탐색합니다.
• 양 끝을 기준으로 push_back(),push_front(),pop_back(),pop_front() 등으로 삽입,삭제 연산을 합니다.
  

List 선언하기

list<자료형> 변수명(사이즈);

List 요소 삽입하기

• lt.push_back(n) : 맨 마지막에 n을 추가합니다.
• lt.push_front(n) : 맨 앞에 n을 추가합니다.
• lt.pop_back() : 맨 뒤의 원소를 pop 합니다.
• lt.pop_front() : 맨 앞의 원소를 pop 합니다.

List 연산

• lt. insert(iter,n) : 해당 iter가 가리키는 위치에 n을 삽입합니다. 삽입한 원소를 가리키는 iterator를 반환합니다. (iterator가 무효화되지 않습니다. )

• lt. erase(iter) : 해당 iter가 가리키는 원소를 삭제합니다. 반환값을 삭제한 원소의 다음을 가리키는 iterator를 반환합니다.

• lt.sort() : 오름차순으로 정렬 합니다. 파라미터로 이항조건자가 옵니다.

• lt.splice(iter2,List1,a,b) : iter2에서 가리키는 곳에 List1을 통째로 붙입니다. 추가로 [a,b)까지의 등의 범위를 지정해줄 수 있습니다.

• lt.remove_if(Predicate) : Predicate(조건)에 맞게 remove를 시킵니다. 조건문이 들어갑니다.

List 순회하기

//범위 기반(range based) for문
for(auto it:li){
	cout<<it<<'\n';
}
//For문
for(list<int> it=li.begin();it != li.end();it++){
	cout<<*it<<'\n';
}

Map

배열로 풀면 2중 반복을 돌아야하는 문제를 가끔 쉽게 풀어주게하는 , key-value쌍으로 저장되는 Map자료구조 형입니다.

• 연관 컨테이너 중 하나이며, 노드 기반으로 이루어진 균형이진트리 구조를 갖습니다.
• Key는 유일한 값입니다. 중복이 되지 않습니다.
• 삽입하면서, key를 기준으로 자동 정렬합니다.
• malloc로 메모리공간이 필요할 때, 메모리를 할당합니다.

map 선언하기

map<key자료형,value자료형> m;
혹은 map<pair<key 자료형,value 자료형>> m; 

map 요소 삽입하기

• map[key] = value로 원소를 추가 혹은 수정이 가능합니다. ([] operator 사용가능)
• m.insert(pair<자료형,자료형>(10,10))과 같이, pair를 통해 insert로 넣는것 또한 가능합니다.

map 연산

• m.find(key): key를 기반으로 탐색을 합니다. 해당 key를 가리키는 반복자를 반환하게 됩니다. 만약, key가 없다면 m.end()와 같은 반복자를 반환합니다. iter가 pair를 가리키기 때문에, (*iter).first 혹은, ->first로 접근해야합니다.
• m[key] + m[key] , m[key] < m[key]와 같이 사칙연산, 부등호 연산이 가능합니다.

범위기반 Loop, 일반 Loop 차이점

범위기반 Loop는 처음부터 끝까지 순회를 하는 반복문입니다.

• Index로 어떤 로직을 수행하기 번거롭습니다.
• DataList의 내부 요소들을 복사하기 때문에 메모리를 더 소모하게 됩니다. 복사를 하지 않는다면, reference(&,참조자)를 이용해야합니다. 하지만, 이러면 원본의 값이 변경될 위험성을 갖게됩니다. 이때, 복사는 일어나지 않고, 원본값을 보호하고 싶다면 const 상수의 특성과 참조자의 특성을 혼합하여 사용하면 됩니다. 원본 값이 변경이 될 필요성이 있다면 const를 빼주면 됩니다.

for(Type element: DataList){
	element...
}

for(const Type& element:DataList){
	//원본 데이터는 참조하면서, 변경 x
}