데브웁스

컨테이너(Container)

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

반복자(Iterator)

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

알고리즘(Algorithm)

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

정책 변경(Policy Base)

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

알고리즘이 사용하는 정책 변경 방법

• 일반 함수 사용
• 함수 객체 사용 - <functional>
• 람다 표현식 사용(C++11)

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // STL 함수 객체

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

    // 1. 일반 함수 사용.
    //std::sort(v.begin(), v.end(), cmp);

    // 2. 함수 객체
    std::greater<int> g; //>
    std::sort(v.begin(), v.end(), g);

    // 3. 람다 함수 사용, Lambda Expression C++11
    std::sort(v.begin(), v.end(),
        [](int a, int b) { return a > b; }); // [] lambda introducer

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

컨테이너가 사용하는 정책 변경 방법

#include <iostream>
#include <set>
#include <functional> // STL 함수 객체

int main()
{
    std::set<int, std::greater<int>> s; // tree, 컨테이너의 기본값 less<int> 대신 std::greater 사용

    s.insert(10);
    s.insert(30);
    s.insert(20);

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

}

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;
}

list, vector, tree 등 여러개의 데이터를 보관하는 자료구조

• 특징
  • 배열은 크기 변경이 불가능 하지만 STL vector는 크기 변경 가능
• 통일된 멤버 함수
  • 대부분 코드 수정 없이 컨테이너 교체 가능
  • 요소 삽입 : push_front, push_back, insert
  • 요소 제거 : pop_front, pop_back, erase
  • 요소 접근 : front, back
  • vector는 앞에 삽입할 수 없다.(push_fron 함수 x)
• 주의사항
  • pop_back : 제거만 하고 리턴 하지 않음
  • back : 리턴만 하고 제거하지 않음

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

int main()
{
    int x[10];
    std::vector<int> v(10);
    v.resize(5);

    std::list<int> s1 = { 1,2,3 };
    std::vector<int> s2 = { 1, 2, 3 };

    s1.push_front(10);
    s1.push_back(10);
    s1.push_back(10);
    s1.pop_back();

    int n2 = s1.back();
    int n3 = s1.back();
    s1.pop_back();
    int n4 = s1.back();
}

• array
  
  • <array>
  • C의 배열과 유사한 자료구조
• vector
  • <vector>
  • 크기를 변경할 수 있는 동적 배열
• list
  • <list>
  • 더블 리스트
• forward_list
  • <forward_list>
  • 싱글 리스트
• deque
  • <deque>
  • list와 vectort의 혼합형 자료구조
• set
  • <set>
  • tree
• map
  • <map>
  • tree를 사용해서 key와 data 저장
• unordered_set
  • <unordered_set>
  • hash
• unordered_map
  • <unordered_map>
  • hash를 사용해서 key와 data 저장
• stack
  • <stack>
  • 스택
• queue
  • <queue>
  • 큐
• priority_queue
  • <queue>
  • 우선순위 큐

C++ 언어가 제공하는 템플릿 기반의 표준 라이브러리

• C++ 탄생(197x ~1980)
  • 연구실용 언어로 사용
• C++98/03(1998 ~ 2003)
  • 자료구조를 나타내는 컨테이너, 알고리즘 함수, 반복자, 함수 객체등 포함
• C++11/14(2011 ~ 2014)
  • Hash, 스마트 포인터, 멀티스레드, atomic, regex, chrono, bind, function 등
• C++17(2017)
  • File System, Optional, Any, string_view, array_view
• C++20(2020)
  • 병렬 프로그래밍, Concept 개념
  • www.isocpp.org 참고

생성자와 연산자 재정의를 이용한 String 클래스 만들기

class String
{
    char* buff; // 문자열 버퍼
    int size; // 문자열 사이즈
public:
    String(const char* s) // 생성자
    {
        size = strlen(s);
        buff = new char[size + 1];
        strcpy(buff, s);
    }
    ~String() { delete[] buff;}

    String(const String& s) : size(s.size) // 복사 생성자(여기선 깊은 복사)
    {
        buff = new char[size + 1];
        strcpy(buff, s.buff);
    }

    String& operator=(const String& s) // 대입 연산자 재정의
    {
        // 자신과의 대입 조사
        if (&s == this)
            return *this;

        size = s.size;

        delete[] buff; // 기존 메모리 해지
        buff = new char[size + 1]; // 대입받는 문자열 사이즈로 메모리 동적 할당
        strcpy(buff, s.buff);

        return *this;
    }

    friend std::ostream& operator<<(std::ostream& os, const String& s); // 멤버 외부 접근용 friend 선언
};

std::ostream& operator<<(std::ostream& os, const String& s)
{
    os << s.buff;
    return os; 
}

int main()
{
    String s1 = "apple"; // 복사 생성자
    String s2 = "banana"; // 복사 생성자

    s1 = s2; // 대입 연산자 지원
    s1 = s1; // 자신에 대한 대입 연산자 지원

    std::cout << s1 << std::endl; // cout 출력 지원
}

• 대입 연산자
  • 객체의 멤버를 모두 복사해주는 연산자
• 생성하지 않을경우 컴파일러가 자동으로 제공하는 멤버들
  • 기본 생성자
  • 소멸자
  • 복사 생성자(Shallow Copy)
  • 대입 연산자
  • move 생성자
  • move 대입 연산자

class Point
{
    int x, y;
public:
    Point(int a = 0, int b = 0) : x(a), y(b) {}

    void print() const
    {
        std::cout << x << ", " << y << std::endl;
    }

    Point& operator=(const Point& p)
    {
        x = p.x;
        y = p.y;

        return *this;
    }

};

int main()
{
    Point p1(1, 1);
    Point p2(2, 2);
    Point p3;
    p3 = (p1 = p2);

    (p3 = p1) = p2; // 대입 연산자가 참조 리턴을 하지 않으면 p3에 p2가 대입되지 않음

    p3.print();

}