이번 시간에는 다음 내용을 살펴보겠습니다.

  1. 제너릭 알고리즘의 개념, 컨테이너와 알고리즘의 연결(iterator)
  2. STL의 구조와 유사한 방식으로 간략한 라이브러리 설계
  3. 예제
  4. C++17 이후의 STL 변화

​

STL Find algorithm

1. C언어의 strchr() 함수

  • 문자열에서 문자를 검색시 널 문자('\0')를 만날 때 까지 검색(구간 종료 조건도 검색 대상에 포함)
  • 검색 실패시 NULL 포인터(0) 리턴
  • 개선점 -> 부분 문자열 검사 불가, 종료 조건을 정의 할 수 없음, char 타입만 검색 가능
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
	char s[] = "abcdefg";

	char* p = strchr(s, 'c');

	if (p == 0)
		cout << "fail" << endl;
	else
		cout << "success : " << *p << endl;
}

2. strchr()의 문제점을 개선한 함수 efind 함수

  • 검색 대상 -> 모든 타입의 배열
  • 검색 구간 first, last(last는 검색에 포함 되지 않음 -> half open range)
  • 구간의 표현 -> 포인터 뿐 아니라 객체도 가능(단 ++, *, !=, == 연산이 가능해야 함)
  • 구간의 이동 -> 전위 연산 ++
  • 검색 실패시 -> last 위치 리턴
#include <iostream>
#include <algorithm>
using namespace std;

template<typename T1, typename T2>
T1 efind(T1 first, T1 last, T2 value)
{
	while (first != last && *first != value)
		++first;

	return first;
}

int main()
{
	double x[10] = { 1,2,3,4,5,6,7,8,9,10 };

	double* p = find(x, x + 10, 5);

	if (p == x + 10)
		cout << "fail" << endl;
	else
		cout << "success : " << *p << endl;
}

STL Container & iterator

Container

  • 데이터 저장소 Node를 갖는 연결리스트
  • 위에서 만든 efind는 slist의 요소 검색 불가
#include <iostream>
using namespace std;


template<typename T> struct Node
{
	T     data;
	Node* next;

	Node(const T& a, Node* n) : data(a), next(n) {}
};

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

int main()
{
	slist<int> s;

	s.push_front(10);
	s.push_front(20);
	s.push_front(30);
	s.push_front(40);
	s.push_front(50);
}

Container와 알고리즘의 결합

  • efind 함수 개선
    • node 탐색을 위해 pointer를 전달 받는 것이 아닌, node의 주소를 순회 할 수 있는 객체를 정의 -> iterator
    • iterator 덕분에 efind는 배열 뿐 아니라, 모든 선형 자료구조에 대해 선형 탐색 수행 가능
ntributor
107 lines (76 sloc)  1.61 KB
#include <iostream>
using namespace std;

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

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

	bool operator ==(const slist_iterator& it)
	{
		return current == it.current;
	}
	bool operator !=(const slist_iterator& it)
	{
		return current != it.current;
	}
};

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

	using iterator = slist_iterator<T>;

	iterator begin() { return iterator(head);}
	iterator end()   { return iterator(0);	}
};

int main()
{
	slist<int> s;

	s.push_front(10);
	s.push_front(20);
	s.push_front(30);
	s.push_front(40);
	s.push_front(50);

	slist<int>::iterator p = s.begin();

	slist<int>::iterator p2 =
				efind(s.begin(), s.end(), 120);

	if (p2 == s.end())
		cout << "fail" << endl;
	else
		cout << *p2 << endl; // 20;
}

STL 구조 핵심정리

  1. 템플릿을 통한 불필요한 함수 구현을 줄임
  2. 자료구조와 알고리즘이 분리된 라이브러리
    • 알고리즘 함수는 자신이 어떤 자료구조에 대해 연산을 수행하는지 모름

STL 구조와 특징

Member Type

  • 모든 stl 컨테이너는 value_type을(자료형의 타입) 멤버로 갖도록 설계됨
  • size_type, iterator, pointer .. 등등 여러 메타정보를 멤버로 갖고 있음
  • 컨테이너의 타입을 출력하는 함수 예제
template<typename T>
void print(T& c)
{
	typename T::value_type n = c.front(); // double

	cout << n << endl;
}

int main()
{
	list<double> v = { 1,2,3 };
	print(v);
}

C++17과 STL

  • C++17 이후 컨테이너 사용시 템플릿 인자 생략 가능
#include <iostream>
#include <list>
using namespace std;

template<typename T> class List
{
public:
	List(int sz, T initValue) {}
};

int main()
{
	List<int> s1(10, 0);
	List      s2(10, 0); // C++17 ok.

	list<int> s3 = { 1,2,3 };
	list      s4 = { 1,2,3 }; // C++17 style
}

Concept (C++20 이후)

  • 특정 함수(클래스)를 사용하기 위해 타입이 가져야하는 조건을 코드에 명시 가능
  • 함수 전달 인자에 제약 조건을 명시 할 수 있음
  • 템플릿 작성시 모든 타입이 아닌, 조건을 만족하는 타입에 대해서 동작하도록 설계 가능