C++ 맵에 대한 정의, 키로값찾기, 값으로키찾기, 시간복잡도

 

---

---

 

이번 글을 통해 배워갈 내용

1.  C++ 맵의 정의
2.  C++ 맵에서 값으로 키 찾기
3.  C++ 맵에서 키로 값 찾기
4.  C++ 버전별 맵에서 키로 값 찾기
5.  C++ 맵의 시간 복잡도에 대한 고찰

---

맵의 정의

맵은 순서에 따라서
키의 값과 그에 맵핑된 값의 조합으로 형성되어진
요소를 저장하는 컨테이너 입니다.

 

쉽게 풀이 하면

key (열쇠) 값을 넣어서 해당되는 value (값)을 가지고 오는

상자(컨테이너) 라고 생각하셔도 좋습니다.

 

맵 예제

C++ 에서 맵은 

#include <map>

최상단에 STL 라이브러리의 하나인 map을 추가하셔서 사용하셔도 되며

 

예제코드를 하단에 적고 그 코드를 통해 설명하겠습니다.

 

#include <iostream>
#include <map>

using namespace std;

class House
{
public:
	string houseName;
	string ownerName;
	House(string houseName,string ownerName)
	{
		this->houseName = houseName;
		this->ownerName = ownerName;
	}
};


int main()
{
	// 집들을 초기화 합니다.
	House h1("myHome1", "Kim1");
	House h2("myHome2", "Kim2");
	House h3("myHome3", "Johnson");
	House h4("myHome4", "Billy");

	// 맵을 초기화 합니다.
	map<int, House> myMap;

	// 맵에 값을 넣습니다.
	myMap.insert({ 1, h1 });
	myMap.insert({ 2, h2 });
	myMap.insert({ 3, h3 });
	myMap.insert({ 4, h4 });

	// 값으로 키를 찾습니다.
	for (auto const& house : myMap)
	{
		if (house.second.ownerName.compare("Billy") == 0)
		{
			cout << "값으로 키 찾기 " << house.second.ownerName  << endl;
		}
	}

	// 키로 값을 찾습니다.
	cout << "키로 값 찾기 " << myMap.at(4).ownerName << endl;

}

 

위에 코드를 보시면

class House
{
public:
	string houseName;
	string ownerName;
	House(string houseName,string ownerName)
	{
		this->houseName = houseName;
		this->ownerName = ownerName;
	}
};

하우스 라는 클래스를 선언 하였고

하우스 클래스에는 생성자와 함께

집이름(houseName) 그리고 집주인이름(ownerName)이 공영(public)변수로 들어 있습니다.

 

---

	// 집들을 초기화 합니다.
	House h1("myHome1", "Kim1");
	House h2("myHome2", "Kim2");
	House h3("myHome3", "Johnson");
	House h4("myHome4", "Billy");

 

main 함수 내에서 집들을 초기화 해줍니다.

 

 

---

	// 맵을 초기화 합니다.
	map<int, House> myMap;

그뒤 맵을 초기화 해주는데

 

맵의 <> 표시 안에

왼쪽에는 key type 예를 들어 위처럼 int

그리고 오른쪽에는 value type을 적어주면 됩니다.

 

---

 

 

키로 값을 찾을 경우

쉽게 맵이름 .at(키값)을 써주시면 됩니다.

 

	// 키로 값을 찾습니다.
	cout << "키로 값 찾기 " << myMap.at(4).ownerName << endl;

---

값으로 키를 찾을 경우

맵을 돌면서 키를 찾아야 해서 조금 비효율 적이며 이는 다음과 같습니다

(C++11이후 버전 형식을 사용하였습니다)

(C++ 11 이후 버전만 실행 가능)

	// 값으로 키를 찾습니다.
	for (auto const& house : myMap)
	{
		// 집주인 명이 빌리라면 0 아니면 0이아님 (compare 함수)
		if (house.second.ownerName.compare("Billy") == 0)
		{
			cout << "값으로 키 찾기 " << house.second.ownerName  << endl;
		}
	}

---

 

C++ 11 이전 버전에서 값으로 키를 찾으시고자 한다면 다음과 같이 쓰실수 있습니다.

	map<int, House>::iterator it;
	for (it = myMap.begin(); it != myMap.end(); it++)
	{
		// 집주인 명이 빌리라면 0 아니면 0이아님 (compare 함수)
		if (it->second.ownerName.compare("Billy") == 0)
		{
			cout << "값으로 키 찾기 " << it->second.ownerName << endl;
		}
	}

