[강의] 12월 26일 수업정리

오늘은 set, insert, pair, string, 해시 테이블에 대한 수업을 들었다.

 

1. set

set은 특정 기준에 따라 원소들이 자동으로 정렬되는 노드 기반 컨테이너이다.

• 기본적으로 오름차순으로 정렬되며, 조건자를 사용하여 내림차순 정렬도 가능하다.
• 유일한 원소만을 가질 수 있는 구조로, 집합(Set)의 의미를 구현된다.
• 내부적으로 균형 이진 탐색 트리(예: Red-Black Tree)로 구현되어, 빠른 시간 내에 원소를 탐색할 수 있다.

 

[ 참고 : 그냥 공부하려고 만든 거지 제대로 된 건 아님, 구조적으로 문제가 있음 (나중에 다시 봐서 알아보자 ) ]

 

1.1 data.h / cpp

#pragma once

class C_DATA
{
private:
int m_nData;

public:
void setData(int nData);
int getData();
};

====================================
#include "data.h"

void C_DATA::setData(int nData)
{
m_nData = nData;
}

int C_DATA::getData()
{
return m_nData;
}

1.2 mgr.h / cpp

#pragma once

#include<set>
#include"data.h"

class C_MGR
{
private:
	std::set<C_DATA*> m_setData;

private:
	C_DATA* createData(int nData);

public:
	C_MGR() = default;
	C_DATA* insert(int nData);
	void earse(C_DATA* pData);
	void print();
};

==============================================
#include "dataMGR.h"

C_DATA * C_MGR::createData(int nData)
{
	C_DATA* pData = new C_DATA{};
	pData->setData(nData);

	return pData;
}

C_DATA* C_MGR::insert(int nData)
{
	C_DATA* pData = createData(nData);

	m_setData.insert(pData);

	return pData;
}

void C_MGR::earse(C_DATA* pData)
{
	std::set<C_DATA*>::iterator iterFind = m_setData.find(pData);
	if (iterFind == m_setData.end())
		return;

	m_setData.erase(iterFind);
	delete pData;
}

void C_MGR::print()
{
	std::set<C_DATA*>::iterator iter = m_setData.begin();

	while (iter != m_setData.end())
	{
		printf("%d ", (*iter)->getData());
		iter++;
	}
	printf("\n");

}

 

 

1.2.1 pair

std::pair<int, float> pData{};

pData.first = 10;
pData.second = 20.f;

printf("%d, %f", pData.first, pData.second);

• pair는 서로 다른 데이터 유형의 두 값을 결합하는 데 사용되는 구조체이다.
• first와 second라는 두 멤버 변수를 가지고 있어, 두 값을 하나의 단위로 묶을 때 유용하다.

 

 

1.2.2 insert

C_DATA* C_MGR::insert(int nData)
{
C_DATA* pData = createData(nData);

m_setData.insert(pData);  

return pData;
}

std::set의 insert의 기본형을 보게 되면 다음과 같다

std::pair<std::set<Key>::iterator, bool> insert(const Key& val);​

여기서 중요한 점은 리턴값으로 pair를 돌려주고 있는데 이 리턴값의 의미를 정확하게 알아야 한다.

• 삽입 성공:
  • iterator: 삽입된 원소의 위치를 가리킴
  • bool: true (중복된 키가 없을 때)
• 삽입 실패:
  • iterator: 중복된 원소의 위치를 가리킴
  • bool: false (중복된 키가 있을 때)

이렇게 리턴값을 반환하고 있다 이점 주의해서 잘 사용할 것

 

1.2.3 find

void C_MGR::earse(C_DATA* pData)
{
std::set<C_DATA*>::iterator iterFind = m_setData.find(pData);
if (iterFind == m_setData.end())
return;

// m_setData.erase(pData); 
m_setData.erase(iterFind);
delete pData;
}

• find 함수는 원소를 검색하는 함수이다.
• 삭제 작업을 할 때 find로 먼저 검색하고, 검색 결과를 기반으로 삭제하는 것이 효율적이다.
• m_setData.erase(pData)를 사용하면 내부적으로 두 번 검색이 이루어지므로, find로 검색한 결과를 이용하는 하여 pData 대신 iterFind 즉, 검색 결과를 넣어주는 게 더 효율적이다.

 

1.3 main.cpp

#include <iostream>
#include "dataMGR.h"

int main()
{
C_MGR cMgr{};
C_DATA* pData{};

cMgr.insert(2);
cMgr.insert(4);
cMgr.insert(1);
cMgr.insert(5);
pData = cMgr.insert(6);

cMgr.print();
cMgr.earse(pData);
cMgr.print();

}

 

 

2. 해시 테이블 

2.1 해시(Hash)

• 해시란 임의 크기의 데이터를 고정 크기 값으로 매핑하는 단방향 함수
• 입력 데이터(키)를 기반으로 매핑된 값을 생성하며, 이 매핑된 값을 해시 값이라고 한다
• 다시 말해, 해시 함수는 키를 고유한 해시 값으로 인코딩하는 함수이다.

 

2.2 해싱(Hashing)

• 해싱은 데이터를 다른 데이터(해시 값)로 변환하는 과정
• 해싱은 고유 데이터를 대상으로 하며, 중복 데이터는 없다.
• 해시 테이블에서 데이터를 효율적으로 저장하기 위해 해싱이 사용된다.

 

2.3 해시 테이블(Hash Table)

• 해시 테이블은 데이터를 (key, value) 쌍으로 저장하는 자료구조.
• 주요 특징은 빠른 검색 속도를 제공한다는 점이다
• 내부적으로 배열 기반 구조를 사용하며, 고유 키를 기반으로 데이터를 저장하고 검색한다.
• 배열을 트리 구조 또는 링크드 리스트 구조와 결합하여 충돌을 처리한다.

 

2.4 std::map을 사용하여 데이터를 저장하고 출력하는 예제

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

int main()
{
	std::map<std::string, int> mapData{};
	std::pair<std::string, int> pairData{};

	pairData.first = "철수";
	pairData.second = 70;

	mapData.insert(pairData);

	std::map<std::string, int>::iterator iter = mapData.begin();

	while (iter != mapData.end())
	{
		printf("%s, %d\n", iter->first.c_str(), iter->second);
		iter++;
	}
}

 

• pairData.first = "철수";와 pairData.second = 70;로 데이터를 pair에 저장한 뒤, mapData.insert(pairData);로 std::map에 삽입.
• 반복자(iterator)를 사용하여 std::map의 데이터를 출력한다.

하지만 간소화된 데이터 삽입 방법이 존재하는데 위의 방식은 std::pair을 별도로 초기화해야 하므로 번거로울 수 있다.

그렇기에 직접 삽입을 하여 간소화가 가능하다. 

 

mapData.insert(std::pair<std::string, int>("철수", 100));

그럼 똑같은 결과가 나오지만 좀 더 편하게 결괏값을 도출해 낼 수 있을 것이다.

 

 

• STL에서 없다는 의미는 end이다.