Review 2 - Container, Iteration in C++

https://eglife.tistory.com/83

Review 1 - Basic Standard Library in C++(Cin/out,file I/O, String)

지난 시간에 복습했던 것들중에 String과 Stringstream 부분은 정말 중요하고, 각종 퀴즈에도 많이 나오니까 잘 숙지해야한다.

 

이번엔 Container에 대해서 얼른 뭐가 있는지, 특징은 무엇인지 체크를 해보자

 

1. Vector

 

Vector는 Dynamic-size array로 연속적인 Container이다. memory끼리 서로 contigous하게 붙어 있으며 Random access를 지원한다.(just like index). Array 형태이다보니까 memory의 처음과 끝에 insertion or deleteion하는 것이 편하다. 그리고 Capa가 초과되면 자동적으로 resizing을 한다. 그냥 결론적으로 Python의 list와 비슷한 녀석이라고 생각하면 된다.

어찌보면 일전에 배웠던 String과도 비슷하다. 역시나 Haep에 Memory allocation이 되는 친구! 

 

#include <iostream>
#include <vector>

int main(){
    // 방법1
    std::vector<int> vec1 = {1,2,3};
    // 방법2
    int arr[] = {5,6,7};
    std::vector<int> vec2(std::begin(arr),std::end(arr));

    // 방법3
    std::vector<int> vec3(5,100); // 5개 size를 100으로 채운다.

    // Insertion
    std::vector<int> vec4;
    vec4.push_back(11);
    vec4.push_back(22);
    vec4.push_back(33);

    std::cout << vec4.at(1) << std::endl;
    //22

    // Deletion
    std::vector<int> vec5 = {12,13,14,15,16,17};
    vec5.pop_back(); // 맨 끝에 놈 삭제
    vec5.erase(vec5.begin()+1); // vec5.begin()=>맨 첫놈 기준 +1 삭제(13)

    for(int x : vec5){
        std::cout << x << " ";
    }//12 14 15 16

    


    return 0;
}

 

뭐 가볍게 알아보면 Vector의 특징은 위와 같은데,

 

사실 initialize는 방법1로 젤 많이 하고, method도 push_back / pop_back 정도를 젤 많이 쓴다.

그래도 복습하면서 알았는데 vec.begin()을( 또는 vec.end() ) 기준으로 삭제하는 erase 메소드도 쓸만할 거 같다는 생각이 든다.

쓸만한 Vector Method 목록

 

※ Iteration

 

C++에서 for문 쓸 때 많이 쓰는 개념이라고 생각하자. 일종의 Python index와 같은 개념으로, Container에서 특정 Data를 조회,삭제,추가하기 위해서 그 놈의 위치를 파악하는 용도로 쓰이는 녀석이다.

 

    std::vector<int> vec = {3,6,9,3,6,9};

    for(int val : vec){
        std::cout << val << " ";
    }
    std::cout << "\n";
    for(auto x : vec){
        std::cout << x << " ";
    }
// 3 6 9 3 6 9 
// 3 6 9 3 6 9

 

auto 를 쓰면 자동적으로 적절한 data type을 설정해 print를 해준다. 이게 나중되면 넘나 유용해서 걍 auto만 쓰게 된다 ㅎ;;;

 

※  Iterators

auto만큼 또 유용한 친구인데 바로 iteraror , 얘를 이용해서도 element들을 print할 수 있다.

 

    std::vector<int> vec = {3,6,9,123,0,-123};

    for(std::vector<int>::iterator it = vec.begin();it!=vec.end();++it){
        std::cout << *it << " ";
    }
// 3 6 9 123 0 -123

 

이렇게 vector의 시작과, 끝 지점을 begin() / end() 를 이용해서 iteraror 로 print할 수 있다.

 

auto가 편한게, for문 안에 저 std::vector<int>::iterator <-- 이렇게 긴 놈도 그냥 auto로 대체가 가능하다.

    for(auto it = vec.begin();it!=vec.end();++it){
        std::cout << *it << " ";
    }
// 3 6 9 123 0 -123

앞서 설명했듯이, Iterator는 pointer와 비슷한 역할을 하며 Container와 상관없이 거진 다 동작한다.

*it 은 C/C++ Pointer처럼 지금 이놈이 가리키고 있는 값을 반환한다.(just like dereference) 그리고 pointer 기준으로 ++,--를 통해 memory 공간을 이리저리 돌아다닐 수도 있다.

 

참고로, vec.begin()은 : 첫 번째 element의 위치를 가리키고 / vec.end()는 마지막 element를 한 칸 지난 시점을 가리킨다.

    std::vector<int> vec = {3,6,9,123,0,-123};

    for(auto it = vec.rbegin();it!=vec.rend();++it){
        std::cout << *it << " ";
    }
// -123 0 123 9 6 3

begin / end 대신 rbegin / rend를 쓸 수도 있다. 그러면 이렇게 거꾸로 출력이 된다.

