C++

컨테이너와 반복자 살펴보기

Awesome Red Tomato 2022. 1. 3. 23:58

표준 라이브러리 컨테이너는 원소를 값으로 처리한다(값 전달 방식). 다시 말해 원소의 복제본을 저장, 대입 연산자로 대입, 소멸자로 삭제한다. 그래서 항상 값을 복제할 수 있게 만들어야 한다. 

 

원소를 레퍼런스로 처리하고 싶다면(레퍼런스 전달 방식) 원소를 그대로 넣지 않고 포인터를 사용해 저장한다.

 

이동 전용 타입, 즉 복제할 수 없는 타입도 컨테이너에 저장할 수 있지만, 이 때컨테이너의 연산 중 에러를 발생시킬 수 있다. 이동 전용 타입의 대표적인 예는 std::unique_ptr가 있다.

 


순차 컨테이너
  • vector
  • deque
  • list
  • forward_list
  • array
 연관 컨테이너
  • map
  • multimap
  • set
  • multiset

비정렬 연관 컨테이너(해시 테이블)
  • unordered_map
  • unordered_multimap
  • unordered_set
  • unordered_multiset
 컨테이너 어댑터
  • queue
  • priority_queue
  • stack

 

 

1. 순차 컨테이너

  1. vector
    vector는 표준 C 스타일 배열과 비슷하다. 원소를 연속된 메모리 공간에 한 자리씩 차지하게 저장한다. 
     
    vector<double> doubleVector;

int i = 0;
double inputNum = 0;

while (true)
{
	cin >> inputNum;
	doubleVector.push_back(inputNum);

	cout << doubleVector[i] << endl;

	if (inputNum == -1)
	{
		cout << "종료함" << endl;
		return;
	}
	++i;
}

    디폴트 생성자는 원소가 0개인 vector를 생성한다.
    vector<int> inVector; // 원소가 0개인 int타입 vector​

    원한다면 원소 개수와 초깃값을 설정할 수 있다.
    vector<int> intVector(10, 100); // 초깃값이 100인 int 원소 10개​

    초기화 방법은 여러가지가 있다.
    // 아래 셋 모두 동일하다.
vector<int> intVector({1, 2, 3, 4, 5});
vector<int> intVector1 = {1, 2, 3, 4, 5}; 
vector<int> intVector2{1, 2, 3, 4, 5, 6};​

    반복자도 있다. 반복자는 쉽게 말해 가리키고 있는 지점이다. 예를들어 아래 구문은 intVec의 0번째 원소를 가리키고 있는 iter이다.
    vector<int> intVec = { 1,2,3,4,5 };
vector<int>::iterator iter = begin(intVec);​

    2번째 원소를 가리키려면 이렇게 하면 된다.
    iter += 2; // 0번째에서 2칸 옮긴다. offset=2

    벡터의 0번째 요소부터 마지막 요소까지 출력하는 구문이다.
    vector<int> intVec = { 1,2,3,4,5 };
vector<int>::iterator iter = begin(intVec);

for (const auto& iter : intVec)
{
	cout << iter << endl;
}​
    const를 붙인 이유는 벡터의 요소들을 수정하지 않고 읽기 전용으로 접근하기 위함이다.

    원소를 추가하려면 push_back(), 삭제하려면 pop_back()을 사용하면 된다. 다른 추가 방법은 insert()를 사용하면 된다. 이 메서드는 원하는 지점에 추가가 가능하다. erase()는 원하는 원소를 제거할 수 있다. 원소를 모두 삭제하려면 clear()를 한다.

    표준 라이브러리는 모두 이동 의미론을 구현하도록 이동 생성자와 이동 대입 연산자가 제공된다. 컨테이너를 함수에서 값으로 리턴해도 성능 오버헤드를 최소화할 수 있다.
    string myElement(5, 'a');
vec.push_back(myElement);​
     
    myElement는 임시객체가 아니기 때문에 push_back()을 실행하면 myElement의 복제본을 만들어 vector에 추가한다. 그래서 이동 의미론 버전인 push_back(T&& val)도 지원한다. 아래 코드처럼 호출하면 복제 연산이 발생하지 않는다.
    vec.push_back(move(myElement));​

    임시 객체를 생성해 이동시키는 방법도 있다.
    vec.push_back(string(5, 'a'));​

    또 다른 추가 방법으로 emplace_back()이 있는데 이 메서드는 복제나 이동 작업을 수행하지 않고 컨테이너에 공간을 마련해 객체를 그 자리에 바로 생성한다.
    vec.emplace_back(5, 'a');​
     vector에 원소를 추가하거나 삭제하면 메모리를 확보하거나 채우기 위해 남은 원소들은 적당히 이동시킨다. 따라서 벡터의 추가 or 삭제된 지점을 참조하는 반복자는 그 연산이 끝난 후 사용할 수 없다. vector는 이걸 알아서 안해주므로 프로그래머가 해야한다.


    vector는 size()와 capacity() 메서드를 통해 크기에 대한 정보를 두 종류로 제공한다. size()는 vector에 담긴 원소 개수를 리턴하고 capacity()는 재할당 없이 담을수 있는 원소 개수(용량)을 리턴한다. 따라서 현재 상태에서 재할당 없이 추가할 수 있는 원소 개수는 capacity() - size()다. 

    C++17부터 std::size(), std::empty()가 추가됐다.
    vector<int> intVec = { 1,2,3,4,5 };
