C++ 기초 : list iterator

---

직접 구현한 list 클래스에도

iterator를 구현하겠습니다.

 

일단 list 역할은 하는 cList 클래스에

inner 클래스인 iterator를 만듭니다.

 

list에서 iterator가 갖고 있어야 하는 정보는

어떤 list가 관리하는 노드인가,

즉 list의 주솟값을 알아야 하고

어떤 노드를 가리킬 것인가

즉 node의 주솟값을 알아야 합니다.

 

해당 iterator가 사용할 수 있는지,

사용할 수 없는지 확인할 수 있는

멤버 bValid도 만들었습니다.

 

 

이후 iterator의 생성자와 소멸자를 만듭니다.

 

기본 생성자는 list를 가리키는 m_pList와 

노드를 가리키는 m_pNode의 값을 이니셜라이저를 통해

nullptr로 초기화합니다. 이렇게 만들어진 iterator는 

사용할 수 없는 iterator이므로 bValid의 값을 false로 둡니다.

 

 

list의 주솟값과 노드의 주솟값을 인자로 받는

생성자의 경우 m_pList를 list의 주솟값으로,

m_pNode를 노드의 주솟값으로 초기화합니다.

 

bValid의 값은 false로 초기화를 하되,

iterator가 가리키는 list와 노드가 존재하는 것이라면

사용할 수 있는 iterator로 보고 bValid에 true를 대입합니다.

 

 

iterator는 단순히 특정 노드를 가리키는

역할을 하므로 소멸되면서 할 일은 없겠죠?

그래서 소멸자는 비워 두도록 하겠습니다.

 

 

90번째 줄에서 

friend 키워드를 통해 cList 클래스가

iterator 클래스의 private 멤버에 접근할 수 

있도록 하였습니다.

(inner 클래스인 iterator는 friend 선언을 하지 않아도

cList 클래스의 private 멤버에 그냥 접근할 수 있습니다.)

 

 

---

 

 

 

iterator는 마치 포인터처럼 * 연산이 가능하죠?

 

그래서 * 연산자를 오버로딩하였습니다.

 

iterator가 가리키는 list나 노드가 없거나 

bValid의 값이 false인 경우 하나라도 해당이 되면

오류 창을 띄웁니다.

 

if 문에 걸리지 않았다면 

iterator가 가리키는 노드의 접근하여 

값이 저장되어 있는 멤버 data의 값을

반환합니다.

 

T형 레퍼런스로 반환하는 이유는

* 연산을 하여 반환한 값을 

다른 변수에 대입할 수도 있기 때문이죠.

 

반환한 값을 바로 레퍼런스로 넘겨 주어 

복사 과정을 거칠 필요 없이

바로 값을 참조해서 대입할 수 있게 됩니다.

 

 

---

 

 

begin과 end 함수도 구현을 하겠습니다.

 

list 역할을 할 cList 클래스 템플릿에 

iterator를 반환 타입으로 하는 

begin과 end 함수를 선언합니다.

 

그 위에 class iterator라는 코드를

넣은 이유는 iterator 클래스가 

더 아래에 적혀 있기 때문입니다.

컴파일러는 위쪽에서는

iterator가 뭔지 모릅니다.

 

그래서 41번째 줄에서 iterator라는

클래스가 존재한다고 미리 알려줌으로써

iterator를 반환 타입으로 하는 

begin과 end 함수를 선언할 수 있는 것이죠.

 

 

함수명을 눌러 Ctrl + . 을 입력하면

정의를 할 수 있도록 틀을 만들어 줍니다.

 

 

정의 부분을 보시죠.

 

먼저 begin 함수의 정의를 보시면

list가 가리키는 첫 번째 노드의 

주솟값을 담은 pHead의 값이 nullptr이라면

오류 창을 띄웁니다.

 

begin 함수는 iterator가

첫 번째 노드를 가리킬 수 있도록 하는

함수인데 첫 번째 노드가 존재하지 

않는다면 오류로 인지해야겠죠?

 

if 문에 걸리지 않았다면

begin 함수를 호출한 list 자신과

첫 번째 노드의 주솟값을 인자로 넘겨

iterator 생성자를 통해

임시로 iterator를 만듭니다.

 

이때 임시 객체 iterator이기 때문에

begin 함수가 끝나면 사라지므로

반환 타입을 일반 iterator로 하여

복사가 일어나도록 해야 합니다.

 

 

end 함수는

list 자신과 nullptr을 인자로 넘겨

iterator 생성자를 통해 임시 객체 iterator를

만들어 반환합니다.

 

list의 iterator에서 end라는 개념은 

iterator가 아무 노드도 가리키고 있지 않다면

end iterator라고 볼 수 있겠죠?

 

그래서 end 함수를 호출하면

nullptr을 넘겨 iterator의 생성자를 통해

end iterator를 생성하고 이를 반환하는 겁니다.

 

 

---

 

 

 

