[c++/algorithm] std::set,std::map

set, map의 차이는 set은 key값만 저장하고 map은 key값과 value를 저장한다.

set과 map 둘 다 중복을 허용하지 않는다. 또한, 둘 다 컨테이너 내부에서 오름차순으로 정렬 된다.

​

std::set 컨테이너

template<class key, class Compare=std::less<Key>//기본적으로 오름차순 정렬

,class Allocator=std::allocator<Key>>

class set;

​

• key 타임의 키(key) 값을 저장하는 연관 컨테이너
• 저장된 데이터는 키 값을 기준으로 정렬됨 (오름차순)
• 데이터 삽입, 삭제, 탐색은 0(log n) 시간 복잡도로 동작 (균형잡힌 이진탐색트리 사용)
• 중복되는 데이터를 set구조로 저장하려면 std::multiset 컨테이너 사용
• 데이터 정렬되지 않은 상태로 저장하려면 std::unordered_set 컨테이너 사용
• #include <set>에 정의

begin(), end(), rbegin(), rend()	순방향 및 역방향 반복자 반환
insert()	(중복되지 않는) 새로운 원소를 삽입 (emplace() -> 좀 더 효율적)
erase()	특정 원소를 삭제
find()	특정 키 값을 갖는 원소를 찾아 반복자를 반환, 원소를 끝까지 찾지 못하면 end()에 해당하는 반복자 반환
clear()	모든 원소 삭제
size()	원소의 개수를 반환
empty()	set이 비어있으면 true를 반환

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	set<int> odds{ 1,7,5,3,9 };	//오름차순 정렬 자동으로 수행
	set<int, greater<>> evens{ 2,4,6,8 };	//내림차순 정렬
	evens.insert(10);
	evens.insert(2);	//이미 있는 값이라 insert 무시됨

	if (evens.find(4) != evens.end())
		cout << "4 is even!" << endl;
	else
		cout << "4 is not even!" << endl;

	//출력: 4 is even!

	for (auto n : odds) {
		cout << n << ", ";
	}
	cout << endl;
	//출력: 1,3,5,7,9, -> 자동 오름차순 (key값 기준)

	for (auto n : evens)
		cout << n << ", ";
	cout << endl;
	//출력: 10,8,6,4,2,
}

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main()
{
	using psi = pair<string, int>;
	set<psi> managers{ {"Amelia", 29}, {"Noah", 25}, {"Olivia", 31}, {"Sophia", 40} };
	managers.insert(make_pair("George", 35));

	psi person1 = { "Noah", 25 };
	if (managers.find(person1) != managers.end())
		cout << person1.first << " is a manager!" << endl;
	else
		cout << person1.first << " is not a manager!" << endl;

	managers.erase({ "Sophia", 40 });
	managers.erase({ "Noah", 30 }); //30살의 Noah는 존재하지 않기 때문에 지워지지 않음

	for (const auto& m : managers)
		cout << m.first << "(" << m.second << ")" << endl;
	//Amelia(29) George(35) Noah(25) Olivia(31) -> 이름(key값)으로 오름차순 (자동)
}

std::map 컨테이너

template<class Key, class T, class Compare=std::less<key>, class Allocator=str::allocator<std::pair<const Key, T>>>

class map;

• Key 타임의 키(key)와 T 타임의 값(value)의 쌍을 저장하는 연관 컨테이너
• key 값을 기준으로 정렬됨
• key 값으로 간단하게 value 값 구할 수 있음
• 데이터 삽입, 삭제, 탐색은 0(log n)의 시간 복잡도로 동작
• 중복되는 데이터를 map으로 저장하려면 std::multimap 컨테이너 사용
• 정렬되지 않은 상태로 저장하려면 std::unordered_map 컨테이너 사용
• #include <map>에 정의

begin(), end(), rbegin(), rend()	순방향 및 역방향 반복자 반환
insert()	(중복되지 않는) 새로운 원소를 삽입 (emplace() 권장)
erase()	특정 원소 삭제
operator[]	특정 키에 해당하는 원소의 값을 참조로 변환. 해당 키의 원소가 없으면 새로운 원소를 기봊값으로 생성하여 참조 반환 (at())
find()	특정 키 값을 갖는 원소를 찾아 반복자를 반환. 원소를 끝까지 찾지 못하면 end()에 해당하는 반복자 반환 (contains())
clear()	모든 원소 삭제
size()	원소의 개수 반환
empty()	map이 비어있으면 true 반환

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
	map<string, int> fruits;	//string값이 key값
	fruits.insert({ "apple", 1000 });	//== fruits.insert(fruits.make_pair("apple", 1000);
	fruits.insert({ "banana", 1500 });
	fruits["orange"] = 3000;
	fruits["grape"] = 4000;
	fruits["lemon"] = 5000;
	fruits["apple"] = 2000;		//값 변경
	fruits["kiwi"];				//0으로 초기화

	fruits.erase("grape");		//key값만 지워도 모두 다 삭제 가능

	for (const auto& p : fruits) {
		cout << p.first << " is " << p.second << " won." << endl;
	}

	/*for (auto [name, price] : fruits)
		cout << name << "is" << price << "won" << endl;
	*/
}