[부트캠프] C++ - 반복자와 알고리즘

Claire·2024년 9월 10일

C++

반복자(Iterator)

반복자란

컨테이너의 구간에 대해 값을 읽어올 수 있는 기능을 제공

즉, 반복자는 컨테이너에 저장되어 있는 원소들을 공통적으로 하나씩 접근할 수 있게 함으로써 모든 컨테이너에 동일하게 동작하여 값을 얻어올 수 있게 한다.

반복자 적용 범위

반복자는 포인터와 흡사하다
정수 배열을 가리키는 포인터일 경우 ++연산을 하게되면 그 다음번 주소의 정수값을 읽을 수 있듯이 반복자 또한 ++ 연산을 적용할 수 있다.
포인터는 그 다음 주소값을 읽어오지만 반복자는 다음번 요소(데이터가 들어있는 메모리 자체)를 읽어온다.

iterator와 contst_iterator의 차이

const_iterator는 반복자가 가리키는 원소 값을 변경하지 못한다.
- 반복자의 값이 변경되지 못하는게 아니라 반복자가 가리키는 원소의 값변경이 불가
일반 반복자는 포인터와 비슷하고 const 반복자는 const 포인터와 비슷하다(= 간접 참조로 값을 변경하지 못한다)

반복자 사용 형태

타입명<T>::iterator it;

// vector의 반복자
vector<int>::iterator it;

반복자 사용 예제 코드

반복자 없이 코드 출력

// 정수형 배열 순회하면서 출력
void main() {
	int arr[] = { 1, 2, 3, 4, 5 };
	int* pNum;

	for (pNum = &arr[0]; pNum != &arr[5]; pNum++) {  // 배열의 첫번째 요소를 pNum 포인터 변수에 전달
		cout << *pNum << " ";  // 실제 값 출력  
        // 결과값: "1, 2, 3, 4, 5"
		cout << pNum << " ";   // 해당 값이 들어있는 주소값 출력  
        // 결과값: "00000069ED35F528, 00000069ED35F52C, 00000069ED35F530, 00000069ED35F534, 00000069ED35F538"
	}
	cout << endl;
}

// 문자열 배열 순회하면서 출력
void main() {
	char pArray[] = "programming";
	char* pArr = pArray;

	while (*pArr) {  // *pArr가 유요한 동안 반복 (pArr != NULL)과 동일한 의미
		cout << *pArr << " ";
		pArr++;
        // 결과값: "p, r, o, g, r, a, m, m, i, n, g"
	}
	cout << endl;
}

반복자 사용해서 코드 출력

void main() {
	int arr[] = { 1, 2, 3, 4, 5 };
	
	// vector
	vector<int> vi(&arr[0], &arr[5]);
	vector<int>::iterator it;

	for (it = vi.begin(); it != vi.end(); it++) {   // vi.end() == &arr[5]와 동일
		cout << *it << " ";
		vi[]
	}
	cout << endl;

	// list
	list<int> li(&arr[0], &arr[5]);
	list<int>::iterator it; 

	for (int i = 0; i < 5; i++) {
		li.push_back(i + 1);
	}

	// 반복자로 리스트 배열 탐색 및 출력
	for (it = li.begin(); it != li.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

알고리즘(Algorithm)

컨테이너에 적용할 수 있는 기능들을 체계적으로 정리해놓은 함수들의 집합
(=어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것)

알고리즘에 속한 함수는 일반적이기 때문에, 특정 컨테이너에 종속된 것이 아닌 모든 컨테이너에 사용할 수 있으며, 멤버함수가 아닌 일반 전역함수로 작성되어 있다.

알고리즘 종류

find( ) & find_if( ): 컨테이터에 특정값이 존재하는지 찾는 함수
copy( ): 컨테이너의 범위값을 대상이 되는 컨테이너에 복사하는 함수
for_each( ): 지정 구간을 반복하면서 지정한 작업을 수행
sort( ): 컨테이너에 저장된 데이터들을 오름차순으로 정렬하고자 할 때 사용하는 함수

해시

키를 값에 매핑할 수 있는 구조인 연관 배열 추가에 사용되는 자료 구조로, 해시 테이블은 해시 함수를 사용하여 색인을 버킷이나 슬롯의 배열로 계산한다.

해시맵(hash_map)

map과의 차이점은 hash라는 자료구서조를 사용함으로써 검색 속도가 빠르다는 점이다.

hash_map 사용형태

// 헤더 파일
#include<hash_map>
using namespace stdext;

// 변수, 반복자 타입
hash_map<key 자료형, value 자료형> 변수명
hash_map<key 자료형, value 자료형>::iterator 변수명
hash_map<key 자료형, value 자료형>::reverse_iterator 변수명
hash_map<key 자료형, value 자료형>::size_tyep 변수명

해시맵 사용 예제 코드

void main() {
	vector<string> str;
	unordered_map<string, int> test1;
	unordered_map<string, vector<string>> test2;

	test1["americano"] = 2000;
	test1["cafelatte"] = 3000;
	test1["cafemoca"] = 3500;
	test1["caramelmacchiato"] = 3500;
	test1["iced tea"] = 2800;
	test1["iced vanila latte"] = 3800;

	unordered_map<string, int>::iterator it_1;  // it_1은 포인터

	for (it_1 = test1.begin(); it_1 != test1.end(); it_1++) {
		cout << "The price that you ordered " << it_1->first << "is " << it_1->second << endl;
	}
    
    // 결과값
    "The price that you ordered cafemocais 3500
	The price that you ordered americanois 2000
	The price that you ordered cafelatteis 3000
	The price that you ordered iced vanila latteis 3800
	The price that you ordered caramelmacchiatois 3500
	The price that you ordered iced teais 2800"
    
	// vector를 인자값으로 받은 hash_map
	str.push_back("Okayama");
	str.push_back("Tokyo");
	str.push_back("Osaka");
	str.push_back("Nagoya");
	str.push_back("Saitama");
	str.push_back("Kagoshima");

	test2["Cities in Japan"] = str;
	str.clear();

	str.push_back("London");
	str.push_back("Harrington");
	str.push_back("Hammersmith");

	test2["Citeis in the UK"] = str;

	unordered_map<string, vector<string>>::iterator ith;
	vector<string>::iterator itv;

	for (ith = test2.begin(); ith != test2.end(); ith++) {  // 바깥쪽 hash_map의 루프를 돌리는 함수 
		// ith->second  "London, Harrington, Hammersmith"가 하나로 출력
		for (itv = ith->second.begin(); itv != ith->second.end(); itv++) {   // hash_map의 데이터인 vector<string>을 분해해서 루프를 돌리는 함수
			cout << ith->first << ": " << *itv << endl;
		}
		cout << endl;
	}
}

	// 결과값
    Cities in Japan: Okayama
	Cities in Japan: Tokyo
	Cities in Japan: Osaka
	Cities in Japan: Nagoya
	Cities in Japan: Saitama
	Cities in Japan: Kagoshima

	Citeis in the UK: London
	Citeis in the UK: Harrington
	Citeis in the UK: Hammersmith