push_front 함수 구현
void push_front(const T& _Data);- 리스트는 데이터 앞쪽에 입력 갯수와 앞에서 동작시간이 상수 시간이다.
template<typename T>
void List<T>::push_front(const T& _Data)
{
Node<T>* pNewNode = new Node<T>(_Data, m_pHead, nullptr);
if (nullptr != m_pHead)
{
m_pHead->pPrev = pNewNode;
}
else
{
m_pTail = pNewNode;
}
m_pHead = pNewNode;
++m_CurCount;
}-
push_front메소드는 템플릿 타입T의 상수 참조를 인자로 받습니다. 이는 리스트에 추가될 데이터를 나타냅니다. -
새 노드 (
pNewNode)는 동적 메모리 할당을 사용하여 생성됩니다. 새 노드는 데이터 (_Data)로 초기화되며, 다음 포인터 (pNext)는 현재 리스트의 헤드 (m_pHead)를 가리키도록 설정됩니다. 이전 포인터 (pPrev)는nullptr로 초기화되는데, 이것은 새로운 첫 번째 노드가 될 것이기 때문입니다. -
리스트가 비어있지 않은 경우 (
m_pHead가nullptr이 아닌 경우)를 확인합니다. 리스트가 비어있지 않다면:- 현재 헤드의 이전 포인터 (
m_pHead->pPrev)를 새 노드 (pNewNode)를 가리키도록 업데이트합니다.
- 현재 헤드의 이전 포인터 (
-
리스트가 비어있다면 (
m_pHead가nullptr인 경우), 새 노드는 리스트의 꼬리 (m_pTail)가 됩니다 (m_pTail = pNewNode). -
리스트의 헤드를 새 노드로 업데이트합니다 (
m_pHead = pNewNode). -
리스트의 크기 (
m_CurCount)를 증가시켜 새 노드의 추가를 반영합니다.
- 리스트가 비어있는 경우와 이미 노드가 있는 경우 모두를 효과적으로 처리합니다. 새 노드가 리스트의 시작 부분에 올바르게 배치되고 기존 노드들이 (있는 경우) 새 노드와 올바르게 연결되도록 보장합니다.
리스트에 데이터 접근할떄 순회하는 iterator사용해야 한다.
- 리스트는 데이터에 접근할때 느리지만 tail을 구현해도 앞뒤 절반씩.
- tail을 구현해놔도 최악의 경우는 O(n/2)이지만 어차피 O(N)으로 표현된다.
- 데이터의 갯수가 늘어날수록 선형으로 알고리즘 효율이 느려진다.
- (O(n/2))기울기를 줄인것.
- 리스트는 인덱스 접근이 느리기 때문에 특정 인덱스 접근하는 기능을 표준라이브러이에서는 아예없다.
- 근데 가끔 리스트에 인덱스 접근해야 될때 인덱스 접근할려면 우리가 iterator을 사용해야 한다.
stdcharlist.push_back(CharInfo(L"Warrior", 100, 30, 50));
stdcharlist.push_back(CharInfo(L"Archer", 80, 50, 40));
stdcharlist.push_back(CharInfo(L"Wizzard", 50, 100, 20));
list<CharInfo>::iterator listiter = stdcharlist.begin();- 리스트의 시작 iterator을 받아와서 우리 이터레이터가 첫번쨰 컨테이너를 가리키고잇는거니까 넣어놨던 처음 정보가 담겨져있다.
- 리스트에 저장한 단위가 구조체니까 우리가 저장한 구조체 단위니까 하나 생성한 구조체 단위를 하나 넣어놨으니까 근데 우리가 생성시킨 원본은 지역변수고 푸쉬백 함수가 참조 받아가서 힙 메모리 공간에 T 타입을 저장할 노드로 복사시켜놓은것.
- 메모리 구조를 생각하면
- 메인함수에서 집어넣을 임시 구조체를 생성해서 우리 리스트 객체함수에 푸쉬백해서 집어넣으니까 우리 맴버중에 헤드 포인터가 가리키고 있는 곳에 넣을려고 하는 데이터 동일한 함수 넥스트 포인트 프리뷰 포인트를 동적할당해서 거기다 이 데이터를 받아서 복사해서 넣어놓고 리스트에 헤드 포인터가 애를 가리키게한다.
레퍼런스 사용한 이유?
void List<T>::push_back(const T& _Data)- 그렇다면 뭐하러 푸쉬백은 복사를 하는데 왜 레퍼런스를 가져갔냐? 원본이 저장되는게 아닌데.
- 푸쉬백으로 전달되는과정에서 이걸 레퍼런스를 안붙이면 푸쉬백 함수가 호출되고 푸쉬백 함수에서 복사받는거에 대한 똑같은 크기를 하나 만들고 저걸 힙 메모리에 복사했을것이다.
- 복사가 2번일어났을것.
- 그걸 막아줄려고 레퍼런스를 사용했다. 집어넣을 데이터 원본자체를 참조해서 가리킬수 있게 하기위해서 레퍼런스를 사용
- 지역변수(charinfo타입)또 선언해서 또 받아서 또 그걸 다시 노드안으로 생성자 복사가 2번될것을 한번으로 줄였다.
접근 수정하는법.
list<CharInfo>::iterator listiter = stdcharlist.begin();
(*listiter) // 1- 1번처럼 접근하면 정확하게 operator가 정확하게 참조해서 반환했기때문에 .눌러서 수정하면 리스트에 넣어둔(힙영역)에 원본을 조정한다.
실제 데이터 순회 하는 코드
list<CharInfo>::iterator listiter = stdcharlist.begin();
++listiter;
++listiter;
list<CharInfo>::iterator listiter;
for (listiter = stdcharlist.begin(); listiter != stdcharlist.end(); ++listiter)
{
std::wcout << (*listiter).szName << std::endl;
}- 특정 인덱스에 접근할려면 iterator을 이용해서 한땀한땀 해줘야한다.
- 그래서 표준라이브러리는 리스트의 데이터 접근을 할려면 효율이 안좋다는걸 알아야한다.
- 함수를 제공안하는 이유는 다른 컨테이너를 사용하는게 맞기 떄문이다.
std::vector<CharInfo> vecInfo;
for (size_t i = 0; i < vecInfo.size(); ++i)
{
std::wcout << (*listiter).szName << std::endl;
}- 하나의 데이터를 지목해서 접근하는거는 벡터가 리스트보다 빠르지만 전체 데이터를 훑는 상황이면 리스트나 벡터나 순회를해서 출력하는 상황이면 효율이 둘다 n이다.
리스트의 insert함수
listiter = stdcharlist.begin();
++listiter; // 1
stdcharlist.insert(listiter, CharInfo(L"Berserker", 80, 10, 80));
const CharInfo& info = (*listiter);- 리스트만 가지고있다.(벡터 x)
- 1번은 현재 iterator이 아쳐를 가리키고있는 상태(2번째 데이터)
- iterator를 누군가 자기를 가리키고있을텐데 가리키고 있는 사이에 넣어준다.
- 워리어-> 아쳐-> 위자드
- 워리어->버서커->아쳐->위자드
- 가리키고있는 데이터를 입력받을건대 맨앞이나 맨뒤가 아니라 가리키는곳 사이에 낑겨 넣어주는것.
- iterator은 아쳐를 가리키고있다.
listiter = stdcharlist.insert(listiter, CharInfo(L"Berserker", 80, 10, 80));
const CharInfo& info = (*listiter);- 아쳐를 원래 가리키고있던 이터레이터니까 여전히 아쳐를 가리키고있는걸 반환값까지 받아서 iterator을 가리키고있는걸 반환한다.
- 반환값도 iterator이다.
- 입력으로 새롭게 생성된 버서커를 가리키는 이터레이터를 하나를 만들어서 반환한다.
- insert의 반환값을 위위의 코드처럼 안받았다면 입력으로 들어갈떄 iterator이 가리키는 아쳐였겠지만 위의 코드처럼 반환을 받으면 iterator이 버서커를 지목할것이다.
- 워리어 -> 버서커 -> 아쳐 -> 위자드
insert 함수 요약
- _targetIter 가 가리키는곳에 _Data 를 저장시키고, 새로 저장한 데이터를 가리키는 iterator 를 반환해준다.
- iterator insert(iterator _targetIter, const T& _Data);
erase함수 구현
listiter = stdcharlist.begin();
++listiter;
++listiter;- 워리어->버서커-> (아쳐)->위자드인 상황에서 아쳐를 가리키고잇는(타켓팅) 상황
stdcharlist.erase(listiter);- 가리키고있는(타켓팅)을 지워버린다.
- 버서커 - 위자드를 연결해주어야한다.
const CharInfo& charinfo = *listiter;- iterator을 가리키는 곳을 지목하면 예외가 걸린다.
- 가리키는 곳을 지웠기 떄문이당.
listiter = stdcharlist.erase(listiter);
const CharInfo& charinfo = *listiter;- 반환값을 대입을 받아야 예외가 발생하지않는다
- 그래서 지목하는곳을 받아서 보면 위자드가 반환된다.
- 반환타입이 iterator지만 사용한 iterator는 위자드를 가리키는 iterator을 반환한다.
- 삭제된 다음을 가리키는 iterator을 반환한다.
erase 함수 요약
- 제거하는 이터레이터.
- _targetIter 가 가리키는 데이터를 삭제하고, 삭제한 다음을 가리키는 iterator 를 반환
- iterator erase(iterator _targetIter);
erase 문제
- 동적배열은 메모리를 연속적으로 가지고 있기 때문에 erase로 한칸을 지우면 뒤에거를 다 가져와야한다.
vector<int> vecInt;
for (int i = 0; i < 100; ++i)
{
vecInt.push_back(i + 1);
}
vector<int>::iterator veciter = vecInt.begin();
for (; veciter != vecInt.end(); ++veciter)
{
if ((*veciter) <= 50) // 1
{
// vecInt.erase(veciter); // 2
// 돌렸을떄 사진
veciter = vecInt.erase(veciter); // 3
} - 1부터 50을 지우고 51부터 100을 표현하고 싶은 상황이다.
- 1번은 반복문을 돌면서 1~50을 지운다.
- 가리키고 있는 곳을 지우고 있는 거라 iterator은 정상적인 상태가 아니다.
- 리스트랑 벡터둘다 개념적으로 어떤 방식으로 관리하던간에 iterator 가리키고 있던곳이다.
- 그래서 2번은 쓸수 없는 상태가 되어버린다.
- 어떤 컨테이너를 erase를 하면 그 iterator는 이상해진다.
- 3번처럼 대입을 받았으므로 다음 iterator 가리키는 iterator을 반환해준다.
- 1,2,3에서 1을 지웠으니 iterator은 2를 가리킨다.
- 1,2,3,4에서 1지우고 3지우고 5지우고 띄엄띄엄 제거한다.
for (; veciter != vecInt.end(); /*++veciter*/)
{
// 3.5
if ((*veciter) <= 50)
{
veciter = vecInt.erase(veciter);
}
else
{
++veciter;
}- 증가연산을 else로 빼서 밖에서 해줘야 1~50을 지우는 코드가 완성된다.
- for문안에 ++을 적어두면 증가연산이 2번된다
- for문안에서 한번
- veciter = vecInt.erase(veciter) 여기서 한번
- 반환값이 다음을 가리키니까.
erase 요약
- erase 사용하는 경우 iterator가 문제가 되지않게, 삭제된 다음 iterator를 돌려받는 구조 따라서 반복문에서 iterator를 매번 ++ 하는 경우 erase함수와 중복되어서 가리키는 요소를 두번 증가하게 될 수 있다.
List클래스 구현
List클래스의 이너클래스 iterator 클래스의 맴버
public:
class iterator
{
private:
List<T>* m_Owner; // 1
Node<T>* m_TargetNode; // 2
};- 이너클래스를 퍼블릭으로해서 외부에 공개.
- 1번은 리스트를 소유하고 있는 본체를 가져오는것.
- 2번은 리스트는 노드단위로 관리하니 iterator도 노드자체를 맴버로 알면 정확하게 알고있으면 된다.
iterator begin,end 함수 구현
class iterator; // 1
iterator begin()
{
//iterator iter(this, m_pHead); // 2
//return iter // 3
return iterator(this, m_pHead); // 4
}
iterator end()
{
return iterator(this, nullptr); // 5
}- 1번은 iterator이 아래에잇어서 전방선언해준것.
- 4번은 m_pHead를 알려주면 본인의 시작(비긴)을 나타내는 iterator이다.
- 지역변수를 만들자마자 반환할 목적이기때문에 이름을 붙여줄 이유가 없이(임시객체) 반환한다.
- 2+3번을 축약한게 4번이다.
- 5번은 다음 데이터를 nullptr을 가리키고있으면 end고 또한 마지막 노드를 가리킨다면 end가 아니라 end전이당.
- List에서는 end가 이거다라고 규칙 정한것이다.
operator *() 구현
public:
T& operator *() // 1
{
// assert(m_Owner); // 2
// assert(m_TargetNode); // 3
assert(!(!m_Owner || !m_TargetNode)); // 4
// assert( m_Owner && m_TargetNode ); // 5
return m_TargetNode->Data;
}- 1번처럼 원본 참조된걸 줘야 원본 데이터를 건드릴수 있다.
- 본인
- 2번처럼 Owner(List)가 설정되어 있지 않다면 정상적인 iterator이 아니다.
- 정상적인 iterator가 아닌데 데이터 꺼내오라고하니까 사용자가 잘못한것이다.
- 3번처럼 타켓노드가가 nullptr이라는 소리는 해당 리스트가 end를 가리키고있다는 소리기 때문에 어설트 걸어준것이다.
- 2번+3번 == 4번은 Onwer 가 설정되어 있어도, m_TargetNode 가 nullptr이면 End Iterator 이기 때문에 마지막의 다음을 가리키는 상태의 iterator 에게 * 로 접근기능을 쓰면 에러
- 4번이랑 같은거.
operator ++()
void operator ++()
{
assert(m_Owner && m_TargetNode); // 1
m_TargetNode = m_TargetNode->pNext; // 2
}
- 간단해 보이지만 예외처리가 중요하다.
- 1번은 end iterator에서 ++ 하는 경우를 assert
- 2번은 마지막 데이터를 가리키고있어도 문제가 없다.
void operator --()
{
assert(m_Owner && m_TargetNode); // 1
m_Owner->m_pHead == m_TargetNode // 2
{
assert(nullptr);
}
m_TargetNode = m_TargetNode->pPrev; // 3
}- 1번은 end iterator에서 ++ 하는 경우를 assert
- begin일떄 --를 하면 예외처리가 된다.
- 2번에서 iterator가 begin일떄 예외처리를 걸어주어야 한다.
- 2번의 축약 버전
assert(m_Owner->m_pHead != m_TargetNode);- 3번은 전의 데이터를 가리키게 하는것
operator ==(),!=()
bool operator == (const iterator& _otheriter)
{
if (m_Owner == _otheriter.m_Owner && m_TargetNode == _otheriter.m_TargetNode)
return true;
else
return false;
}
bool operator != (const iterator& _otheriter)
{
return !((*this) == _otheriter); // 1
}- ==의 반대경우를 반환하면 된다.
강의 코드
main.cpp
#include <iostream>
#include <vector>
using std::vector;
#include <list>
using std::list;
#include "List.h"
struct CharInfo
{
wchar_t szName[20];
int HP;
int MP;
int SP;
int MaxHP;
int MaxMP;
int MaxSP;
public:
void SetInfo(const wchar_t* _strName, int _HP, int _MP, int _SP)
{
wcscpy_s(szName, _strName);
HP = MaxHP = _HP;
MP = MaxMP = _MP;
SP = MaxSP = _SP;
}
CharInfo()
: HP(0), MP(0), SP(0)
, MaxHP(0), MaxMP(0), MaxSP(0)
{}
CharInfo(const wchar_t* _strName, int _HP, int _MP, int _SP)
: HP(0), MP(0), SP(0)
, MaxHP(0), MaxMP(0), MaxSP(0)
{
SetInfo(_strName, _HP, _MP, _SP);
}
~CharInfo()
{}
};
List<CharInfo> charlist;
list<CharInfo> stdcharlist;
int main()
{
//CharInfo(L"Warrior", 100, 30, 50) - 임시객체, 이름없는 지역변수
charlist.push_back(CharInfo(L"Warrior", 100, 30, 50));
charlist.push_back(CharInfo(L"Archer", 80, 50, 40));
charlist.push_back(CharInfo(L"Wizzard", 50, 100, 20));
stdcharlist.push_back(CharInfo(L"Warrior", 100, 30, 50));
stdcharlist.push_back(CharInfo(L"Archer", 80, 50, 40));
stdcharlist.push_back(CharInfo(L"Wizzard", 50, 100, 20));
list<CharInfo>::iterator listiter;
listiter = stdcharlist.begin();
--listiter;
for (listiter = stdcharlist.begin(); listiter != stdcharlist.end(); ++listiter)
{
std::wcout << (*listiter).szName << std::endl;
}
listiter = stdcharlist.begin();
++listiter;
// list 의 insert 함수 테스트
stdcharlist.insert(listiter, CharInfo(L"Berserker", 80, 10, 80));
const CharInfo& info = (*listiter);
// list 의 erase 함수 테스트
// Warrior - Berserker - (Archer) - Wizzard
listiter = stdcharlist.begin();
++listiter;
++listiter;
listiter = stdcharlist.erase(listiter);
const CharInfo& charinfo = *listiter;
// erase 문제
vector<int> vecInt;
for (int i = 0; i < 100; ++i)
{
// 1 ~ 100 까지 입력
vecInt.push_back(i + 1);
}
// erase 사용하는 경우 iterator 가 문제가 되지 않게, 삭제된 다음 iterator 를 돌려받는 구조
// 따라서 반복문에서 iterator 를 매번 ++ 하는 경우 erase 함수와 중복되어서
// 가리키는 요소를 두번 증가하게 될 수 있다.
vector<int>::iterator veciter = vecInt.begin();
for (; veciter != vecInt.end();)
{
if ((*veciter) <= 50)
{
veciter = vecInt.erase(veciter);
}
else
{
++veciter;
}
}
return 0;
}List.h
#pragma once
#include <assert.h>
template<typename T>
struct Node
{
T Data;
Node<T>* pNext;
Node<T>* pPrev;
Node()
: Data()
, pNext(nullptr)
, pPrev(nullptr)
{}
Node(const T& _Data, Node<T>* _Next, Node<T>* _Prev)
: Data(_Data)
, pNext(_Next)
, pPrev(_Prev)
{}
};
template<typename T>
class List
{
private:
Node<T>* m_pHead;
Node<T>* m_pTail;
int m_CurCount;
public:
void push_back(const T& _Data);
void push_front(const T& _Data);
class iterator;
iterator begin() { return iterator(this, m_pHead); }
iterator end() { return iterator(this, nullptr); }
// _targetIter 가 가리키는곳에 _Data 를 저장시키고, 새로 저장한 데이터를 가리키는 iterator 를 반환해준다.
// iterator insert(iterator _targetIter, const T& _Data);
// _targetIter 가 가리키는 데이터를 삭제하고, 삭제한 다음을 가리키는 iterator 를 반환
// iterator erase(iterator _targetIter);
public:
List()
: m_pHead(nullptr)
, m_pTail(nullptr)
, m_CurCount(0)
{}
~List()
{
Node<T>* pNode = m_pHead;
while (pNode)
{
Node<T>* pNext = pNode->pNext;
delete pNode;
pNode = pNext;
}
}
public:
class iterator
{
private:
List<T>* m_Owner;
Node<T>* m_TargetNode;
public:
T& operator *()
{
// Owner(List) 가 설정되어있지 않으면, 정상적인 iterator 가 아니다.
// Owner 가 설정되어 있어도, m_TargetNode 가 nullptr 이면 End Iterator 이기 때문에
// 마지막의 다음을 가리키는 상태의 iterator 에게 * 로 접근기능을 쓰면 에러
assert(m_Owner && m_TargetNode);
return m_TargetNode->Data;
}
// 1. ++, -- 반환타입 문제
// 2. ++, -- 후위연산자 문제
void operator ++()
{
// enditerator 에서 ++ 하는 경우
assert(m_Owner && m_TargetNode);
m_TargetNode = m_TargetNode->pNext;
}
void operator --()
{
assert(m_Owner && m_TargetNode);
assert(m_Owner->m_pHead != m_TargetNode); // iterator 가 begin 이다.
m_TargetNode = m_TargetNode->pPrev;
}
bool operator == (const iterator& _otheriter)
{
if (m_Owner == _otheriter.m_Owner && m_TargetNode == _otheriter.m_TargetNode)
return true;
else
return false;
}
bool operator != (const iterator& _otheriter)
{
return !((*this) == _otheriter);
}
public:
iterator()
: m_Owner(nullptr)
, m_TargetNode(nullptr)
{}
iterator(List<T>* _Owner, Node<T>* _TargetNode)
: m_Owner(_Owner)
, m_TargetNode(_TargetNode)
{}
~iterator()
{}
};
};
template<typename T>
void List<T>::push_back(const T& _Data)
{
Node<T>* pNewNode = new Node<T>(_Data, nullptr, nullptr);
if (0 == m_CurCount) //nullptr == m_pHead)
{
m_pHead = pNewNode;
m_pTail = pNewNode;
}
else
{
m_pTail->pNext = pNewNode;
pNewNode->pPrev = m_pTail;
m_pTail = pNewNode;
}
++m_CurCount;
}
template<typename T>
inline void List<T>::push_front(const T& _Data)
{
Node<T>* pNewNode = new Node<T>(_Data, m_pHead, nullptr);
if (nullptr != m_pHead)
{
m_pHead->pPrev = pNewNode;
}
else
{
m_pTail = pNewNode;
}
m_pHead = pNewNode;
++m_CurCount;
}1차 23.12.29
2차 24.01.02
3차 24.01.03
4차 24.01.04
5차 24.01.05
:D