데브웁스

Policy Based Design

• 클래스가 사용하는 정책을 템플릿 인자를 통해서 교체 할 수 있게 만드는 디자인

• 성능 저하 없이 정책을 교체 할 수 있음

• 대부분의 정책은 담은 "단위 전략 클래스"는 지켜야 하는 규칙이 있음

  • 규칙을 표현하는 코딩 방식은 없음(인터페이스 사용시 가상 함수이므로 약간의 오버헤드 발생), C++20 concept 문법

  • 우리가 만든 동기화 정책클래스는 "lock/unlock" 함수가 필요함

  • 템플릿 기반 라이브러리, 특히 STL에서 널리 사용되는 디자인 기법

#include <iostream>
using namespace std;

// 1개의 클래스로 정책 템플릿 인자를 통해서 다르게 구현 할 수 있도록 디자인
template<typename T, typename ThreadModel> class List
{
    ThreadModel tm;
public:
    void push_front(const T& a)
    {
        tm.lock();
        // 구현부 코드
        tm.unlock();
    }
};

// 싱글 쓰레드 기반 환경용
class NoLock
{
public:
    inline void Lock() {};
    inline void Unlock() {}
};

// 멀티 쓰레드 기반 환경용
class MutexLock
{
public:
    inline void Lock() {};
    inline void Unlock() {}
};

// 환경에 따라서 클래스 생성 시 전략을 선택 할 수 있음
// 싱글 쓰레드용 생성
//List<int, NoLock> s;
// 멀티 쓰레드용 생성
List<int, MutexLock> s;

int main()
{
    s.push_front(10);
}

STL allocator

• C++에서 메모리 할당 방법은 다양함

  • new, malloc, calloc, win32 api, linux system call

• STL에서는 각 데이터 컨테이너의 템플릿 인자로 메모리 할당 방식에 대한 전략을 선택할 수 있도록 지원함

#include <iostream>
using namespace std;

// STL의 Vector 생각
// 메모리 할당기
template<typename T> class allocator
{
public:
    T* allocate() {}
    void deallocate() {}
};

template<typename T, typename Ax = allocator<T>> class vector
{
    T* buff;
    Ax ax;
public:
    void resize(int n)
    {
        // 버퍼 재할당이 필요하다면 어떻게 할까요?
        // new, malloc, calloc, win32 api, linux system call
        T* p = ax.allocate(n);
        ax.deallocate(p);
    }
};

int main()
{
    vector<int, MyAlloc<int>> v(10);
    v.resize(20);
}

rebind

#include <iostream>
using namespace std;

template<typename T> class allocator
{
public:
    T* allocate(int sz) { return new T[sz]; }
    void deallocate(T* p) { delete[] p; }

    template<typename U> struct rebind
    {
        typename allocator<U> other;
    };
};

template<typename T, typename Ax = allocator<T> > class list
{
    struct NODE
    {
        T data;
        NODE* next, * prev;
    };
    //Ax ax; // allocator<int>
    //allocator<int>::rebind<NODE>::other ax; // allocator<NODE> ax;
    typename Ax::template rebind<NODE>::other ax; // allocator<NODE> ax;
public:
    void push_front(const T& a)
    {
        ax.allocate(1);
    }
};

int main()
{
    list<int> s;
    s.push_front(10);
}

컨테이너(Container)

• 다양한 알고리즘을 사용하는 자료구조 제공
  • 리스트, 벡터, 트리, 해시

반복자(Iterator)

• 컨테이너의 내부구조에 상관없이 동일한 방식으로 요소에 접근 제공

알고리즘(Algorithm)

• 다양한 알고리즘에 처리를 위한 일반함수 제공
  • 선형검색, 이진검색, 정렬, 순열

정책 변경(Policy Base)

• 알고리즘 및 컨테이너의 정책을 변경
  • 일반 함수, 함수 객체, 람다 표현식 이용

STL 알고리즘 특징

• 멤버 함수가 아닌 일반 함수로 제공
• <algorithm> 헤더 제공
• 대부분 함수 인자와 반환 타입으로 반복자를 사용
• 자료구조에 독립적 동작

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

int main()
{
    std::list<int> s = { 1,2,3,4,5 };
    std::vector<int> v = { 1,2,3,4,5 };

    auto p1 = std::find(s.begin(), s.end(), 3); list 요소중 3 값 탐색
    auto p2 = std::find(v.begin(), v.end(), 3); vector 요소중 3 값 탐색

    std::cout << *p1 << std::endl;
    std::cout << *p2 << std::endl;
}

find 알고리즘

