Inner Class
어떤 개념의 하위 개념을 표현한다. 어떤 개념 안에 있는 멤버 변수들을 개념 안에 묶는다.
인벤토리라는 개념이 있을 때, 그 인벤토리라는 개념 안에 인텐토리 아이콘이라는 개념이 속한다.
Class 안에 Inner Class를 만들 수 있다. InventoryIcon 클래스를 Inventory 클래스 내에서만 사용하고 싶다면 private, 외부에서도 InventoryIcon 클래스를 사용한다면 public으로 두면 된다.
#include<vector>
class Image {
};
class Inventory {
public:
class InventoryIcon {
Image Image;
int Count;
};
std::vector<InventoryIcon> Icons;
};
int main()
{
Inventory Inventory;
Inventory::InventoryIcon Icon;
}Inner Class에서 바깥 클래스의 변수 사용 불가하다. 그냥 밖에 있는 클래스랑 다를 게 없음.
friend 문법
- A클래스에 B클래스를 friend로 설정하면 B클래스에서 A클래스의 멤버 변수나 함수를 사용할 수 있다.
('class' 를 붙인 건 전방선언임)
- friend로 설정하면 그 클래스나 함수에 접근 권한을 주는 것 같다..
A클래스에서 B클래스를 friend로 설정했기 때문에 B클래스에서 A클래스의 private 멤버까지도 접근할 수 있다.
https://learn.microsoft.com/ko-kr/cpp/cpp/friend-cpp?view=msvc-170
STL 자료구조
🍌List 리스트
헤더 #include <list>
- std::list는 앞과 뒤로 연결되어 있기 때문에 양방향 리스트라고 부르고 그 안에 존재하는 노드는 양방향 노드라고 부른다.
- list는 구조상 한 번에 n번째 노드의 값에 접근하는 것이 불가능하다.
- push_back()되고 push_front()도 된다.
- 넣은 순서대로 나온다.
🍌MyList
안에 더미노드방식으로 ListNode 만들어서 사용한다.
push_back()
End 노드의 Prev에 새로운 데이터를 넣겠다.
새로운 노드의 Prev는 무조건 End의 Prev.
void push_back(const DataType& _Data){
ListNode* NewNode = new ListNode();
NewNode->Data = _Data;
//새로운 노드의 Prev는 항상 바뀐다.
NewNode->Next = End;
NewNode->Prev = End->Prev;
// 새로 생긴 노드의 앞과 뒤에게 이제 자신이 그들의 앞과 뒤라는 것을 알려준다.
ListNode* PrevNode = NewNode->Prev; // 내 앞
ListNode* NextNode = NewNode->Next; // 내 뒤
PrevNode->Next = NewNode;
NextNode->Prev = NewNode;
}push_front()
Start 노드의 Next에 새로운 데이터를 넣겠다.
(과제1에 자세히)
iterator
std의 거의 모든 자료구조는 iterator 라는 통일된 인터페이스를 사용한다.
이유는 순회를 돌리는 방식이 각 자료구조마다 다르기 때문이다.
그 인터페이스를 순회를 돌려주는 순회자라는 클래스를 만들고 똑같은 방식으로 이용하게 해서 진입장벽을 낮춘 것이다.
- MyList 클래스의 Inner Class인 iterator와 begin(), end()를 보면 된다.
class MyList
{
private:
class ListNode
{
public:
DataType Data = DataType();
ListNode* Next = nullptr;
ListNode* Prev = nullptr;
};
public:
class iterator
{
public:
iterator(ListNode* _CurNode)
: CurNode(_CurNode)
{
}
bool operator!=(const iterator& _Other)
{
return CurNode != _Other.CurNode;
}
DataType& operator*()
{
return CurNode->Data;
}
void operator++()
{
CurNode = CurNode->Next;
}
private:
ListNode* CurNode = nullptr;
};
MyList()
{
Start->Next = End;
End->Prev = Start;
}
iterator begin()
{
return iterator(Start->Next);
}
iterator end()
{
return iterator(End);
}
/* MyList 구현 내용 일부 생략 */
}
protected:
private:
ListNode* Start = new ListNode();
ListNode* End = new ListNode();
};- main에서 사용할 때
MyList::iterator StartIter = NewList.begin();
MyList::iterator EndIter = NewList.end();
for ( ; StartIter != EndIter; ++StartIter)
{
std::cout << *StartIter << std::endl;
// std::cout << StartIter .operator*() << std::endl;
}leak 관리
Start부터 End까지 다 지워야 함
~MyList() {
ListNode* Node = Start;
while (Node != nullptr) {
ListNode* tmp = Node->Next;
delete Node;
Node = tmp;
}
Node = nullptr;
}MyList 사용 예시
std::cout << "내 리스트" << std::endl;
MyList NewList = MyList();
for (int i = 0; i < 10; i++)
{
NewList.push_front(i);
// NewList.push_front();
}
MyList::iterator StartIter = NewList.begin();
MyList::iterator EndIter = NewList.end();
// 안된다.,
//NewList[5];
StartIter = NewList.erase(StartIter);
for (/*std::list<int>::iterator StartIter = NewList.begin()*/
; StartIter != EndIter
; ++StartIter
)
{
int& Value = *StartIter;
StartIter.operator*();
StartIter.operator*() += 10;
StartIter.operator*() += 20;
std::cout << *StartIter << std::endl;
// std::cout << StartIter.operator*() << std::endl;
}🍌Map 기초
트리 구조
연관 컨테이너, 노드형
트리 구조 노드 중에서 자식의 개수가 2개일 때 2진 트리라고 한다.
노드를 넣을 때 크기 비교를 하게 되면 써치 트리라고 한다.
→ Map은 2진 써치 트리
그 중에도
→ 레드블랙 바이너리 써치트리 (= 레드블랙트리)
Map은 기본적으로 (속도보다)탐색과 정렬에 특화되어 있는 자료구조입니다.
트리 문제점 : 편향트리
트리의 기본적인 단점은 편향트리가 생길 수 있다는 점이다.
레드블랙 알고리즘은 스핀이라는 알고리즘을 통해서 트리의 균형을 잡아준다.
→ 레드블랙 자가균형 2진 트리 라고 부른다.
언리얼에서는 모든 자료구조가 전부 배열형 메모리를 가진 자료구조이다. 노드형이 없다고 한다. 신기함..
과제
🍌과제 1 push_front() 만들기
- push_back()과 비슷하지만 새 데이터가 들어가는 위치 논리만 다르다.
// in MyList class
void push_back(const DataType& _Data)
{
ListNode* NewNode = new ListNode();
NewNode->Data = _Data;
NewNode->Next = End;
NewNode->Prev = End->Prev;
ListNode* PrevNode = NewNode->Prev;
ListNode* NextNode = NewNode->Next;
PrevNode->Next = NewNode;
NextNode->Prev = NewNode;
}
// Start의 Next에 새로운 데이터를 넣겠다.
void push_front(const DataType& _Data)
{
// 역함수
ListNode* NewNode = new ListNode();
NewNode->Data = _Data;
NewNode->Prev = Start;
NewNode->Next = Start->Next;
ListNode* PrevNode = NewNode->Prev;
ListNode* NextNode = NewNode->Next;
PrevNode->Next = NewNode;
NextNode->Prev = NewNode;
}🍌과제 2 leak 없애기
모든 노드를 지워줘야 하는데 지우고 나면 Node->Next를 알 수 없으므로 임시로 받아두는 포인터를 만들었다.
- MyList 클래스의 소멸자
~MyList() {
ListNode* Node = Start;
while (Node != nullptr) {
ListNode* tmp = Node->Next;
delete Node;
Node = tmp;
}
Node = nullptr;
}🍌과제 3 reverse_iterator 구현
내 코드
iterator 클래스를 복사해서 reverse_iterator 클래스를 만들었다. 그 안에서 operator++와 rbegin(), rend()를 조금 수정했다.
#include <iostream>
#include <list>
#include <ConsoleEngine/EngineDebug.h>
typedef int DataType;
class MyList
{
private:
class ListNode
{
public:
DataType Data = DataType();
ListNode* Next = nullptr;
ListNode* Prev = nullptr;
};
public:
class iterator
{
friend MyList;
public:
iterator()
{
}
iterator(ListNode* _CurNode)
: CurNode(_CurNode)
{
}
bool operator!=(const iterator& _Other)
{
return CurNode != _Other.CurNode;
}
DataType& operator*()
{
return CurNode->Data;
}
// 연산자 겹지정 중에
void operator++()
{
CurNode = CurNode->Next;
}
private:
ListNode* CurNode = nullptr;
};
class reverse_iterator
{
friend MyList;
public:
reverse_iterator()
{
}
reverse_iterator(ListNode* _CurNode)
: CurNode(_CurNode)
{
}
bool operator!=(const reverse_iterator& _Other)
{
return CurNode != _Other.CurNode;
}
DataType& operator*()
{
return CurNode->Data;
}
// 연산자 겹지정 중에
void operator++()
{
CurNode = CurNode->Prev;
}
private:
ListNode* CurNode = nullptr;
};
MyList()
{
Start->Next = End;
End->Prev = Start;
}
~MyList()
{
ListNode* CurNode = Start;
while (CurNode)
{
ListNode* Next = CurNode->Next;
if (nullptr != CurNode)
{
delete CurNode;
CurNode = Next;
}
}
}
iterator begin()
{
return iterator(Start->Next);
}
iterator end()
{
return iterator(End);
}
reverse_iterator rbegin() {
return reverse_iterator(End->Prev);
}
reverse_iterator rend() {
return reverse_iterator(Start);
}
// End의 Prev에 새로운 데이터를 넣겠다.
void push_back(const DataType& _Data)
{
ListNode* NewNode = new ListNode();
NewNode->Data = _Data;
NewNode->Next = End;
NewNode->Prev = End->Prev;
ListNode* PrevNode = NewNode->Prev;
ListNode* NextNode = NewNode->Next;
PrevNode->Next = NewNode;
NextNode->Prev = NewNode;
}
// Start의 Next에 새로운 데이터를 넣겠다.
void push_front(const DataType& _Data)
{
// 역함수
ListNode* NewNode = new ListNode();
NewNode->Data = _Data;
NewNode->Prev = Start;
NewNode->Next = Start->Next;
ListNode* PrevNode = NewNode->Prev;
ListNode* NextNode = NewNode->Next;
PrevNode->Next = NewNode;
NextNode->Prev = NewNode;
}
iterator erase(iterator& _Iter)
{
if (_Iter.CurNode == Start)
{
MsgBoxAssert("Start를 삭제하려고 했습니다.");
}
if (_Iter.CurNode == End)
{
MsgBoxAssert("End를 삭제하려고 했습니다.");
}
iterator ReturnIter;
if (nullptr != _Iter.CurNode)
{
ReturnIter = iterator(_Iter.CurNode->Next);
ListNode* PrevNode = _Iter.CurNode->Prev;
ListNode* NextNode = _Iter.CurNode->Next;
PrevNode->Next = NextNode;
NextNode->Prev = PrevNode;
if (nullptr != _Iter.CurNode)
{
delete _Iter.CurNode;
_Iter.CurNode = nullptr;
}
}
return ReturnIter;
}
protected:
private:
ListNode* Start = new ListNode();
ListNode* End = new ListNode();
};
int main()
{
LeakCheck;
{
std::cout << "std 리스트" << std::endl;
std::list<int> NewList = std::list<int>();
// 0, 1, 2, 3, 4
for (int i = 0; i < 5; i++)
{
NewList.push_back(i);
// NewList.push_front();
}
std::list<int>::reverse_iterator rStartIter = NewList.rbegin();
std::list<int>::reverse_iterator rEndIter = NewList.rend();
for (/*std::list<int>::iterator StartIter = NewList.begin()*/
; rStartIter != rEndIter
; ++rStartIter)
{
std::cout << *rStartIter << std::endl;
}
}
{
std::cout << "내 리스트" << std::endl;
MyList NewList = MyList();
for (int i = 0; i < 5; i++) {
NewList.push_back(i);
}
MyList::reverse_iterator rStartIter = NewList.rbegin();
MyList::reverse_iterator rEndIter = NewList.rend();
for (; rStartIter != rEndIter; ++rStartIter) {
std::cout << *rStartIter << std::endl;
}
}
}선생님 코드
선생님은 iterator와 reverse_iterator의 공통된 부분을 iterator_Base 클래스로 뽑아 상속시켰다.
#include <iostream>
#include <list>
#include <ConsoleEngine/EngineDebug.h>
typedef int DataType;
// template<typename DataType>
class MyList
{
private:
class ListNode
{
public:
DataType Data = DataType();
ListNode* Next = nullptr;
ListNode* Prev = nullptr;
};
private:
class iterator_Base
{
public:
iterator_Base()
{
}
iterator_Base(ListNode* _CurNode)
: CurNode(_CurNode)
{
}
bool operator!=(const iterator_Base& _Other)
{
return CurNode != _Other.CurNode;
}
DataType& operator*()
{
return CurNode->Data;
}
public:
ListNode* CurNode = nullptr;
};
public:
class iterator : public iterator_Base
{
public:
iterator()
{
}
iterator(ListNode* _CurNode)
: iterator_Base(_CurNode)
{
}
// 연산자 겹지정 중에
void operator++()
{
CurNode = CurNode->Next;
}
};
class reverse_iterator : public iterator_Base
{
friend MyList;
public:
reverse_iterator()
{
}
reverse_iterator(ListNode* _CurNode)
: iterator_Base(_CurNode)
{
}
void operator++()
{
CurNode = CurNode->Prev;
}
protected:
};
MyList()
{
Start->Next = End;
End->Prev = Start;
}
~MyList()
{
ListNode* CurNode = Start;
while (CurNode)
{
ListNode* Next = CurNode->Next;
if (nullptr != CurNode)
{
delete CurNode;
CurNode = Next;
}
}
}
iterator begin()
{
return iterator(Start->Next);
}
iterator end()
{
return iterator(End);
}
// End의 Prev에 새로운 데이터를 넣겠다.
void push_back(const DataType& _Data)
{
ListNode* NewNode = new ListNode();
NewNode->Data = _Data;
NewNode->Next = End;
NewNode->Prev = End->Prev;
ListNode* PrevNode = NewNode->Prev;
ListNode* NextNode = NewNode->Next;
PrevNode->Next = NewNode;
NextNode->Prev = NewNode;
}
// Start의 Next에 새로운 데이터를 넣겠다.
void push_front(const DataType& _Data)
{
// 역함수
ListNode* NewNode = new ListNode();
NewNode->Data = _Data;
NewNode->Prev = Start;
NewNode->Next = Start->Next;
ListNode* PrevNode = NewNode->Prev;
ListNode* NextNode = NewNode->Next;
PrevNode->Next = NewNode;
NextNode->Prev = NewNode;
}
iterator erase(iterator& _Iter)
{
if (_Iter.CurNode == Start)
{
MsgBoxAssert("Start를 삭제하려고 했습니다.");
}
if (_Iter.CurNode == End)
{
MsgBoxAssert("End를 삭제하려고 했습니다.");
}
iterator ReturnIter;
if (nullptr != _Iter.CurNode)
{
ReturnIter = iterator(_Iter.CurNode->Next);
ListNode* PrevNode = _Iter.CurNode->Prev;
ListNode* NextNode = _Iter.CurNode->Next;
PrevNode->Next = NextNode;
NextNode->Prev = PrevNode;
if (nullptr != _Iter.CurNode)
{
delete _Iter.CurNode;
_Iter.CurNode = nullptr;
}
}
return ReturnIter;
}
reverse_iterator rbegin()
{
return reverse_iterator(End->Prev);
}
reverse_iterator rend()
{
return reverse_iterator(Start);
}
protected:
private:
ListNode* Start = new ListNode();
ListNode* End = new ListNode();
};
int main()
{
LeakCheck;
{
std::cout << "std 리스트" << std::endl;
std::list<int> NewList = std::list<int>();
// 0, 1, 2, 3, 4
for (int i = 0; i < 5; i++)
{
NewList.push_back(i);
// NewList.push_front();
}
std::list<int>::reverse_iterator rStartIter = NewList.rbegin();
std::list<int>::reverse_iterator rEndIter = NewList.rend();
for (/*std::list<int>::iterator StartIter = NewList.begin()*/
; rStartIter != rEndIter
; ++rStartIter)
{
std::cout << *rStartIter << std::endl;
}
}
{
std::cout << "내 리스트" << std::endl;
MyList NewList = MyList();
// 0, 1, 2, 3, 4
for (int i = 0; i < 5; i++)
{
NewList.push_back(i);
// NewList.push_front();
}
MyList::reverse_iterator rStartIter = NewList.rbegin();
MyList::reverse_iterator rEndIter = NewList.rend();
for (/*std::list<int>::iterator StartIter = NewList.begin()*/
; rStartIter != rEndIter
; ++rStartIter)
{
std::cout << *rStartIter << std::endl;
}
}
}
일단 시작해보자