1. Vector

동적으로 요소를 할당할 수 있는 동적 배열
탐색, 가장 뒤의 요소 사젝, 삽입 >> O(1)

vector<자료형>

1.1. push_back()

vector의 뒤에서 부터 원하는 값 추가

1.2. pop_back()

vector의 가장 뒤의 원소 제거

1.3. erase()

erase(position)
erase(start, last)

하나의 input이 제공되는 경우 해당 위치, 범위인 경우 첫 번째 인자의 위치부터, 두번째 인자 전까지 제거

1.4. find() - O(N)

find(start, end, value) // return : iterator

value 값을 찾아서 iterator 반환. 백터의 function이 아니라 STL 라이브러리의 기능이다.

1.5. clear()

vector 초기화

1.6. fill()

fill(start, end, value)

value 값으로 구간 채우기

1.7. 정적할당

아래와 같이 선언 가능

vector<int> v_init(5,100); // size 5, value 100 

1.8. 2차원 배열 선언

vector<vector<int>> v1;
    vector<vector<int>> v2(10, vector<int>(10,0)); // 이런식으로 바로 선언하는 것도 가능
    vector<int> v3[10];
    for( int i = 0; i < 10; i++){
        vector<int> temp;
        v1.push_back(temp);
    }

1.9. 전체 코드

#include <iostream>
#include <vector>
#include <list>
#include <map>

using namespace std;

int main(){
    cout << "Vector" << endl;
    vector<int> v;
    for( int i = 1; i <= 10; i++) v.push_back(i); 
    for( int a : v ) cout << a;
    cout << endl;

    v.pop_back(); // 백터의 가장 뒷부분 삭제
    for( int a : v ) cout << a;

    v.erase(v.begin(), v.begin() + 3); // erase의 경우 두번재 인자는 빼고 삭제!
    for( int a : v ) cout << a; // 범위기반 for loop의 경우 vector, array, map 모두 사용가능
    cout << endl;

    auto a = find(v.begin(), v.end(), 100);
    if(a == v.end()) cout << "not found" << endl;

    v.clear();
    if(v.size() == 0) cout << "noting" <<endl; // v.size() 함수는 vector의 함수임! array에 없다. 
    cout << endl; 

    vector<int> v_init(5,100); // size 5, value 100 
    for(int a : v_init) cout << a << " ";

    vector<vector<int>> v1;
    vector<vector<int>> v2(10, vector<int>(10,0)); // 이런식으로 바로 선언하는 것도 가능
    vector<int> v3[10];
    for( int i = 0; i < 10; i++){
        vector<int> temp;
        v1.push_back(temp);
    }
    cout << endl;
}

---

2. Array

정적 배열. 연속된 메모리 공간에 위치한 같은 타입 요소의 모음

기본적으로 아래와 같이 선언

 int a1[3] = {1,2,3};

하지만 아래와 같이 선언도 가능하다. 자동으로 크기가 할당됨

 int a1[] = {1,2,3};

이차원 배열에서 순차접근시 행먼저 접근하는 것이 캐시 측면에서 유리하다.

#include <iostream>
#include <vector>
#include <list>
#include <map>

using namespace std;

int main(){
    cout << "array"<< endl;
    int a1[3] = {1,2,3};
    int a2[] = {1,2,3};
    int a3[10];
    cout << sizeof(a1) << "," << sizeof(a2) << endl;

    const int mxy = 3;
    const int mxx = 4;
    int a_2d[mxy][mxx];
    for( int i = 0; i <mxy; i ++){
        for( int j = 0; j<mxx; j ++){
            a_2d[i][j] = (i+j);
        }
    }
    for( int i = 0; i <mxy; i ++){
        for( int j = 0; j<mxx; j ++){
            cout << a_2d[i][j] << " "; // x축으로 모두 탐색하고, 다음줄로 넘어가는것이 메모리 캐쉬측면에서도 좋다. 
        }
        cout << endl;
    }
}

---

3. list

CPP list는 Doubly linked list. 인접한 메모리 위치에 저장되지 않으며, 랜덤접근이 불가능하여 반드시 순차 접근해야함.

삽입과 삭제가 O(1)으로 빠르나, index 접근시 O(K)로 불리하다.

3.1. push_front()

리스트의 앞부분에 value 삽입

3.2. push_back()

리스트의 뒷부분에 value 삽입

3.3. insert(idx, value)

insert( position, val) // return : iterator