저 위의 그림에서 end -> rbegin, begin -> rend 가 되었다고 생각하면 된다.

 

Iterator를 써서 element의 위치를 찾거나 element들의 값을 더할 수도 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>

int main(){

    std::vector<int> vec = {3,6,9,123,0,-123};

    auto it = std::find(vec.begin(),vec.end(),123);
    if(it != vec.end()){
        std::cout << "123 index: " << std::distance(vec.begin(),it) << std::endl;
    }else{std::cout << "NOT FOUNDED";}
    // 123 index: 3

 

그러면 이제 find함수를 써야 하는데 이 때 #include <algorithm> 헤더파일이 필요하다.

find 함수는 find(vec.begin(), vec.end(), target) 이런 식으로 선언을 하는데, target을 찾으면 그 놈의 위치 iterator를 반환하고 못 찾으면 그냥 vec.end()를 반환한다.

 

iterator의 offset를 반환해주기 위해서 vec.begin() 기준으로 이 놈이 얼마나 떨어져있나를 알려주기 위해서 distance 함수를 사용한다. distance(vec.begin(),it) 이렇게 쓴다.

#include <iostream>
#include <vector>
#include <numeric> // for std::accumulate
// #include <algorithm>

int main(){

    std::vector<int> vec = {3,6,9,123,0,-123};
    size_t sum = std::accumulate(vec.begin(),vec.end(),0);
    // 초기 seed 값이 0이라는 뜻

    std::cout << sum; //18

이렇게 numeric이라는 header file을 선언해주면, accumulate 함수를 쓸 수도 있다.

 

솔직히 함수는 종류가 너무 많아서 다 외우긴 힘들고, 문제 풀면서 자연스럽게 손에 익는 녀석들만 가져가는 게 맞는듯하다.

  size_t sum = std::accumulate(vec.begin(),vec.begin()+2,0);

 

뭐,, 상식적으로 될만한 것들은 다 된다. accumulate을 쓸  때도, 무조건 처음부터 끝! 이렇게 지정해줄 필요는 없고 이렇게 적절히 iterator의 위치를 정해서 일정부분만 더하는 방법도 가능하다.

 

 

2. list

 

list는 non-contiguous memory allocation을 하는 container이다(<-> vector). 그 유명한 Doubly linked list로 구현되어 있으며 어느 곳에서나 element insertion / deletion하기가 유용하다. 다만, 단점으론 vector와 달리(contiguous memory와 달리) random access를 지원하지 않는다. ex: lst[0] , lst[14] 이런거 불가 ㅠ

개략적인 list 구조

#include <list>
int main(){
    //방법1
    std::list<int> lst1;
    //방법2
    std::list<int> lst2 = {6,3,9};
    //방법3
    std::list<int> lst3(5,10);
    cout << "lst1 : ";
    for(int x : lst1){
        cout << x << " ";
    }
    cout << "\nlst2: ";
    for(int x : lst2){
        cout << x << " ";
    }
    cout << "\nlst3: ";    
    for(int x : lst3){
        cout << x << " ";
    }
//     lst1 : 
// lst2: 6 3 9
// lst3: 10 10 10 10 10

 

list도 vector와 비슷하게 initialize하는 방법이 여러개 잇지만 역시 direct하게 하는 방법2가 가장 많이 쓰인다.

 

int main(){

    list<int> lst = {3,6,9};
    lst.push_back(11);
    lst.push_front(0);

    for(int x : lst){
        cout << x << " ";
    }
    cout << endl;
// 0 3 6 9 11 
    auto it = lst.begin();
    advance(it,3); // it을 +3 해줌
    lst.insert(it,100);

    for(int x : lst){
        cout << x << " ";
    }
    cout << endl;
    // 0 3 6 100 9 11

    advance(it,-2); // it을 -1 해줌
    lst.erase(it);    

    for(int x : lst){
        cout << x << " ";
    }
    cout << endl;
    // 0 3 100 9 11


    lst.pop_back();
    lst.pop_front();

    for(int x : lst){
        cout << x << " ";
    }
    cout << endl;
// 3 100 9

 

element를 insert / delete하는 것도 vector와 비슷하다.

대신 push_front / pop_front 기능도 지원하며, insert/erase를 사용할땐 advance로 it의 위치를 바꿔줘야 한다.

 

list의 내용을 읽는 iterator는 vector와 동일하고 역시 rbein / rend를 지원한다.

 

list, vector 모두 dynamic한 구조라서 memory는 heap에 할당된다!

알아두면 유용한 list의 method들

 

3. map

 

Python에서도 별 거 아닌거처럼 보였지만, 실은 굉장히 많이 쓰이던(Hash 때문에) MAP! C++에서도 등장하였다.

 

C++에서도 Key-Value 쌍으로 선언된다. 참고로 C++에선 vector,list,map,set 모두 { } 중괄호를 사용해서 선언된다. 대괄호는 index접근, 소괄호는 Method사용할 때만 쓰인다고 보면 된다.

 

역시나 Key는 unique value only, Value는 중복허용이다.

 

다만, Hash와는 다른게 자동적으로 map은 key값 기준으로 ascending(오름차순) 정렬을 지원한다. 이건 Red-Black Tree(Balance binary tree) Base로 구현되었는데, 요놈은 나중에 알고리즘 복습할 때 나오는 녀석이다.. 어려운 개념임

 

그래서 Element 조회,삽입,삭제 등의 TIme complexity는 O(log N)인데, 기존 Hash를 사용해서 빠르게 element를 탐색하는 것이 필요하면 unordered_map ( O(1), but 최악으론 O(n) ) 을 사용하면 된다. 얘는 key 값 기준 정렬효과 없는 map구조다.

 

map은 pair object로 접근할 수 있는데 각각 first(key) , second(value)를 뜻한다.

 

using namespace std;
#include <string>
#include <list>
#include <map>
int main(){
    //방법 1
    map<string,int> map1;

    //방법 2
    map<string,int> map2 = {
        {"A",100},
        {"B",50}
    };

 

map은 요렇게 선언해줄 수 있다. vector , list 처럼 N사이즈만큼 X로 채워달라~ 이런 거 없음!

map 구조에 element를 넣을 때 주의할 점은,

insert를해서 넣으면 기존에 동일한 key가 존재할 경우 insert가 일어나지 않는다. 그래서 보통 대괄호 [  ] 를 써서 insert하는 것이 편하다. 얘는 element update가 가능하게 하도록 한다.

 

    map<string,int> map2 = {
        {"A",100},
        {"B",50},
        {"C",0}
    };

    if(map2.find("A")!=map2.end()){
        int ans = map2["A"];
        cout << ans << endl;
    }//100

    auto it = map2.find("B");
    if(it != map2.end()){
        cout<<it->first<<" "<<(*it).second<<endl;
    }//B 50

 

Element는 이렇게 find 를 이용해서 찾을 수 있다.

 

공통적으로, find는 해당 element를(KEY  값 기준임) 찾으면 그 놈에 맞는 pair 를 return해주고,

값이 없으면 map2.end() 값을 return한다.

 

    if(map2.find("A")!=map2.end()){
        int ans = map2["A"];
        cout << ans << endl;
    }else cout<<"NONE"<<endl;//100

    map2.erase("A");

    if(map2.find("A")!=map2.end()){
        int ans = map2["A"];
        cout << ans << endl;
    }else cout<<"NONE"<<endl;//100  
    // NONE

 

map 구조의 delete는 간단히 erase를 써주면 된다. erase에 key 값만 써줘도 그에 해당하는 pair가 삭제되는 것을 볼 수 있다.

 

    map<string,int> map2 = {
        {"A",100},
        {"B",50},
        {"C",0}
    };

    for(auto p : map2){
        cout << p.first << " " << p.second <<endl;
    }
// A 100
// B 50
// C 0
    for(auto it=map2.begin();it!=map2.end();it++){
        cout << it->first << " " << it->second << endl;
    }
// A 100
// B 50
// C 0

 

map은 print할 때 pair 라는 녀석의 first / second로 read하거나 iterator를 돌려준다.

 

알아두면 유용한 map의 method

 

 

4. set

Python 때와 마찬가지로 C++에서도 set은 unique한 element를 저장한다. key 와 value가 동일한 map구조로 알고 있으면 되고, 이 역시 value(=key) 값 기준으로 sorting이 되어있다.

 

#include <set>
int main(){
    set<int> s1 = {1,2,3,4,2,5,2,1,5};
    set<int> s2;

    for(auto x:s1){
        cout << x << " ";
    }
    // 1 2 3 4 5

set도 요렇게 선언할 수 있으며, 자동으로 중복제거가 되는 것을 확인할 수 있다.

    set<int> s1 = {1,2,3,4,2,5,2,1,5};
    set<int> s2;

    s1.insert(7);
    s1.erase(1);
    for(auto x:s1){
        cout << x << " ";
    }
    // 2 3 4 5 7
    auto it = s1.find(2);
    if(it != s1.end()){
        s1.erase(it);
    }
    for(auto x:s1){
        cout << x << " ";
    }//3 4 5 7

 

insert / delete는 가볍게 insert, erase 함수에 value를 집어넣어서 할 수 있고,

 

특이하게 erase의 경우엔 find를 통해 찾은 iterator를 넣어도 erase가 발생한다.

 

set의 element를 읽는 방법도 똑같이 for(auto x:set) / for(auto it=set.begin(); it != set.end() ; it ++ ){ *it  }

 

요렇게 2가지가 있으니 skip한다.

set의 method

이것 말고도 deque, unorderd_map, unordered_set, priority_queue 등 다양한 container가 있다.

 

 

누누히 말하지만,

 

Container도 보통 잘 쓰이는 것만 쓰이니까

 

실습을 많이 하면서 어느 경우에 어떤 놈을 쓰는 것이 적합한지 잘 파악해야 헌다.

 

- E. O. D -