cout << size(intVec) << endl;
cout << empty(intVec) << endl;​
     
    C++17부터 std::data()가 추가됐다. 이 메서드를 호출하면 vector에서 데이터가 있는 메모리 블록에 대한 포인터를 구할 수 있다. 
    vector<int> intVec = { 1,2,3,4,5 };
int* data1 = intVec.data();

for (size_t i = 0; i < intVec.size(); i++)
{
	cout << data1[i];
}​



     

  2. deque
    deque는 vector와 거의 같지만 활용도는 낮다. 메모리를 연속적으로 저장하지 않으며 vector에는 없는 push_front(), pop_front() emplace_front()를 제공한다. 거의 사용하지 않으므로 패스.





  3. list
    리스트는 이중 연결 리스트를 구현한 표준 라이브러리 클래스 템플릿이다. 메모리에 연속적으로 할당하지 않으므로 operator[](예 list[3])을 지원하지 않아 반복자로만 개별 원소에 접근할 수 있다. 대부분 메서드는 vector와 같으므로 다른 점만 설명한다.

    원소를 접근하는 방법은 front()와 back() 뿐이다. 각 원소의 끝과 마지막 레퍼런스를 리턴한다. 나머지 원소는 반복자(iterator)로만 접근 가능하다.

    반복자는 양방향을 지원한다. 그래서 ++p나 --p 같은 연산으로 list 원소를 탐색할 수 있다. 하지만 vector와 달리 메모리가 순차적이지 않으므로 p+n같은 연산은 불가능하다.

    추가와 삭제는 push_front(), push_back(), pop_back(), emplace(), emplace_back(), insert() erase(), clear(), emplace_front(), pop_front() 등 제공한다.
     
    리스트는 vector와는 달리 deque처럼 내부메모리 모델에 관련된 메서드가 없다. 그래서 size(), empty(), resize()를 제공하지만 reserve(), capacity()는 제공하지 않는다.

    리스트는 원소의 빠른 추가와 삭제를 위해 몇 가지 특수 연산을 제공한다. 리스트는 전반적으로 연결 리스트이기 때문에 한 리스트를 통째로 다른리스트에 이어붙이는(splice)는 splice() 메서드를 제공한다. 그 외에 효율적인 버전의 알고리즘을 제공한다.

    remove()
    remove_if()    		 list에서 특정 원소를 제거한다.
    unique() list에서 같은 원소가 연달아 나온 부분을 제거한다. 
    merge() 두 list를 합친다. 둘 다 operator<나 사용자가 지정한 비교 연산으로 정렬된 상태여야 한다.
    sort() list를 정렬한다. 순위가 같은 원소는 그대로 놔둔다.
    reverse() list의 순서를 반대로 바꾼다.

    리스트는 단방향 리스트도 있다.
    https://docs.microsoft.com/ko-kr/cpp/standard-library/forward-list-class?view=msvc-170





  4. array
    크기가 고정된 점을 제외하면 vector와 같다. 다시 말해 크기를 늘리거나 줄일 수 없다. 그 이유는 vector처럼 항상 힙에 저장해서 접근하지 않고 원소를 스택에 할당하기 위해서다. 크기가 고정되어 있기에 크기와 관련된(원소 추가, 삭제, 용량 등) 메서드를 제공하지 않는다.




2. 컨테이너 어댑터

