[C++] C++ Standard Library Part 3. Container에 대해 자세히 알아보기

List

---

list는 sequence container로, 요소들이 메모리상에 연속적으로 배치되지 않고, non-contiguous 메모리 할당 방식을 사용한다.

보통 doubly linked list 형태로 구현돼 있어, 각 노드가 이전 노드와 다음 노드를 가리킨다.

 

주요 특징은

• 효율적인 insertion 및 deletion: list의 중간, 시작, 끝 어디에서나 insertion, deletion연산이 빠르게 가능하다.
• Random Access가 불가능하다. 원하는 element에 접근하기 위해서는 순차적으로 접근해야 한다.

List-initialization

항상 헤더를 포함해야 하고 list의 경우는 include <list>를 포함해야 한다.

 

vector initialization과 비슷하다.

 

list를 선언할 때, data type을 명시해야 하고 list는 단 하나의 데이터 type만 저장할 수 있다.

#include <list>
#include <string>

int main(){
	std::list<std::int> list1; //기본 초기화
    
    std::list<std::string> list2={"apple", "cake", "phone"} //직접 초기화
    
    std::list<std::string> list3(5, "dog") //특정 개수의 요소를 값으로 초기화
    
    return 0;
    }

List-insertion&deletion

#include <iostream>
#include <list>
#include <iterator>

int main(){
	std::list<int> lst={1,2,3,4,5};
    
    lst.push_back(6); //6을 뒤에 추가
    lst.push_front(7);//7을 앞에 추가
    
    auto it =lst.begin();//it이라는 iterator를 지정, auto를 통해 type 자동으로 지정
    std::advance(it, 4);//4번째 위치로 이동하는데, 여기서는 it iterator가 4를 가리킴
    lst.insert(it,8); //4를 가리키는 자리에 8삽입 > {7,1,2,3,8,4,5,6}
    
    std::advance(it,-4); //여기서 it은 그대로 4를 가리키고 있다. 8을 가리키는게 아님
    					 //따라서, 지금은 1을 가리키고 있음
    lst.erase(it);       // 1을 지움 > {7,2,3,8,4,5,6}
    
    lst.pop_back();      //마지막 요소 삭제 > {7,2,3,8,4,5}
    lst.pop_front();     //첫 번째 요소 삭제 > {2,3,8,4,5}
    
    return 0; 
  }

여기서는 advance동작을 했을 때 iterator가 어떤 것을 가리키는지 주의해서 봐야 한다.

List-Iteration

List interation은 두 가지 방법으로 할 수 있다.

Range-based for 문은 단순히 모든 요소를 순회할 때 이용하면 좋다.

반면에 중간에 조건을 넣어 세밀하게 제어를 하려면 iterator를 이용하여 순회하면 좋다.

• Range-based for 문

std::list<int> lst={1,2,3,4,5};

for (int element:lst){
	std::cout <<element<< " ";
}

• Iterator 사용