이제 구현한 것들이 잘 작동되는지 확인해 볼까요?

 

list를 하나 만들고 100, 200, 300을 넣어

세 개의 노드가 생성되게 하였습니다.

 

이후 iterator를 만들어 100이 들어 있는

첫 번째 노드를 가리키도록 하고

iterator에 * 연산을 하여 222를 대입하겠습니다.

 

list가 가리키는 첫 번째 노드의 값을

확인해 보니 정말 222가 대입되었음을 볼 수 있습니다.

 

 

* 연산을 하여 값을 얻고 

이 값을 다시 다른 변수에 대입할 수 있는지

확인하겠습니다.

 

iterator는 첫 번째 노드(100)를 가리키고 있는 상황입니다.

* 연산을 하여 iterator가 가리키는 값을 얻은 후

변수 i에 대입하였더니 100이 대입되는 것을 확인할 수 있네요.

 

 

 

---

 

 

 

iterator는 반복자입니다.

존재하는 노드를 처음부터 끝까지 순회할 수 있어야 하죠.

 

아래 코드처럼 for 문을 통해서 노드 순회가 가능해야 합니다. 

 

이것이 가능하려면 iterator끼리의 비교 연산과

iterator의 ++ 연산이 가능해야겠죠.

 

 

우선 비교 연산자부터 오버로딩하겠습니다.

 

같은지 다른지 비교하는 연산이기 때문에 

반환 타입은 bool형으로 합니다. 

 

== 연산자부터 보시면

단순히 비교만 진행하며 iterator의 값을 바꿀 일이 없고

복사하지 않고 레퍼런스로 참조하여 값을 비교하는 게

더 빠르겠죠? 그래서 const iterator형 레퍼런스로 인자를 받습니다.

여기서 인자로 받는 iterator는 비교 시, 오른쪽에 있는 iterator죠.

 

== 연산을 호출한 iterator(왼쪽)와 인자로 받은 iterator(오른쪽)가

같은 list의 iterator이며, 같은 노드를 가리키고 있다면

같다는 의미로 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

 

 

!= 연산은 같지 않아야 true이고

같으면 false로 인지합니다.

 

그래서 연산자를 호출한 iterator와 인자로 받은 iterator를

비교하여 같은 경우 true를 반환하게 되는데

앞에 있는 부정 연산자(!)로 인해 false를 최종적으로 반환합니다.

 

두 iterator가 다른 경우 false를 반환하고 

부정 연산자로 인해 최종적으로 true를 반환할 겁니다.

 

 

다음은 ++ 연산자를 오버로딩하겠습니다.

 

먼저 전위 ++ 연산자입니다.

 

iterator가 end인 상태에서 ++ 연산을 하면

안되겠죠. 그래서 iterator가 아무 노드도 가리키고 있지 

않거나,  사용할 수 없는 iterator라서 bValid의 값이 false라면

오류 창을 띄웁니다.

 

그런 경우가 아니면 현재 가리키고 있는 노드로부터

다음 노드의 주솟값을 저장하여 그 노드를 가리키게 합니다.

 

이후 레퍼런스로 iterator 자신을 반환합니다.

 

 

매개 변수 자리에 자료형이 적힌 것은

후위 연산자임을 의미합니다.

 

먼저 연산자를 호출한 iterator를

지역 변수에 저장합니다.

 

그리고 호출한 iterator가 다음 노드를

가리키게 합니다.

 

근데 여기서 다음 노드를 가리키기 전의

iterator를 저장하였던 지역 변수를 반환하여

마치 후위 ++ 연산을 하는 것과 같은 기능을 합니다.

 

이러한 이유로 반환 타입이 레퍼런스가 아닌

일반 iterator인 것입니다. 레퍼런스로 하면 

100번째 줄을 통해 다음 노드를 가리키게 되는 iterator를

참조하여 반환하기 때문에 후위 연산처럼 작동할 수 없죠.

 

 

-- 연산자는 거의 ++ 연산자와 같지만

 

107번째 줄에서 조건이 하나 더 추가되었습니다.

 

만약 iterator가 맨 앞 노드를 가리키는 상태에서

-- 연산을 진행하면 안되기 때문이죠.

 

if 문에 걸리지 않는다면

112번째 줄이 실행됩니다.

-- 연산이기 때문에 현재 iterator가 가리키는

노드로부터 이전에 있는 노드의 주솟값을 저장합니다.

그러면 이전 노드를 가리키게 되겠죠.

 

 

후위 -- 연산자의 경우도 

++ 부분이 --으로 바뀌는 것 말고는

++ 연산과 다른 점은 없습니다.

 

 

모두 구현한 후에

 

27번째 줄처럼 for 문을 작성하고 실행하면

list가 관리하는 모든 노드를 순회하면서

들어 있는 데이터를 하나씩 출력하는 것을

확인할 수 있습니다.

 

 

---

 

 

 

