#include <iostream>
using namespace std;
// 일반적프로그램의개념
// 선형검색: 주어진구간에서주어진조건을만족하는값을찾는다.
// 구간의조건: NULL 로끝나는문자열
// 구간의이동: ++
// 실패의경우: 0을리턴
// 단점: 반드시NULL을끝나는문자열이어야한다. - 너무특수한상황이다.
/*
char* xstrchr( char* s, int c )
{
while( *s != 0 && *s != c )
++s;
return *s == c ? s : (char*)0;
}
*/
// 보다일반화한버전.
// 주어진구간의조건: [begin , end) - 반개행구간. 한쪽만열려있다는의미>> [ ~ )
// 이때end를past the end 라고한다.
// 구간의이동: ++
// 실패의처리: past the end
// 장점: 부분문자열검색이가능하다-> 보다일반화되었다.
// 단점: 문자열(char)만검색가능하다. -> template으로일반화하자.
/*
char* xstrchr( char* begin, char* end, int c )
{
while( begin != end && *begin != c )
++begin;
return begin;
}
void main()
{
char s[10] = "ABCDEFG";
//char* c = xstrchr( s, 'C' );
char *c = xstrchr( s, s+4, 'C' );
if ( c == s + 4 )
{
cout << "실패" << endl;
}
else
cout << *c << endl;
}
*/
// 버전3. template의도입
// 모든type의배열로부터선형검색을수행한다.!!
/*
template<typename T1, typename T2> T1 find( T1 first, T1 last, T2 value )
{
while( first != last && *first != value )
++first;
return first;
}
void main()
{
int x[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int* p = find( x, x+10, 3 );
if( p == x+10 )
{
cout << "값을찾을수없습니다." << endl;
}
else
cout << *p << endl;
}
*/
// 이제Single Linked List를고려해보자.
template<typename T> class slist
{
struct Node
{
T data;
Node* next;
Node( T d, Node* n ) : data(d), next(n) {}
};
Node* head;
public:
slist() : head(0) {}
void push_front( T a ) { head = new Node( a, head ); }
// list의각요소를접근하기위해스마트포인터를넣는다.
// 내포로만들거나외부에(그리고내부에typedef로선언) 만들수있다.
class iterator
{
Node* current;
public:
iterator( Node* init = 0 ) : current( init ) {}
iterator& operator++()
{
current = current->next;
return *this;
}
T& operator* ()
{
return current->data;
}
bool operator !=( const iterator& i )
{
return (current != i.current);
}
};
//-------------------------------------------------------
// 이제slist의처음과past the end iterator를리턴하는함수를제공한다.
iterator begin() { return iterator(head); }
iterator end() { return iterator( 0 ); }
};
// 모든type의모든자료구조로부터선형검색을수행한다.!!
template<typename T1, typename T2> T1 find( T1 first, T1 last, T2 value )
{
while( first != last && *first != value )
++first;
return first;
}
// 모든type의모든자료구조로부터선형검색을수행한다.!!
// 상수가아닌조건을만족하는것을찾는다.주어진조건을찾는다!!!
template<typename T1, typename T2> T1 find_if( T1 first, T1 last, T2 pred )
{
while( first != last )
{
if ( pred(*first) )
break;
++first;
}
return first;
}
bool foo( int a )
{
return a % 3 == 0;
}
void main()
{
int x[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int* p2 = find_if( x, x+10, foo );
cout << *p2 << endl;
//////////////////////////////////////////////////
slist<int> s;
s.push_front(10);
s.push_front(20);
s.push_front(30);
s.push_front(40);
slist<int>::iterator p = find( s.begin(), s.end(), 20 );
cout << *p << endl;
++p;
cout << *p << endl;
/////////////////////////////////////////////////
p = find_if( s.begin(), s.end(), foo );
cout << *p << endl;
}
