자료구조
자료구조를 코딩으로 공부하는 가장 좋은 방법 ⇒ 똑같이 구현해보기!
💡 자료구조의 분류
기준 | 컨테이너 | 메모리형태(참고) ----- | ----- | ----- vector | 시퀀스 | 배열 list | 시퀀스 | 노드 map | 연관 | string | 어댑터 | stack | 어댑터 | queue | 어댑터 |
vector
/*
[Vector]
- 시퀸스 컨테이너의 일종
- 배열기반 메모리 구조를 가지고 있다.
[][][][][][][][]...
(+)
웬만한 자료구조보다 훨씬 빠른 자료구조에 해당한다.
(-)
유동적으로 자료의 크기가 변하는 개념을 표현할 때에는 알맞지 않다.
자료가 한 번 추가되면 그 자료를 삭제하는 것이 어렵고 힘들기 때문이다.
한 번 push_back() 해서 확장된 공간을 줄이는 것도 어렵다.
*/
#include <iostream>
#include <vector>
#include <list>
#include <Windows.h>
#include <assert.h>
template<typename DataType>
class CArray
{
public:
CArray()
{
}
CArray(int _Size)
{
ReSize(_Size);
}
CArray(const CArray& _Other)
{
Copy(_Other);
}
~CArray()
{
Release();
}
void operator=(const CArray& _Other)
{
Copy(_Other);
}
DataType& operator[](int _Count)
{
return ArrPtr[_Count];
}
int Num()
{
return NumValue;
}
void Copy(const CArray& _Other)
{
NumValue = _Other.NumValue;
ReSize(NumValue);
for (int i = 0; i < NumValue; i++)
{
ArrPtr[i] = _Other.ArrPtr[i];
}
}
void ReSize(int _Size)
{
if (0 >= _Size)
{
MessageBoxA(nullptr, "배열의 크기가 0일수 없습니다", "치명적 에러", MB_OK);
assert(false);
}
DataType* Ptr = ArrPtr;
ArrPtr = new DataType[_Size];
int CopySize = NumValue <= _Size ? NumValue : _Size;
for (int i = 0; i < CopySize; i++)
{
ArrPtr[i] = Ptr[i];
}
NumValue = _Size;
if (nullptr != Ptr)
{
delete[] Ptr;
Ptr = nullptr;
}
}
void Release()
{
if (nullptr != ArrPtr)
{
delete[] ArrPtr;
ArrPtr = nullptr;
}
}
private:
int NumValue = 0;
DataType* ArrPtr = nullptr;
};
// CArray를 이용한 MyVector 구현
template<typename DataType>
class MyVector
{
public:
DataType& operator[](size_t _Index)
{
if (size() <= _Index)
{
MessageBoxA(nullptr, "인덱스를 넘겨서 접근하려고 했습니다.", "치명적 에러", MB_OK);
assert(false);
}
return Array[_Index];
}
void push_back(const DataType& _Data)
{
if (sizeValue + 1 >= capacity())
{
Array.ReSize((Array.Num() + 1) * 2);
}
Array[sizeValue] = _Data;
++sizeValue;
}
void emplace_back()
{
if (sizeValue + 1 >= capacity())
{
Array.ReSize((Array.Num() + 1) * 2);
}
Array[sizeValue] = DataType();
++sizeValue;
}
void resize(int _Size)
{
sizeValue = _Size;
Array.ReSize(_Size);
}
void reserve(int _Size)
{
Array.ReSize(_Size);
}
void clear()
{
sizeValue = 0;
}
size_t size()
{
return sizeValue;
}
size_t capacity()
{
return Array.Num();
}
protected:
private:
int sizeValue = 0;
CArray<int> Array;
};
int main()
{
/*
std::vector<int>();
=>
- 내부에서 resize()를 실행한다
- 크기가 없는 vector를 만들 수 있다 (이후에 push_back() 등으로 추가)
puch_back();
=> 메모리를 할당하고, 할당한 메모리에 데이터를 넣는다
- 공간을 확장하는 순서
확장된 공간을 새로이 만든다 -> 기존의 데이터를 확장된 공간에 복사해준다
-> 기존의 공간을 delete한다 -> 확장된 공간을 vector 안에 넣어준다
-> 추가할 데이터를 확장된 공간에 넣어준다
- 확장 시 필요한 크기보다 좀 더 크게 확장한다
- 데이터가 들어가 있는 공간의 크기 : size()
- 실제 vector 크기 : capacity()
- 이 때문에 데이터가 들어가 있지 않은 공간이 생긴다 (capacity - size 만큼)
emplace_back();
=> push_back()과 동일하지만, 공간만 확장시킨다
resize();
=> 미리 push_back()을 n번 해서 확장해준다
- 직접적으로 resize()를 쓰지는 않는 것 같다...아마도
reserve();
=> 미리 데이터 n개를 확실히 사용하겠다고 capacity를 정해 확장해준다
- capacity가 변할 때 기존의 배열이 delete되고 새로운 배열이 new되는 것인데,
C++에서 new와 delete는 가장 부하가 심한 연산에 포함된다
- 따라서 vector 사용 전에 reserve()해주면 부하를 줄일 수 있다
- 이 때문에 vector는 크기를 확장할 수 있는 정적배열로서 사용된다
clear();
=> vector 내부의 데이터를 전부 지운다
- size를 0으로 만들어준다
- capacity는 해당되지 않기 때문에, 실제론 vector가 존재하는 것과 같다
*/
{
std::cout << "Std Vector" << std::endl;
std::vector<int> ArrVector = std::vector<int>();
for (int i = 0; i < 10; i++)
{
ArrVector.emplace_back(); // ArrVector.push_back(i);
std::cout << "capacity : " << ArrVector.capacity() << std::endl;
std::cout << "size : " << ArrVector.size() << std::endl;
}
ArrVector.clear();
std::cout << "Clear " << std::endl;
std::cout << "capacity : " << ArrVector.capacity() << std::endl;
std::cout << "size : " << ArrVector.size() << std::endl;
}
{
std::cout << std::endl;
std::cout << "MyVector" << std::endl;
MyVector<int> ArrVector = MyVector<int>();
for (int i = 0; i < 10; i++)
{
ArrVector.emplace_back(); // ArrVector.push_back(i);
std::cout << "capacity : " << ArrVector.capacity() << std::endl;
std::cout << "size : " << ArrVector.size() << std::endl;
}
ArrVector.clear();
std::cout << "Clear " << std::endl;
std::cout << "capacity : " << ArrVector.capacity() << std::endl;
std::cout << "size : " << ArrVector.size() << std::endl;
}
{
// 다른 자료구조와의 차이점
/*
1. 정적배열과의 차이점
- 벡터는 공간과 데이터의 개념을 분리한다(중요!)
- 공간이 할당된 것과 데이터가 들어가 있는 것은 별개
*/
int Arr[10];
Arr[0] = 20; // [20][?][?][?][?][?][?][?][?][?]
Arr[2]; // 배열에서는 가능, 벡터에서는 불가능
/*
2. list와의 차이점
- list에는 존재하는 push_front()가 불가능하다
- 데이터의 복사가 구성원의 수만큼 일어나야 하기 때문에 엄청난 부담이기 때문
*/
std::list<int> MyList;
MyList.push_back(0);
MyList.push_front(0);
}
}// 궁금해서 찾아본...
// Q) 혹시 한 인덱스의 데이터를 erase()로 삭제하게 되면 어떤일이 발생할까?
#include <iostream>
#include <vector>
int main()
{
std::vector<int> ArrVector = std::vector<int>();
for (int i = 0; i < 10; i++)
{
ArrVector.push_back(i); // [0][1][2][3][4][5][6][7][8][9]
}
std::cout << "capacity : " << ArrVector.capacity() << std::endl; // 13
std::cout << "size : " << ArrVector.size() << std::endl; // 10
ArrVector.erase(ArrVector.begin() + 3);
// [0][1][2][?][4][5][6][7][8][9] (X)
// [0][1][2][4][5][6][7][8][9] (O)
for (int i = 0; i < ArrVector.size(); i++)
{
std::cout << ArrVector[i] << std::endl;
std::cout << reinterpret_cast<int>(&ArrVector[i]) << std::endl; // 4씩 차이난다
}
std::cout << "capacity : " << ArrVector.capacity() << std::endl; // 13
std::cout << "size : " << ArrVector.size() << std::endl; // 9
}
// size가 1 줄어든다
// capacity는 변하지 않는다
// erase된 index 3 이후의 데이터들이 앞으로 한 칸씩 이동한다
// 결과적으로 index 8 까지만 데이터가 차있는 배열이 된다💡int라도, vector라도, class라도 얼마든지 같은 경우이다!
복잡하다고 생각하지 말고 int로 치환해서 생각해보자#include <iostream> class Test { public: void TestFunction() { *Ptr = 20; // Ptr.push_back(20); } public: int* Ptr; // std::vector<int>* Ptr; }; int main() { _CrtSetDbgFlag(_CRTDBG_LEAK_CHECK_DF | _CRTDBG_ALLOC_MEM_DF); int Value = 0; // std::vector<int> Value; Test NewTest; NewTest.Ptr = &Value; NewTest.TestFunction(); } // int 자리에 다른 자료형을 넣어도 같은 원리로 작동한다
node
/*
[Node]
- 자료구조의 두가지 메모리 형태 중 하나
- 어떠한 데이터가 자신의 참조형을 n개 가진 형태이다.
(+)
중간 index에 접근하여 데이터를 추가하거나 삭제하기 용이하다.
*/
#include <iostream>
#include <vector>
typedef int DataType;
class Node
{
public:
DataType Value;
Node* Next = nullptr;
Node* Prev = nullptr;
};
// 노드 활용 e.g.
class Zone
{
public:
std::vector<Zone*> LinkZone; // 현재 지역에서 연결된 지역들
};
int main()
{
Node Node0;
Node Node1;
Node Node2;
Node Node3;
Node Node4;
Node Node5;
Node Node6;
Node0.Value = 0;
Node1.Value = 1;
Node2.Value = 2;
Node3.Value = 3;
Node4.Value = 4;
Node5.Value = 5;
Node6.Value = 6;
Node0.Next = &Node1;
Node1.Next = &Node2;
Node2.Next = &Node3;
Node3.Next = &Node4;
Node4.Next = &Node5;
Node5.Next = &Node6;
Node1.Prev = &Node0;
Node2.Prev = &Node1;
Node3.Prev = &Node2;
Node4.Prev = &Node3;
Node5.Prev = &Node4;
Node6.Prev = &Node5;
// 가장 처음 노드에서 마지막 노드까지 Value 출력
Node* CurNode = &Node0;
while (CurNode != nullptr)
{
std::cout << CurNode->Value << std::endl;
CurNode = CurNode->Next;
}
// 가장 마지막 노드에서 처음 노드까지 Value 출력
CurNode = &Node6;
while (nullptr != CurNode)
{
std::cout << CurNode->Value << std::endl;
CurNode = CurNode->Prev;
}
}
⋆꙳⊹⋰ 𓇼⋆ 𝑻𝑰𝑳 𝑨𝑹𝑪𝑯𝑰𝑽𝑬 ⸝·⸝⋆꙳⊹⋰