STL 자료구조
🫧벡터 vector
시퀀스 컨테이너이면서 배열기반 메모리 구조를 가졌다.
메모리가 연속된다.
면접에서 많이 물어보는 벡터 질문
- capacity와 size 차이
- vector는 어떤 메모리 구조를 가졌냐.
- 그러므로 어떻게 사용해야 하는지?
자료구조를 공부하는 좋은 방법은 똑같이 만들어보는 것이다.
벡터의 핵심은 데이터와 메모리의 분리이다.
vector
[0][1][2]()()()()()()()
어제만든 IntArray의 Resize
[0][1][2][][][][][][][]벡터는 "크기가 없다"라는 개념이 가능하다. 아무 것도 없는 게 가능하다.
vector의 push_back()
ArrVector.push_back(i); 이 코드를 실행시 push_back()은 두 단계로 과정을 진행한다.
- 메모리를 할당한다. (새로운 확장된 공간을 만든다.)
- 확장된 공간에 데이터를 넣는다.
기존의 배열이 하던 것과 동일한 작업을 한다. 넣어주면서 확장하는 점이 다르다.
Vector의 push_back()의 가장 큰 특징은 데이터를 넣을 때 기존 크기보다 더 크게 확장해서 사용한다는 것이다.
더 크게 확장되면 데이터가 들어가지 않은 공간이 생길 수가 있다.
그래서 실제로 생긴 메모리 공간의 크기가 capacity이고 데이터가 들어있는 공간의 크기가 size이다.
vector를 사용하는 기본 방침과 최적화 관련 이야기
new와 delete는 C++ 기본 연산자 중에서 가장 부하가 심한 연산이다. 최대한 피하려고 한다.
그래서 push_back()을 남발하지 않아야 한다.
capacity가 변한 순간은 곧 배열이 delete되고 다시 새로운 배열이 new가 된 순간이라는 것이다. 즉 부하가 큰 사용법이다.
↓ 그래서 reserve ↓
vector의 reserve()
ArrVector.reserve(10);
- reseve는 미리 capacity를 확장시키고 사용하는 사용법이다.
메모리 공간의 크기의 쓸데 없는 확장이 일어나지 않는다. new와 delete연산이 훨씬 적게 발생한다.
vector의 resize()
ArrVector.resize(10); 얘는 이미 데이터가 10개가 들어간 상황으로 만드는 함수이다. push_back을 10번 한 것과 같다.
vector의 clear()
ArrVector.clear(); 데이터만 clear된다. size는 0이 되고 capacity는 남는다.
이것들을 어제 template으로 만든 Array를 활용해서 MyVector를 만들 거다..
vector의 emplace_back()
ArrVector.emplace_back() push_back과 같은 일을 하는데 생성자로 생성하는 애다.
MyVector로 만들어보면 구현 차이가 이렇다.
(emplace_back 검색해보면 인자를 넣으면 생성자의 인자로 들어간다....)
vector는 push_front() 없음
vector는 list와 다르게 push_front()가 없다. 앞자리에 데이터를 넣기 위해 다른 데이터를 모두 한 칸 밀어야 하기 때문에 vector에게는 어렵다.
🫧자료구조 사용개념
-
vector는 언제 쓰고 왜 썼나?
유동적으로 자료의 크기가 변하는 개념에서 vector는 직관성이 떨어진다. 자료가 한 번 추가되면 그 자료를 삭제하는 것이 어렵고 힘들기 때문이다.- ConsoleObject로 갤러그를 만들려고 했을 때의 경험
→ 해도 되는데 굉장히 까다로운 관리코드를 쳐야 함.
더 직관적인 자료구조 사용하자
- ConsoleObject로 갤러그를 만들려고 했을 때의 경험
🫧노드 Node
자료구조의 메모리의 2가지 형태 중 하나로서
어떠한 데이터가 자기 자신의 데이터의 참조형을 n개 가지면 그걸 노드구조라고 한다.
- 노드를 가장 잘 표현하는 클래스 모양새
단방향 노드
typedef int DataType;
class Node {
public:
DataType Value;
Node* Next = nullptr;
};노드에서 Next에 자기 자신을 참조하는 것은 금기이다.
(과제2로 노드 공부)
과제
🫧과제 1
- TestFunction()을 했을 때 내부 Ptr이 왜 바뀌는지 메모리맵 그려보기
🫧과제 2
아래 코드 메모리맵 그려보고 CurNode만 가지고 Node0부터 Node6까지 다 읽히게 만들기.
#include <iostream>
typedef int DataType;
class Node {
public:
DataType Value;
Node* Next = nullptr;
};
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;
Node* CurNode = &Node0;
std::cout << CurNode->Value << std::endl;
}-
메모리맵
-
코드
while (CurNode != nullptr) {
std::cout << CurNode->Value << std::endl;
CurNode = CurNode->Next;
}- 출력
이전 노드 가리키는 Prev 포인터 추가
Prev추가하면 양방향 노드
역순으로 출력 가능하다.
- 코드
typedef int DataType;
class Node
{
public:
DataType Value;
Node* Next = nullptr;
Node* Prev = nullptr;
};
int main()
{
int Value0;
int Value1;
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;
Node* CurNode = &Node0;
while (nullptr != CurNode)
{
std::cout << CurNode->Value << std::endl;
CurNode = CurNode->Next;
}
std::cout << "----------" << std::endl;
CurNode = &Node6;
while (nullptr != CurNode)
{
std::cout << CurNode->Value << std::endl;
CurNode = CurNode->Prev;
}
}- 코드