큐, 우선순위큐, 스택 총 세 가지 컨테이너 어댑터가 있다. 각각 내부적으로는 순차 컨테이너를 이용한다. 일종의 래퍼(wrapper)다. 그래서 내부 컨테이너를 교체해도 어댑터 사용에는 영향이 없다.

  1. queue
     
    template <class T, class Container = deque<T>> class queue;​

    내부 컨테이너로 deque나 list 중 하나만 쓸 수 있다.

    표준 FIFO(선입선출, first in first out) 방식을 구현한 것이다. queue는 간단하다. 생성자와 메서드 8개, 일반 비교 연산자가 전부다. push()와 emplace()는 큐의 끝에 원소를 추가하고 pop()은 큐의 앞에서 원소를 제거한다. front()와 back()을 이용하면 원소를 제거하지 않고도 맨 앞과 맨 뒤의 원소에 대한 레퍼런스를 구할 수 있다.
     




  2. priority_queue
    우선순위 큐는 원소를 정렬한 상태로 저장하는 큐다. FIFO에 따라 정렬하지 않으며, 맨 앞에 있는 원소의 우선순위가 가장 높다. 
    template <class T, class Container = vector<T>, class Compare less = <T>>;​
     내부 컨테이너로 vector나 deque를 사용한다. 세 번째 매개변수는 18장에서 자세히 설명한다.

    priority_queue가 제공하는 연산의 종류는 queue보다 훨씨 적다. push(), emplace()는 원소를 추가하고, pop()은 원소를 제거하고, top()은 맨 앞의 원소에 대한 const 래퍼런스를 리턴한다. 큐와 마찬가지로 size(), empty(), swap()을 지원하나 비교 연산자는 지원하지 않는다.





  3. stack
    queue와 거의 같다. FIFO가 아닌 FILO(선입후출, first in last out)이란 점만 다르다.
    template<class T, class Container = deque<T>> class stack;​

    내부 컨테이너로vector, list 또는 deque를 사용한다.



3. 정렬 연관 컨테이너

pair 유틸리티 클래스
정렬 연관 컨테이너를 살펴보기 전 <utility> 헤더에 정의된 pair 클래스를 보자. pair은 두 값을 그룹으로 묶는 클래스 템플릿이다. 두 값의 타입은 다르게 설정할 수 있다. 

표준 라이브러리는 두 값으로 pair를 만들어주는 make_pair()라는 유틸리티 함수 템플릿도 제공한다.

pair<string, float> aPair = make_pair("hi", 10.0f);


C++17부터 생성자에 대한 템플릿 매개변수 추론이 가능해졌다.

auto aPair = pair("hello", 32);​

 
C++17부터 구조적 바인딩도 추가됐다.

pair<string, int> myPair("hello", 5);
auto[theString, theInt] = myPair;	// 구조적 바인딩으로 pair의 원소를 분리한다.
cout << "theString: " << theString << endl;
cout << "theInt: " << theInt << endl;

 

  1. map
    key, value 쌍으로 저장한다. 추가, 조회, 삭제 연산은 모두 키를 기준으로 수행한다. 맵(map)이란 용어는 이 컨테이너가 키를 값에 매핑(대응, mapping)한다는 개념에서 따온 것이다. 

    원소들은 키 값을 기준으로 정렬된 상태를 유지한다. map은 생성할 때 키와 값에 대한 타입만 지정하고, 비교 타입과 할당자 매개변수를 지정하지 않으면 vector나 list와 같은 형태로 생성된다. 비교 타입은 18장에서 자세히 설명한다.
    map<string, int> mMap = 
{
	{"hi", 10},
	{"hello", 11},
	{"world", 12}
};​
     
    map은 순서에 상관 없이 원소를 추가할 수 있다. insert()는 키마 이미 존재하는지 검사할 수 있다.

    C++17부터 if문의 이니셜라이저에서 map에 데이터를 추가하고 그 결과를 확인하는 문장을 다음과 같이 표현할 수 있다.
    map<string, int> dataMap;
if (auto result = dataMap.insert({ "hello",10 }); result.second)
{
	cout << "SUCCEEDED" << endl;
}
else 
	cout << "FAILED" << endl;


// C++17
if(auto [iter, success] = dataMap.insert({"hello", 10}); success)
{
	cout << "SUCCEEDED" << endl;
}
else
	cout << "FAILED" << endl;

    C++17부터 insert_or_assign() 메서드를 지원한다. insert()와 비슷하나 참 거짓을 반환하지 않고 그대로 덮어쓰는 차이가 있다.

    원소를 그 자리에서 바로 생성하려면 emplace()와 emplace_hint() 메서드를 제공한다. vector와 기능은 비슷하다. C++17부터 지정한 키가 map에 존재하지 않으면 원소를 새로 만들어 추가하고, 키가 존재하면 아무것도 수행하지 않는 try_emplace()가 추가됐다.

    iterator은 순차 컨테이너와 비슷하게 작동한다. 가장 큰 차이점은 값 하나가 아닌 키/값 pair를 가리킨다는 점이다. 값에 접근하려면 반드시 pair객체의 second를 조회해야 한다. map의 iterator은 양방향이다.
    for(auto iter = cbegin(dataMap); iter != cend(dataMap); ++iter)
{
	cout << iter->second << endl;
}

    조회와 삭제를 위해 operator[]와 erase()를 제공한다.

    C++17부터 표준 라이브러리에서 노드(node)를 노드 핸들(node handle)의 형태로 직접 접근하는 기능이 추가됐다. extract() 메서드에 반복자 or 위치 or 키를 지정해 호출하면 연관 컨테이너에서 노드를 쓰는 노드 핸들ㅇ로 가져올 수 있다. extract()로 컨테이너에서 노드를 추출하면 컨테이너에서는 삭제된다. 
    map<string, int> dataMap; 