• [first, last) 사이의 선형 검색을 수행
• last는 검색 대상 아님(iterator.end()에 해당하는 마지막 요소 다음 요소)
• 검색 실패시 0이 아닌 마지막을 요소 반환

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> v = { 1,2,3,4,5 };

    // [first, last), 선형 검색, 시작요소는 검색에 포함, 마지막 요소는 검색에 포함되지 않음 의미
    auto p = std::find(v.begin(), v.end(), 3);
    if (p == v.end()) //검색 실패시 v.end() 값 리턴
        std::cout << "검색 실패" << std::endl;

    auto p1 = std::begin(v);
    auto ret = std::find(p1, p1 + 2, 3); // 부분 검색 필요시

    if (ret == p1 + 2)
        std::cout << "실패" << std::endl;

    std::find(ret, std::end(v), 3); // 다음 검색 필요시 두번째 파라미터를 첫째 파라미터로 활용
}

reverse, sort 알고리즘

• 마찬가지로 iterator의 begin, end 값을 파라미터로 지원
• 이외 많은 알고리즘이 제공되며 www.cppreference.com 참고

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> v = { 1,2,3,4,5,6,7,8,9,10 };

    std::reverse(v.begin(), v.end()); // 집합의 요소 역순 정렬

    for (auto& n : v)
    {
        std::cout << n << ",";
    }

    std::cout << std::endl; // 개행

    std::sort(v.begin(), v.end()); // 집합의 요소 정순 정렬

    for (auto& n : v)
    {
        std::cout << n << ",";
    }
}

반복자(iterator)

집합에서 요소 하나하나를 읽어오는 방법

• begin : 집합의 첫 번째 요소의 주소 반환
• end : 집합의 마지막 번째 다음 요소의 주소 반환

#include <list>


int main()
{
    int x[10] = { 1,2,3,4,5,6,7,8,9,10 }; // 배열 선언
    int* px = x; // 배열의 첫번째 요소를 가르키는 포인터 대입
    ++px; // 포인터 증가
    std::cout << *px << std::endl; // 다음 배열의 값 출력

    std::list<int> s = { 1,2,3,4,5,6,7,8,9,10 }; // 리스트 선언
    std::list<int>::iterator p = s.begin(); // 리스트의 첫번째 요소를 가르키는 iterator 대입
    // std::list<int>::iterator p; -> auto로 간소화 : auto p;
    ++p; // 이터레이터 증가
    std::cout << *p << std::endl; // 다음 리스트의 값 출력
}

기능

• 멤버 함수 begin/end
• 일반 함수 begin/end(C++11 이상)
  • 표준 배열까지 동일 코드로 사용 가능한 일반 함수 버전 사용을 권장

#include <iostream>
#include <vector>
#include <list>

int main()
{
    std::list<int> s1 = { 1,2,3,4,5,6,7,8,9,10 }; // 리스트 선언
    auto s1b = s1.begin(); // 첫번째 요소
    auto s1e = s1.end(); // 마지막 다음 요소.

    while (s1b != s1e) // 모든 요소 읽기
    {
        int n = *s1b;
        ++s1b;
    }

    std::vector<int> s2 = { 1,2,3,4,5,6,7,8,9,10 }; // vector 선언
    auto s2b = s1.begin(); // 첫번째 요소
    auto s2e = s1.end(); // 마지막 다음요소.

    while (s2b != s2e) // 모든 요소 읽기
    {
        int n = *s2b;
        ++s2b;
    }

    int s3[] = { 1,2,3,4,5,6,7,8,9,10 }; // 배열 선언
    auto s3b = std::begin(s3); // 첫번째 요소(일반 함수) C++11, 멤버보단 일반 함수 권장
    auto s3e = std::end(s3); // 마지막 다음요소(일반 함수) C++11
}

전체 요소 접근 방법

1. [] 연산자 사용 : vector, deque 사용 가능, list 사용 불가
2. range fo 사용
3. while 사용

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = { 1,2,3,4,5,6,7,8,9,10 };

    // 1. [] 연산자, vector는 되지만 list는 안됨
    for (int i = 0; i < v.size(); i++)
    {
        std::cout << v[i] << std::endl;
    }

    // 2. range for, 모든 집합 타입 가능
    for (auto& n : v)
        std::cout << n << std::endl;

    // 3. 반복자 사용, 모든 집합 타입 가능
    auto p1 = std::begin(v);
    while (p1 != std::end(v))
    {
        std::cout << *p1 << std::endl;
        ++p1;
    }

}

반복자의 장점

• 컨테이너의 내부 자료구조에 상관없이 동일한 방법으로 모든 요소를 접근 할 수 있음
• GoF's 디자인 패턴중 "iterator" 패턴 활용

#include <iostream>
#include <vector>
#include <list>

int main()
{
    std::list<int> s = { 1,2,3,4,5 }; // 비순차 메모리 주소 알고리즘
    std::vector<int> v = { 1,2,3,4,5 }; // 순차 메모리 주소 알고리즘

    auto p1 = std::begin(s); // 자료구조 무관 동일 접근
    auto p2 = std::begin(v); // 자료구조 무관 동일 접근
    
    ++p1;
    ++p2;

    int n1 = *p1;
    int n2 = *p2;
}