[C++][구현] strchr, list, iterator

STL의 구조도 알아볼겸, string 기능의 search 시스템  strchr을 구현해보고

 

직접 만든 list란 컨테이너를 내가 만든 strchr에도 쓸 수 있게끔 만들어주려고합니다

 

list와 비슷하게 구현해보는게 목표입니다.

---

[기본] strchr 함수설명

char s[] = "abcdefg";
char *p;

p = strchr(s, 'c');
cout << *p << endl;

const char* strchr(const char* str, int c);
char* strchr (char* str, int c);

strchr(문자열 포인트, 찾고싶은 문자)

 

만약에 문자가 있으면, 그 문자열의 주소를 리턴해줍니다.

없다면 NULL을 리턴해줍니다.

 

 

이후 저만의 strchr를 xstrchr라 지칭하고, 단계별로 STL로 발전시켜보겠습니다.

 

xstrchr(1단계)

char* xstrchr(char* s, char c) {
	while (*s != 0 && *s != c) ++s;
	return *s == 0 ? 0 : s;
}

함수로써, 만든 xstrchr입니다. c라는 문자를 찾을때까지 s의 주소값을 계속 증가시켜주죠.

이제 좀 더 Generaliztion 하게 검색을 해보려고합니다.

 

 

xstrchar(2단계)

char* xstrchr(char* first, char* last , char c) {
	while (first != last && *first != c) ++first;
	return *first == 0 ? 0 : first;
}

이제는 범위를 설정하여 어디까지 검색 할 수 있는지 정할 수 있게 해줬습니다.

 

여기서 이제 문자열만 사용할 수 있는 검색엔진이 아닌 다른 타입도 이용할 수 있게 변행해보죠

 

xstrchar(3단계)

template <typename T>
T* xstrchr(T* first, T* last , T c) {
	while (first != last && *first != c) ++first;
	return *first == 0 ? 0 : first;
}

template로 typename을 변형시킬 수 있게 하여 좀 더, 여러 타입에 쓸 수 있는 검색기능을 만들었습니다.

 

하지만 여기서는 똑같은 타입끼리만 사용할 수 있죠, 저는 double이라는 배열에서 int를 찾아보고 싶습니다.

 

xstrchar(4단계)

template <typename T1, typename T2>
T1 xstrchr(T1 first, T1 last , T2 c) {
	while (first != last && *first != c) ++first;
	return first == 0 ? 0 : first;
}

이제는 검색할배열(T1) , 찾고싶은것(T2)으로 2가지 타입으로 나눠서, 다른 타입도 찾아 볼 수 있게 만들었습니다.

여기서 문자열에 국한된게 아니기에 포인터를 빼도 무방합니다.

왜냐면 어차피 T1, T2 도 자연스럽게 포인터를 지원해주기 때문입니다.

 

하지만 여기서도, 만약에 NULL을 리턴해줘야한다면? 에러가납니다.

int main()
{
	char s[] = "abcde";
	char* p = xstrchr(s, s + 5, 'h');
	cout << *p << endl;
	
}

NULL을 리턴해줘야하지만 T1은 char에 대한 것으로 리턴값을 NULL로 받지 못하게 됩니다. 

이걸 보완하고자 하는게 

 

xstrchar(5단계)

template <typename T1, typename T2>
T1 xstrchr(T1 first, T1 last , T2 c) {
	while (first != last && *first != c) ++first;
	return first;
}


int main()
{
	char s[] = "abcde";
	char* p = xstrchr(s, s + 5, 'a');
	if (p == s + 5) cout << "Not Found" << endl;
	else  cout << *p << endl;
	
}

사용할 때, 포인터가 마지막까지 순회했는지를 묻고

못찾으면 Not Found, 찾았으면 그 값을 출력해줍니다.

---

나만의 list를 가져와 보겠습니다.

 

slist(1단계)

// Node
template <typename T> struct Node {
	T data;
	Node* next;
	Node(T a, Node* n) : data(a), next(n) {	}
};

// List
template<typename T> class slist {
	Node<T>* head;
public:
	slist() :head(0) {}
	void push_front(const T& a) { head = new Node<T>(a,head)}
};

간단하게 push_front 기능만 있는 리스트입니다.

 

이를 만든 xstrchr를 이용해서 해보려고해도 

int main()
{
	slist<int> s;
	s.push_front(10);
	s.push_front(20);
	s.push_front(30);

	slist<int>* p = xstrchr(s, s + 4, 30);
	
}

당연히 클래스의 주소를 찾으려는게 아니여서, 못찾습니다.

 

이를 어떻게 호환할 수 있게 만들까요?

 

slist(2단계)

// List
template<typename T> class slist {
	Node<T>* head;
	Node<T>* current;
public:
	slist() :head(0) {}
	void push_front(const T& a) { head = new Node<T>(a,head)}

	// * 값 찾기
	T& operator*() { return current->data; }

	slist& next() {
		current = current->next;
		return *this;
	}
    
	bool end() {
		return current == 0;
	}

	slist<T>& begin() {
		current = head;
		return *this;
	}

};

노드들을 순회해야하기에, 노드들을 순회할 current 변수를 가지고,

 