auto extracteNode = dataMap.extract(1); 
dataMap.insert(std::move(extractNode));​





  2. multimap
    한 키에 여러 값을 담을 수 있는 map이다. 값이 여러개라 operator[], at(), insert_or_assign(), try_emplace() 등 제공하지 않는다. 대신 원소의 범위를 가리키는 iterator를 제공한다.



  3. set / multiset
    map과 비슷하다. 다만 key/value가 아닌 키가 곧 값이라는 점이다. 




4. 비정렬 연관 컨테이너(해시 테이블)

비정렬 연관 컨테이너를 해시 함수로 구현하기 때문에 흔히 해시 테이블이라고 부른다. 해시 테이블은 버킷(bucket)이라는 배열 형태로 원소를 저장한다. 버킷마다 0, 1, 2와 같이 숫자 인덱스가 붙어 있다. 해시 함수는 키를 해시값(hash value)로 변환하는데 이 값은 다시 버킷 인덱스(bucket index)로 변환된다.

 

해시 함수의 결과는 중복될 수 있다. 두 개 이상의 키가 같은 버킷 인덱스를 가리키는 현상을 (해시)충돌이라 부른다. 이러한 충돌을 해결하기 위해 이차 함수 재해싱, 리니어 체이닝 등 다양한 방법이 나왔다. 관심 있다면 B.3절을 봐라.

 

 

  1. unordered_map
    template <
		class Key, class T, 
		class Hash = hash<Key>, 
		class Pred = std::equal_to<Key>, 
		class Alloc = std::allocator<std::pair<const Key, T>>>
class unordered_map;

    매개변수로 총 다섯가지를 가지며, 마지막 세 가지 변수를 통해 해시함수, 등호 비교 함수, 할당자 함수를 커스터마이즈 할 수 있다. 근데 대부분 디폴트값 쓴다
    	unordered_map<int, string> m =
	{
		{1, "hi1"},
		{2, "hi2"},
		{3, "hi3"},
		{4, "hi4"}
	};

	for (const auto& [key, value] : m)
	{
		cout << "key: " << key << ", value: " << value << endl;
	}

    map과 마찬가지로 키가 중복될 수 없다.





  2. unordered_multimap
    같은 키로 여러 원소를 대응할 수 있는 unordered_map이다. 차이는 operator[]와 at()을 제공하지 않는점, unordered_multimap에 대한 추가 연산은 항상 성공하고, insert_or_assign()과 try_emplace()를 제공하지 않는다.






  3. unordered_set과 unordered_multiset
    각각 키를 정렬하지 않고 해시 함수를 사용한다는 점만 빼면 set, multiset과 비슷하다. 따라서 생략한다.



5. 기타 컨테이너

C++언어는 표준 라이브러리와 함께 사용할 수 있는 컨테이너를 다양하게 제공한다(배열, string, stream, bitset 등).

 

  1. 배열
    생략한다.


  2. string
    string을 문자에 대한 순차 컨테이너로 볼 수 있다. vector처럼 사용 가능하다.
    	string mString;
	mString.insert(cend(mString), 'h');
	mString.push_back('i');

	for (const auto& letter : mString)
	{
		cout << letter;
	}​
     
  3. 스트림
    생략한다.

  4. bitset
    <bitset> 헤더에 정의되어 있다. 저장할 비트 수에 대해 템플릿화할 수 있다. 디폴트 생성자는 필드를 0으로 초기화 한다. 0, 1로 구성된 string을 만드는 bitset을 만드는 생성자도 있다.

    각 비트값은 set(), unset(), flip() 메서드로 설정할 수 있고 operator[]로 조회 및 설정 가능하다. test() 메서드로 개별 필드에 접근할 수도 있다.

    	bitset<10> mBit;
	mBit.set(3);
	mBit.set(6);
	mBit[8] = true;
	mBit[9] = 3;
	
	if (mBit.test(3)) // 해당 인덱스가 1인지 0인지
	{
		cout << mBit;
	}