val 값을 해당 idx에 추가해준다. (기존 idx는 뒤로 밀림!)

3.4. erase(idx)

리스트의 idx 번째 요소 삭제

3.5. pop_front(), pop_back()

앞, 뒤 요소를 각각 삭제

3.6. front(), back()

앞, 뒤 요소 참조

3.7. clear()

3.8. 전체 코드

#include <iostream>
#include <vector>
#include <list>
#include <map>

using namespace std;

int main(){
    cout << "list" << endl;
    list<int> li;
    for(int i = 1; i <= 3; i++) li.push_back(i);
    for(int i = 1; i <= 3; i++) li.push_front(i); // 앞으로 삽입도 가능. O(1)
    for( int a : li) cout << a;
    cout << endl;

    auto it = li.begin(); // iterator는 보통 auto type으로 받아주는 것 같다. 
    it++ ;
    li.insert(it, 1000);
    for( int a : li) cout << a;
    cout << endl;


    li.erase(it); // insert 하면, 해당 iterator 앞에 추가되는 듯!
    for( int a : li) cout << a;
    cout << endl;

    li.pop_front();
    li.pop_back();

    for( int a : li) cout << a;
    cout << endl;

    li.clear();
    cout << endl;

}

4. Map

Key - Value 쌍으로 이루어져 있는 정렬된(삽입시마다 자동정렬) 컨테이너.

레드블랙 트리로 구현되어있으며 삽입, 삭제, 수정, 탐색 모두 O(logN)의 시간복잡도를 가진다.

4.1. insert({key, value})

map 에 {key, value} 삽입.

map.insert({key, value})
map.insert(make_pair(key, value)) // 이것도 가능함!

4.2. size()

map 에 있는 요소의 개수 반환

4.3. erase(key)

key 요소 제거

4.4. find(key)

find(key) // return : iterator

key 값을 가지고 있으면 iteraor를 반환한다. 못찾는 경우 map.end()가리턴됨.

4.5. map의 범위기반 for loop

map을 순환시에 다음과 같이 key, value에 접근 가능

for( int a : map) cout << a.first << a.second

하지만 만약 범위기반 for loop을 사용하지 않고 접근하는 경우 pointer로 접근해야하기 때문에 역참조 연산이 필요하다.

for( auto it = map.begin(); it != map.end() ; it ++ ){
	cout << (*it).first << (*it).second 
    }
    

4.6. 주의점

map 사용시, map을 참조하기만 하더라도 초기화가 발생해 요소가 추가된다

if(map["aaa"] == 0)
~~

위와 같은 코드를 실행하고 나면 , {"aaa" : value}가 생성되어버림.

이를 방지하기 위하여 find()를 사용할 수 있음

if(mp.find("kkk") == mp.end()){ // 이렇게 확인하는 것이 생성되는 것을 막을수 있다. 시간 복잡도는...?
        mp["kkk"]  = 10; 
    }

4.7. 전체 코드

#include <iostream>
#include <vector>
#include <list>
#include <map>

using namespace std;

int main(){
    cout << " map " << endl;
    map<string, int> mp; // 페어 형태로 들어가는거 같은데.. 
    string s[3] = {"jtm", "kye", "lcw"};
    for(int i = 0; i < 3; i++){
        mp.insert(make_pair(s[i], i+1));
        mp[s[i]] = i + 1;
    }
    cout << mp["jtm"] <<endl;

    cout<< mp.size() <<endl; // size 사용가능 
    mp.erase("jtm");
    auto it_m = mp.find("jtm");
    if(it_m == mp.end()) cout << "no keys in there"<<endl << endl;

    mp["jtm"] = 100;
    it_m = mp.find("jtm");
    if(it_m != mp.end()){
        cout << (*it_m).first << " : " << (*it_m).second << endl;
    }
 
    for(auto it : mp) cout << it.first << " : " << it.first << endl; // 이경우는 그냥 바로 값을 준다. 
    cout << endl;
    for(auto it = mp.begin(); it != mp.end(); it ++) cout << (*it).first << " : " << (*it).second <<endl;

    cout << endl;
    mp["aaa"];
    cout << mp["aaa"] << endl<< endl; //자동으로 int 면 0으로 초기화됨
    if (mp["bbb"] == 0) cout << "right now, bbb is added";

    if(mp.find("kkk") == mp.end()){ // 이렇게 확인하는 것이 생성되는 것을 막을수 있다. 시간 복잡도는...?
        mp["kkk"]  = 10; 
    }
}