지나간 삶

vector, deque, list 는 다음과 같은 생성자를 갖는다.
 

vector<int> v1;
vector<int> v2(5);
vector<int> v3( 5, 5 );                 // 5개를5로초기화
vecotr<int> v4( v3.begin(), v3.end() ); // v3의끝과처음으로초기화
vector<int> v5( v4 );                   // v4로초기화

** 사용자 정의 type을 Sequence Container에 넣으려면

1. 기본 생성자가 반드시 정의되어 있어야 한다.
2. 복사 생성자도 명시적으로든 묵시적으로든 반드시 존재해야 한다.
3. 일부 generic 알고리즘에서 원소들간의 상등관계나 대소 관계를 필요로 하기 때문에
   == 연산자와 < 연산자를 정의해 두는 것이 좋다.

// Allocator의개념...

// 메모리 할당만 책임을 지는 클래스를 설계한다.

template<typename T> class allocator

{

public:

        T* allocate( size_t sz )

        {

        }

        void deallocate( void* p )

        {

        }

};

 

// 단위전략기반의 설계: 한가지한가지의 정책을 template 인자로 전달할수 있게하는 기법.!!

template<typename T, typename Alloc = allocator<T> > class vector

{

        T* buf;

        Alloc alloc;           // 메모리할당기객체.

public:

        void push_front( T a )

        {

               // 메모리할당이 필요하게 되었다. !!

               // 어떤 방법으로 할당을 하는게 최고일까?
               // new ? malloc ? object pooling

               int* p = (int*)alloc.allocate();

        }

};

 

// 메모리 할당전략을 바꾸고 싶을때 내가 만든 클래스로 전달하게 해준다.!!!

// 기본할당자 allocator 를 가로챌수 있게 된다.

template<typename T> class myallocator

{

public:

        T* allocate( size_t sz )

        {

        }

        void deallocate( void* p )

        {

        }

};

 

void main()

{

        vector<int, myallocator<int> > v;

}

// reverse_iterator 덕에 알고리즘의 능력이 2배가 된다.

 

void main()

{

        string s1 = "hello";

        string s2 = "abcde";

 

        copy( s1.begin(), s1.end(), s2.rbegin() );

 

        cout << s2 << endl;    //'olleh'

 

        vector<int> v(5);

 

        v[0] = 1;

        v[1] = 2;

        v[2] = 3;

        v[3] = 4;

        v[4] = 5;

 

        vector<int>::reverse_iterator p = v.rbegin();  // 주의rbegin

 

        cout << *p << endl;

        ++p;

        cout << *p << endl;

}

// 어떤 container가 가진 type을 알고 싶을 때가 있다.

// 이 문제를 해결하기 위한 STL은 아래의 기법을 사용하고 있다.

template<typename T> class vector

{

public:

        typedef T value_type;

        typedef T* pointer;

        typedef T& reference;

        typedef const T* const_pointer;

};

 

template<typename T> void foo( T a )

{

        // typeof( a[0] ) n = a[0]; // 다른 언어에서 지원하는 언어 C#

        // a에서 첫번째 요소를 꺼내고 싶다.

        typename T::value_type n = a.front();

}

void main()

{

        vector<double> v(5);

        v[0] = 3.4;

 

        foo( v );

}

 

vector	장점	가변 길이 Sequence에 대한 임의 접근이 가능하며, 시퀸스 끝부분에서 신속한 삽입, 삭제가 가능하다. 검색 속도가 가장 빠르다.
	단점	시퀀스의 맨 끝이 아닌 임의의 다른 위치에서의 삽입삭제는 느리다.(선형시간)
deque	장점	시퀀스 양쪽 끝의 삽입, 삭제가 벡터보다 빠르다.
	단점	시퀀스의 접근시간은 vector보다 느리고, 중간에서의 삽입삭제는 list보다 느리다.