(위 코드는 C++ 11, 17, 이전 버전 모두 사용 가능합니다)

 

---

C++ 17은 비쥬얼 스튜디오의 경우 프로젝트에 마우스 우클릭후 설정에서 변경가능하며

 

	for (auto const& [key, val] : myMap)
	{
		// 집주인 명이 빌리라면 0 아니면 0이아님 (compare 함수)
		if (val.ownerName.compare("Billy") == 0)
		{
			cout << key;
			cout << "값으로 키 찾기 " << val.ownerName << endl;
		}
	}

위와 같습니다

 

작성하다 보니 키를 안찾고 다른 값을 찾았네요 ~ ㅎㅎ

지금 와서 깨달았습니다

 

전체 코드를 다시 적습니다

C++ 구버전, C++ 11, C++17

맵 값으로 키 찾기 활용하실 분은 아래 코드 참고하시면 좋을듯 합니다.

 

 

#include <iostream>
#include <map>

using namespace std;

class House
{
public:
	string houseName;
	string ownerName;
	House(string houseName,string ownerName)
	{
		this->houseName = houseName;
		this->ownerName = ownerName;
	}
};


int main()
{
	// 집들을 초기화 합니다.
	House h1("myHome1", "Kim1");
	House h2("myHome2", "Kim2");
	House h3("myHome3", "Johnson");
	House h4("myHome4", "Billy");

	// 맵을 초기화 합니다.
	map<int, House> myMap;

	// 맵에 값을 넣습니다.
	myMap.insert({ 1, h1 });
	myMap.insert({ 2, h2 });
	myMap.insert({ 3, h3 });
	myMap.insert({ 4, h4 });
//////////////////////////////////////////////
// 값으로 키를 찾습니다.
// C++ 11 버전 이후만 실행가능
	for (auto const& house : myMap)
	{
		// 집주인 명이 빌리라면 0 아니면 0이아님 (compare 함수)
		if (house.second.ownerName.compare("Billy") == 0)
		{
			cout << "값으로 키 찾기 " << house.second.ownerName  << endl;
		}
	}
//////////////////////////////////////////////
// 값으로 키를 찾습니다.
// C++ 11 버전 이전도 실행 가능
	map<int, House>::iterator it;
	for (it = myMap.begin(); it != myMap.end(); it++)
	{
		// 집주인 명이 빌리라면 0 아니면 0이아님 (compare 함수)
		if (it->second.ownerName.compare("Billy") == 0)
		{
			cout << "값으로 키 찾기 " << it->second.ownerName << endl;
		}
	}
//////////////////////////////////////////////
// 값으로 키를 찾습니다.
// C++ 17 버전 이후만 실행가능
	for (auto const& [key, val] : myMap)
	{
		// 집주인 명이 빌리라면 0 아니면 0이아님 (compare 함수)
		if (val.ownerName.compare("Billy") == 0)
		{
			cout << key;
			cout << "값으로 키 찾기 " << val.ownerName << endl;
		}
	}
//////////////////////////////////////////////
	// 키로 값을 찾습니다.
	cout << "키로 값 찾기 " << myMap.at(4).ownerName << endl;

}​

 

 

시간 복잡도에 대한 고찰

 

맵의 복잡도의 경우 검색하면서 알게 되었습니다만

확정적인게 아니고

 

일반적으로

 

값을 맵에 넣을때 O(Log(2)N) 에 비례하는게 일반적이며

각 값을 넣는게

거의 O(1)이 들며

값을 전부 넣는게 O(N)정도 든다고 합니다.

아래 스택오버플로우 참조

 

 

또한 std::map은 Red Black Tree를 활용했기 때문에

Access, Search, Insertion, Deletion 모두

시간 복잡도가 O(log(n))이며

공간 복잡도가 O(n) 이라는 글이 있네요

 

---

 

오늘은 즐거운 맵에 대해서 공부해 보았습니다.

 

---

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

https://www.cplusplus.com/reference/map/map/

map - C++ Reference

https://stackoverflow.com/questions/21740893/what-is-the-time-complexity-of-stdmap

What is the time complexity of std::map

https://stackoverflow.com/questions/26281979/c-loop-through-map

C++ Loop through Map

https://www.cplusplus.com/reference/string/string/compare/

string::compare - C++ Reference

C++ Primer

 

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

---