이제 노드를 삽입하는 insert 함수를

구현할 것인데, 먼저 std에 있는

실제 list의 insert 함수가 

어떻게 작동하는지 살펴 봅시다.

 

list를 만들고 10, 20, 30을 넣었습니다.

 

그리고 iterator를 통해 10이 저장된 첫 번째 노드를 가리킵니다.

 

list의 멤버 함수 insert를 통해

iterator가 가리키는 곳에 999를 넣습니다.

 

그랬더니 첫 번째 노드 앞에, 999가 저장된 노드가 새로 생겼네요.

 

insert 함수를 사용하면 현재 iterator가 가리키는 공간 기준,

앞쪽(왼쪽)에 새로운 노드가 삽입되는 것을 알 수 있습니다.

 

위 상태에서 20과 30 사이에  999를 삽입하고 싶다면 

iterator로 30을 가리킨 후에 insert 함수를 호출하면 되는 것이죠.

 

아래 코드를 보시면

 

10을 가리키고 있는 iterator에 ++ 연산을 두 번하여

30을 가리키게 하고 이를 통해 insert 함수를 호출하여

999를 대입하였더니 가리키던 공간 앞쪽에 999가 대입되었습니다.

 

 

이러한 insert를 구현해 봅시다.

 

insert 함수는 iterator와 데이터를 인자로 받습니다.

 

인자로 받은 iterator가 가리키는 노드의 앞쪽에

노드를 새로 만들어 인자로 받은 T형 데이터를 넣는 것이죠.

 

이 과정에서 iterator와 들어온 데이터가 수정될 필요가 없고

복사할 필요도 없기에 const 레퍼런스로 받아 참조하도록 합니다.

 

 

end iterator인 경우

오류로 인지할 것이기 때문에 

end 함수의 반환값과 인자로 받은 iterator가 

같다면 assert 매크로를 호출해 오류 창을 띄웁니다.

 

 

문제가 없다면 새로운 노드를 만들어

동적 할당을 진행합니다. 노드는 tListNode형이었죠?

동적 할당을 진행하면서 생성된 노드를 초기화해 줍니다.

해당 노드는 인자로 받은 data 값을 저장하며 

노드가 생성되는 시점에는 앞과 뒤쪽에 노드가 존재하지 

않으므로 일단 nullptr로 초기화합니다.

 

 

만약 iterator가 첫 번째 노드, 

즉 헤드 노드를 가리키고 있다면

헤드 노드의 주솟값을 저장하는 pHead에

새로 생성된 노드의 주솟값을 저장하고

새로 생성된 노드의 이전 노드를 가리키는

멤버 변수 pPrev에 nullptr을 대입합니다.

 

iterator 기준 앞쪽에 insert가 되기 때문에

iterator가 헤드 노드를 가리키고 있다면

새로 삽입되는 노드가 헤드 노드로 바뀌어야겠죠.

 

또한 헤드 노드로부터 이전 노드는 존재하지 않으므로

새로 생성된 노드의 이전 노드를 가리키는

멤버 변수 pPrev에 nullptr을 대입하는 겁니다.

 

 

근데 헤드 노드가 아니라

어떤 노드와 노드 사이에 insert가 발생한다면

새로 삽입되는 노드와 앞쪽에 있는 노드와 연결하고,

새로 삽입되는 노드와  뒤쪽에 있는 노드와 연결을 해야 합니다.

 

이를 위해 iterator가 가리키는 노드로 갑니다.

해당 노드는 이전 노드의 주솟값을 가지고 있으므로

이전 노드로 이동할 수 있죠. 이전 노드로 갑니다.

이전 노드에서 다음 노드를 가리키는 멤버 pNext에

새로운 노드의 주솟값을 저장합니다.

 

 

다음에는 iterator가 가리키는 노드에서

이전 노드를 가리키는 멤버 pPrev에

새로운 노드의 주솟값을 저장합니다.

 

그리고 새로 생성된 노드에서

다음 노드를 가리키는 멤버 pNext에

iterator가 가리키는 노드의 주솟값을 저장합니다.

 

 

insert 함수를 통해 list가 관리하는 데이터가

하나 증가했으므로 iCount의 값을 하나 올립니다.

 

 

마지막으로 새로 생성한 노드를 인자로 받아

임시 객체 iterator를 생성해 반환합니다.

 

실제 std에 있는 list의 멤버 함수 insert를

 

호출한 후에 이를 다시 iterator에 대입하였더니

새로 생선된 노드의 값인 999가 대입되었습니다.

 

즉 insert 함수는 새로 생성된 노드를 반환함을 의미합니다.

 

 

insert 함수를 통해 노드를 삽입하는 과정을

그림으로 나타내 보겠습니다.

 

만약 두 개의 노드 사이에 

insert 함수를 통해 새로운 노드를 삽입한다면

 

위 그림과 같은 상황이 되겠죠.

 

 

 

 

 

강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB

---