list	장점	시퀀스 중간에서의 삽입, 삭제가 가장 빠르다.
	단점	시퀀스 접근 시간이 가장 느리고, 임의 접근이 불가능하다.

검색 속도 : vector > deque > list
삽입 삭제 : list > deque > vector

- 순서 없이 요소를 저장할 때 사용한다. vector, list, deque의 3가지 종류가 있다.

시퀀스 컨테이너에 속하는 3가지 컨테이너들간에 기능에 차이는 거의 없다. 주로 서능에 차이가 난다.
검색은 vector가 가장 빠르지만 삽입, 삭제는 list가 가장 빠르다.

 세가지 컨테이너 중에서 모든 연산에 대해 수행 성능이 최고인 컨테이너는 없다. 그래서 자신이 만드는 프로그램
에 가장 적합한 컨테이너를 선택하는 것이 중요하다.

또한, 이들 컨테이너들은 거의 동일한 인터페이스로 만들어져 있기 때문에 프로그램을 수정하지 않고도 컨테이너를 변경해 가면서 가장 좋은 성능을 내는 컨테이너를 찾아 낼 수 있다.
인터페이스에 차이가 있다면, 그것은 해당하는 컨테이너를 사용하는 것을 다시 한번 고려해 보라고 의도적으로 그렇게 설계한 것이다.( 예로, vector에는 push_front, pop_front가 없다. )

실제로는 캐시 때문에 vector가 제일 빠르다 . 왜냐하면 list는 연속된 메모리가 아니기 때문에 캐시에 올라올때 모든 메모리가 올라오지 못한다. 하지만 vector는 연속된 메모리로써 메모리에 위치하게 된다. 그러므로 왠만하면 vector를 사용하여 메모리를 잡자.

#include <iostream>

#include <algorithm>

#include <vector>

#include <functional>

//#include <boost\lambda\lambda.hpp>

using namespace std;

 

void foo( int a )

{

        cout << a << " ";

}

 

void main()

{

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

 

        //for_each( x, x+10, foo );

        //for_each( x, x+10, cout << _1 );  // 익명의함수, 람다개념.

 

        char* s[] = { "robert", "kim", "lee", "park" };

 

        // s 배열에서park을찾고싶다.

 

        // C의 함수를 STL 단항함수 객체에 넣고 싶을 때는

        // 단항으로 바꾼다. 함수객체로 바꾼다. 0을 리턴하므로 1로 바꿔주도록 not1을 한다.

        char** p = find_if( s, s+4,
                   not1( bind2nd( ptr_fun(strcmp), "park" ) ) );

        cout << *p << endl;

}

 

// 함수어답터

// 기존의 만들어 놓은 함수를 함수객체로 변경하여 STL로 사용하고 싶을때 필요하다.

int Mod( int a, int b )

{

        return a % b;

}

void main()

{

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

 

        int* p = remove_if( x, x+10, bind2nd( ptr_fun(Mod), 2 ) );

 

        copy( x, p, ostream_iterator<int>(cout, " ") );

}

 

// 부정자: 함수객체의 결과를 부정하는 함수객체를 생성한다.

void main()

{

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

 

        //홀수를 제거하라.

 int* p = remove_if( x, x+10, bind2nd( modulus<int>(), 2 ) );

        //not1으로 감싸주면 짝수를 제거하라.

        int* p = remove_if( x, x+10, not1(bind2nd( modulus<int>(), 2 ) ) );

 

        copy( x, p, ostream_iterator<int>(cout, " ") );

}

// 바인더를 구현해보기.

template<class Arg1, class Arg2, class Result> struct xbinary_function
{
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
};

class AbsolutePlus : public xbinary_function< int, int, int >
{
public:
    int operator ()(int a, int b) const
    {
        return abs(a) + abs(b);
    }
};

template<typename T> class my_binder1nd
{
    T op;
    typename T::first_argument_type left;
public:
    my_binder1nd( T _right, typename T::first_argument_type _left )
        : op(_right), left(_left) {}
    typename T::result_type operator()
        ( typename T::first_argument_type right ) const
    {
        return op( left, right );
    }
};