for(std::list<int>::iterator it =lst.begin(); it !=lst.end();++it){
	std::cout << *it<<" " //1 2 3 4 5

forward iterator를 사용할 경우로 begin()에서 시작해서 end()로 끝난다.

iterator앞에 *을 이용하여 element를 출력할 수 있다.

for(std::list<int>::reverse_iterator rit=lst.rbegin(); rit != lst.rend(); ++rit){
	std::cout << *rit << " ";
    }
    //5 4 3 2 1

list는 doubly linked list로 구현되기 때문에 backward iterator를 사용할 수 있다.

rbegin()은 5를 가리키는 iterator이고 rend()는 1을 가리키는 iterator이다.

따라서, 출력하면 5 4 3 2 1이 나온다.

List-Memory 구조

rend(), end()에 관해서 메모리에서 어떻게 동작이 일어나는지 이해하면 좋다.

 

먼저 rend(), end() iterator가 가리키는 값은 실제로 없기 때문에 이 값을 참조하면 undefined behavior 오류가 뜬다.

 

end()는 마지막 element 다음을 가리키는 것이고 rend()는 첫 번째 element 앞을 가리키는 것이다.

 

이 둘은 단지 iterate 연산을 할 때, 범위를 지정하기 위해 사용한 것이다.

 

List에서는 이 둘은 sentinel을 가리킬 가능성이 높다.(compiler마다 조금씩 다르다..)

 

예시를 통해 보면

std::list<int> lst={1,2,3,4,5};

for(auto it =lst.begin(); it != lst.end();++it){
	cout << &(*it)<<" ";
    }
cout << &(*lst.end()) << endl;

for(auto rit =lst.rbegin(); rit != lst.rend(); ++rit){
cout << &(*rit) << " ";
	}
cout << &(*lst.rend()) << endl;

/* Output:
0x7f8dfbf05f20 0x7f8dfbf06010 0x7f8dfbf06030 0x7f8dfbf05f90 0x7f8dfbf05fb0 0x7ff7b3bf71f8
0x7f8dfbf05fb0 0x7f8dfbf05f90 0x7f8dfbf06030 0x7f8dfbf06010 0x7f8dfbf05f20 0x7ff7b3bf71f8
*/

먼저 0x7ff7b3bf71f8을 제외하고는 역순으로 배치돼 있는 것을 알 수 있다.

 

즉, 1,2,3,4,5가 저장돼 있는 곳을 순서만 바꿔 출력했기 때문이다.

end()와 rend()가 저장돼 있는 주소도 동일한데 이는 순환구조를 가지고 있는 list의 sentinel임을 이해할 수 있다.

 

주소의 값도 자세히 보면 element는 0x7f8로 돼있는 반면, sentinel은 0x7ff로 돼 있다.

 

둘의 거리가 먼데, 그 이유는 sentinel은 안 변하기 때문에 stack에 저장해 놓고 element는 자주 변할 수도 있어 heap에 보관한다.

 

List에서 많이 쓰는 것

Map

---

Map은 유일한 하나의 key와 하나의 value 쌍으로 구성된 컨테이너이다.

기본적으로 map에 저장된 element들은 key를 기준으로 오름차순으로 정렬된다.(element=key:value구조)

이러한 element를 node라고도 하며 first(key)와 second(value) pair로 구성돼 있다.

key는 unique 해야 하고 value는 중복된 값이 있어도 괜찮다.

 

Map은 balanced binary search tree를 이용하여 구현해서 모든 연산에 대해 \(O(logn)\)의 시간 복잡도를 가진다.

Map-initialization

map을 사용하기 위해서는 항상 <map> 헤더 파일을 포함해야 한다.

map을 선언할 때는 key와 value의 type은 구체화해야 한다.

 

map은 nested list로도 initialization이 가능하다.

#include <map>
#include <string>

int main(){
	std::map<std::string, int> map1: //key, value의 type을 정하고 empty map을 initialize함
    
    std::map<std::string, int> map2={
    	{"Alice", 30},
        {"Bob", 25},
        {"Charlie",22}
        };
        return 0;
  }

Map-insertion

key-value pair를 insert 하기 위해 insert function을 이용하던가 [] operator를 이용한다.

#include <iostream>
#include <map>
#include <string>

int main(){
	map<std::string, int> ageMap;
    
    ageMap.insert({"Alice",30});
    ageMap["Bob"]=25;
    ageMap.insert(make_pair("Charlie",40));
    
    ageMap.insert({"Alice", 35});
    ageMap["Alice"]=35;
    
    cout << ageMap["Alice"] <<endl;
    cout << ageMap["Bob"] << endl;
    cout << ageMap["Charlie"] << endl;
    cout << ageMap["David"] << endl;
    
    return 0;
    } // 35 25 40 0

insert함수를 이용한 삽입과 [] operator를 이용한 삽입의 차이는 insert 함수를 이용할 경우 원래 있는 key의 pair가 삽입될 때 value가 update 되지 않는다. 

 

그 반면 [] operator를 이용하면 삽입할 수 있다.

 

또한 존재하지 않는 key에 대해 access 하려 할 때, 새로운 pair를 만들어버린다. 

이때 value는 default 값 또는 0으로 설정한다.

Map-Search

find() 함수는 iterator를 반환한다.

 

map.find(key) 형태로 사용하며 존재하면 해당 element를 가리키는 iterator를 반환하고 존재하지 않은다면 end()를 반환한다.

end() iterator까지 같은 iterator가 없으면 못 찾은 것이다.

int main(){
	std::map<std::string, int> ageMap={
    	{"Alice",30},
        {"Bob", 25},
        {"Charlie",22}
        };
     std::string name="Bob";
     
     if(ageMap.find(name) != ageMap.end()){
     	int age=ageMap[name];
        std::cout << name << ":" << age << std::endl;
        }
        
      auto it = ageMap.find("Charlie");
        if(it != ageMap.end()){
        std::cout << it-> first << ":" << it ->second <<std::endl;
        }

 

위 코드와 아래 코드는 상관없는 코드다.

 

if 조건에 안 맞을 경우인 else에 대해서는 딱히 지정 안 해도 문제가 없긴 하다.

아래로 구현한 find 코드가 it을 반환해서 하는 것이기 때문에 좀 더 세세하게 동작할 수 있다.  

std::cout << it->first << ":" << it->second <<endl;

이 코드를 보면 it은 map의 iterator이기 때문에 pair의 key를 first에 value를 second에 할당한다.

Map-Deletion

.erase() 함수는 지정한 key 또는 iterator를 이용하여 해당 요소를 삭제한다.

존재하지 않는 key에 대해 호출해도 오류를 발생시키지 않는다.

ageMap.erase("Bob");

Map-iteration

• Range-based for문

for(std::pair<std::string, int> pair : ageMap){
	std::cout << pair.first << "is" << pair.second <<"year" << std::endl;
    }

node를 정의해서 ageMap에서 for문으로 순회하는 방법이다.

node에서 key와 value를 접근하기 위해서는. first,. second 방법을 이용한다.

• iterator를 이용한 순회

for(std::map<std::string, int>::iterator it= ageMap.begin(); it !=ageMap.end(); ++it){
	std::cout << it->first << "is" << it->second << " years old." <<std::endl;
    }

iterator를 이용할 경우 node의 key와 value를 접근하려면 ->를 이용하면 된다.

Range-based for문을 이용할 때 사용한 (*it). first, (*it). second 꼴과 똑같은 것이다.

Map에서 많이 쓰이는 것

Set

---

Associative Container로 내부적으로 key를 사용하여 element를 저장/관리한다.

즉 중복을 허용하지 않고 유일한 값만 저장할 수 있다.

 

map에서는 key, value 쌍을 저장하지만, set에서는 value 자체가 곧 key가 된다.

또한 Set은 기본적으로 오름차순으로 정렬된다.

 

Set은 map과 동일하게 Balanced binary search tree(red-black tree)를 이용하여 구현하고 \(O(logn)\)의 시간복잡도를 갖는다.

 

Set-initialization

이제 너무 익숙할 거 같지만 항상 헤더파일을 include 해야 한다.

여기서는 <set> 헤더를 include 해야 한다.

#include <iostream>
#include <set>

int main(){
	set<int> mySet1;  // 빈 set이다.
    
    set<int> mySet2={2, 4, 1, 5, 3}; //내부적으로 정렬된 상태이며, 실제 순서는 {1, 2, 3, 4, 5}이다.
    return 0;
  }

set을 선언할 때는 data type를 구체화해야 한다.

Set-insertion, search, and deletion

std::set<int> mySet={2, 4, 1, 5, 3};

insert는 insert() 함수를 이용하여 구현할 수 있다.

mySet.insert(6)

deletion은 erase() 함수를 이용하여 구현할 수 있는데 value와 iterator 둘 다 이용하여 element를 찾아 지울 수 있다.

mySet.erase(4);

search는 find() 함수를 이용하여 value를 찾으면 iterator를 반환한다.

auto it =mySet.find(2);
if (it != mySet.end()){
	std::cout << *it< "FIND" << std::endl;}

Set-iteration

지금까지 봤던 것이랑 역시 똑같다.

std::set<int> mySet={4,2,3,5,1};

• Range-Based for loop

for (auto elem :mySet){
	std::cout << elem << "";
    } // 1 2 3 4 5

• iterator를 이용한 순회

for (std::set<int>::iterator it=mySet.begin();it !=mySet.end(); ++it){
	std::cout << *it << " ";
    }

좀더 세세하게 다룰 수 있다.

 

Set에서 많이 쓰는 것