operator 오버로딩을 통해,  data의 값을 가져오고,

 

next()는 current 노드를 다음 노드로 바꿔줍니다.

 

end()는 current 노드가 0일때,

 

begin()은 current 노드의 head노드를 연결시켜줍니다.

이렇게 한다면

 

slist<int> s;
s.push_front(10);
s.push_front(20);
s.push_front(30);

for(s.begin(); !s.end(); s.next()){
	cout << *s << endl;
}

for문을 써서 이렇게나마, 순회를 하면서 검색을 할 수 있을 것입니다.

 

저희는 xstrchr을 이용 할 수 있도록 만들어야하기 때문에

 

리스트의 끝과 처음을 쉽게 알기 위해서 proxy라는 기법을 사용할 것입니다.

 

 

slist(3단계)

 

template <typename T> class slist_proxy {
	Node<T>* current;
public:
	slist_proxy(Node<T>* p = 0) : current(p) }
    
    bool operator!=(const slist_proxy& p) {return current != p.current;}
};

// List
template<typename T> class slist {
	Node<T>* head;
	Node<T>* current;
public:
	slist() :head(0) {}
	void push_front(const T& a) { head = new Node<T>(a,head)}

	// * 값 찾기
	T& operator*() { return current->data; }

	slist& next() {
		current = current->next;
		return *this;
	}

	slist_proxy<T> begin() { return slist_proxy<T>(head); }
	slist_proxy<T> end() { return slist_proxy<T>(0); }

};

begin()과, end()를 따로 알기위하여, slist의 proxy를 만들어줍니다.

 

int main()
{
	slist<int> s;
	s.push_front(10); s.push_front(20);
	s.push_front(30);

	slist_proxy<int> p;

	for(p = s.begin(); p != s.end(); s.next()){
    	cout << *s << endl;
    }
}

이렇게 proxy를 두어서, 대신 순회 할 수 있게 만들어줍니다.

 

이후에 순환할 기능들은 slist에서 slist_proxy로 다 기능을 넘겨줍시다.

 

slist(4단계)

template <typename T> class slist_proxy {
	Node<T>* current;
public:
	slist_proxy(Node<T>* p = 0) : current(p){}

	// * 값 찾기
	T& operator*() { return current->data;}

	slist_proxy& operator++(int) {
		current = current->next;
		return *this;
	}
};

// List
template<typename T> class slist {
	Node<T>* head;
public:
	slist() :head(0) {}
	void push_front(const T& a) { head = new Node<T>(a,head)}

	slist_proxy<T> begin() { return slist_proxy<T>(head); }
	slist_proxy<T> end() { return slist_proxy<T>(0); }

};

이제는 proxy에 next기능대신 operator ++ 을 두어,

for(p = s.begin(); p != s.end(); p++){
    cout << *s << endl;

p++ 로 순회 할 수 있게 됩니다.

 

이제 proxy라는 이름을 버리고 iterator이라는 이름으로 명명해 주면서~,

operator != 오버로드도 추가해줍시다.

 

slist(5단계)

template <typename T> struct Node {
	T data;
	Node* next;
	Node(T a, Node* n) : data(a), next(n) {	}
};

template <typename T> class slist_iterator {
	Node<T>* current;
public:
	slist_iterator(Node<T>* p = 0) : current(p){}

	template<typename U> bool operator!=(U data) { return current->data != data; }

	bool operator!=(const slist_iterator& p) { return current != p.current; }
	// * 값 찾기
	T& operator*() { return current->data;}

	slist_iterator& operator++() {
		current = current->next;
		return *this;
	}	
	slist_iterator& operator++(int) {
		current = current->next;
		return *this;
	}
};

// List
template<typename T> class slist {
	Node<T>* head;
public:
	slist() :head(0) {}
	void push_front(const T& a) { head = new Node<T>(a, head); }

	slist_iterator<T> begin() { return slist_iterator<T>(head); }
	slist_iterator<T> end() { return slist_iterator<T>(0); }

};

 

이런식으로 만들어 이제 xstrchr을 사용할 수 있게 됩니다.

int main()
{
	slist<int> s;
	s.push_front(10);
	s.push_front(20);
	s.push_front(30);

	slist_iterator<int> p = xstrchr(s.begin(), s.end(), 30);
	cout << *p << endl;

	
}

 

 

마지막 우리는 반복자 slist_iterator을 iterator이라는 동일한 이름으로 나타내면 됩니다.

// List
template<typename T> class slist {
	Node<T>* head;
public:
	slist() :head(0) {}
	void push_front(const T& a) { head = new Node<T>(a, head); }

	typedef slist_iterator<T> iterator;

	iterator<T> begin() { return iterator<T>(head); }
	iterator<T> end() { return iterator<T>(0); }

};

 

 

굉장히 복잡하게 적혀졌지만 포스팅하고 싶은 내용은

 

STL 식으로 만들기 위해서는, generic 한 특성이 있어야 하니

 

각 컨테이너를 순환할 수 있는 iterator이란 것을 만들어 줘서 내가 만든 xstrchr이란 기능에도 접합 할 수 있게

proxy 기법, iterator 기법을 사용 하였다 라는것을 알 수 있는 과정이였습니다.