template<typename T> class my_binder2nd
{
    T op;
    typename T::second_argument_type right;
public:
    my_binder2nd( T _left, typename T::second_argument_type _right)
        : op(_left), right(_right) {}
    typename T::result_type operator()
        ( typename T::first_argument_type left ) const
    {
        return op( left, right );
    }
};

void main()
{
    // 1번째파라미터를상수값으로고정
    my_binder1nd<AbsolutePlus> f1( AbsolutePlus(), 2 );  
    // 2번째파라미터를상수값으로고정
    my_binder2nd<AbsolutePlus> f2( AbsolutePlus(), 5 );

    cout << f1(-3) << endl;
    cout << f2(-5) << endl;
}







//////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////

















// 바인더



// 단항함수: 인자가 1개인 함수.
// 이항함수: 인자가 2개인 함수

int foo( int a )
{
    return a % 3 == 0;
}

void main()
{
    // STL에는 modulus가 있다.
    modulus<int> m;
    int k = m(10, 3);
    cout << k << endl;

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


    // 함수버전으로 수행
    int* p = remove_if( x, x+10, bind2nd( m, 3 ) );

    // 이항함수 객체를 단항함수 객체로 변경한다. 클래스버전으로 수행.
    binder2nd<modulus<int> > f( m, 3 );   // f는 m%3을 가지는 단항함수이다.
    int k2 = f(10);
    cout << k2 << endl;
    int* p1 = remove_if( x, x + 10, f );  // 3의 배수가 아닌 것을 제거해라.

    //int* p = remove_if( x, x + 10, foo );
    copy( x, p1, ostream_iterator<int>( cout, " " ) );
}

// void foo( int a )
// {
//      cout << a << endl;
// }

// 함수보다는 함수객체가 훨씬 좋다.

template<typename T> struct Show

{

        ostream& os;

 

        Show( ostream& s = cout ) : os( s ) {}

 

        void operator()( T a )

        {

                os << a << endl;

        }

};

// Point foo( Point )
// {
//      Point p;
//      return p;
//      return Point();        // RVO
// }

void main()

{

//      Point p;

//      foo(p);                // 객체를 만들어서 복사해서 보내기.
//      foo( Point() );        // 만들면서 보내는게 좋다!!

 

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

 

//      ofstream f( "a.txt" );

//      Show<int> s(f);

//      for_each( x, x+10, s );

 

        for_each( x, x+10, Show<int>() );

        //for_each( x, x+10, foo );

}

// transform 에 대해서

int foo( int a, int b )

{

        return a + b;

}

// functional 헤더파일에서 지원한다.

template<typename T> struct plus

{

        T operator()( T a, T b )

        {

               return a+b;

        }

};

 

#include <functional>

 

void main()

{

        int x[5] = { 1, 2, 3, 4, 5 };

        int y[5] = { 1, 2, 3, 4, 5 };

        int z[5];

 

        // x~x+5 에 있는 것과 y에 있는것을 더하여 z에 넣어준다.
        transform( x, x+5, y, z, plus<int>() );

        copy( z, z+5, ostream_iterator<int>(cout, " ") );

}

// 조건자(predicator, 술어) : bool을 리턴하는 함수 또는 함수객체

// 선형검색의 정의: 주어진 구간에서 주어진 조건을 만족하는 요소를 찾는것.

 

bool foo( int a )

{

        return a > 5;

}

 

bool goo( int a )

{

        return a % 3 == 0;

}

 

void main()

{

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

 

        int* p = remove_if( x, x+10, foo );

        copy( x, p, ostream_iterator<int>( cout, " " ) );

        cout << endl;

 

        int* p1 = find( x, x+10, 4 );

        int* p2 = find_if( x, x+10, goo );

        cout << *p2 << endl;

}