1. Sorting array (selection sort)

선택 정렬을 이용한 배열 정렬

배열을 정렬한다는건 배열의 모든 element를 특정 조건에 맞는 순서로 정렬하는걸 의미한다
ex) 연락처 이름순, 이메일 최신순

배열을 정렬하게 되면 사람뿐 아니라 컴퓨터에서도 배열 검색을 효율적으로 만들 수 있다
ex) 이름 검색 시 가나다 순으로 정렬되어 있으면 더 효율적으로 검색 가능

심지어 정렬하게 되면 배열 검색 자체를 하지 않아도 되는 상황도 많이 존재한다 (최대, 최소 찾기)

일반적으로 정렬이란 배열 element 쌍을 비교하고 기준에 충족하면 교환하는 방식으로 설계한다, 굉장히 다양한 정렬 알고리즘이 존재한다

C++ STL에는 두 element를 교환할 수 있게 해주는 std::swap()함수가 정의되어 있다

	#include <utility>  // std::swap을 사용하기 위함

    int a{ 10 };
    int b{ 20 };

    std::swap(a, b); //a에 20, b에 10이 들어가게 된다

selection sort

다양한 정렬 방법중에 이해하기 가장 쉽지만 가장 느린 정렬 중 하나인 선택 정렬이다

배열의 element를 오름차순으로 정렬한다고 가정했을때 선택 정렬은 다음과 같은 단계들을 수행한다

1. 배열 index 0에서 시작해서 전체 배열을 검색 후 가장 작은 값을 찾는다
2. 배열에서 찾은 가장 작은 값을 index 0값과 교환
3. 다음 인덱스부터 다시 시작해서 1, 2단계를 반복한다

예를들어 { 30, 20, 50, 80, 70 }이 있다고 가정하면 1번 단계를 거치면 20, 30, 50, 80, 70이 된다, 이 단계를 반복하여 수행해서 20 30 50 70 80을 만드는것이다

선택 정렬을 C++로 구현해보면 다음과 같다

	int array[]{ 30, 20, 50, 80, 70 };
    constexpr int length{ static_cast<int>(std::size(array)) };

    for (int start{ 0 }; start < length - 1; ++start) //마지막은 어차피 정렬된 상태기 때문에 -1
    {
        int smallestIndex{ start };

		for (int current{ start + 1 }; current < length; ++current)
		{
			if (array[current] < array[smallestIndex])
			{
				smallestIndex = current;
			}
		}

		std::swap(array[start], array[smallestIndex]);
    }

이러한 배열 정렬은 C++ STL에 std::sort()로 구현되어 있다 (algoritm헤더를 include해야함)

    int array[]{ 30, 20, 50, 80, 70 };

	std::sort(std::begin(array), std::end(array)); //오름차순으로 정렬한다

내부적으로 위의 직접 구현한 selection sort와 유사하게 동작하지만 실제로는 더 효율적인 알고리즘을 사용한다 (intro sort)

std::begin()과 std::end()는 각각 container의 시작, 끝 다음을 가리키는 iterator를 return한다

2. Iterator

Iterator

컨테이너를 순회하는 작업은 굉장히 자주 있는 일이다, 이제까지 for, while, for-each와 같은 loop와 포인터 연산을 사용하여 순회하는 방법을 정리했다

index를 사용하여 순회하는 것은 몇가지 단점이 존재한다, 우선 list와 같은 컨테이너들은 element에 대한 직접 접근이 불가능하기 때문에 사용이 불가능하며 단순히 element에 접근하는 용도로만 사용한다면 필요 이상의 타이핑이 생길 수 있다

또한 포인터 연산으로 컨테이너의 element 순회는 배열과 같은 컨테이너처럼 element가 연속적으로 있을때만 작동한다 (list, map과 같은 컨테이너는 그렇지 않다)

물론 포인터 연산 없이, 포인터는 일부 비순차적 구조를 순회하는데 사용할 수 있다 (linked list의 각 element는 포인터를 통해 이전 element에 연결된다 -> 따라서 포인터 체인으로 list 순회가 가능하다)

for-each는 컨테이너를 순회할 수 있다 (array, list, tree, map 등 거의 다 동작), 그렇다면 전부 각기 다른 컨테이너인데 for-each는 어떻게 전부 동작이 가능한걸까? 바로 iterator를 사용하기 때문이다

iterator는 컨테이너를 순회하도록 설계된 객체이다 (각 element에 접근을 제공한다)

컨테이너들은 다양한 종류의 iterator를 제공한다, 예를들어 배열 컨테이너는 배열을 순방향으로 탐색하는 순방향 iterator와 반대로 역방향으로 탐색하는 역방향 iterator를 제공한다

이러한 iterator 객체가 제공하는 인터페이스를 사용하여 컨테이너를 순회할 수 있다

pointer iterator

가장 간단한 종류의 iterator는 포인터이다, 앞서 정리한대로 포인터 연산을 이용하여 순회한다 (따라서 메모리에 순차적으로 저장된 데이터에 대해 작동한다)

	std::array arr{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	auto begin{ &arr[0] }; //std::array인 arr의 0번째 element를 가리키는 포인터
    
	auto end{ begin + std::size(arr) };
    auto end{ arr.data() + std::size(arr) }; //이렇게도 가능!

	for (auto ptr{ begin }; ptr != end; ++ptr) //순회
	{
		std::cout << *ptr << std::endl; //역참조로 값 가져오기
	}

여기서 중요한 점은 std::size(arr)을 이용하여 인덱싱을 하게 되면 out of bound값을 역참조 하기 때문에 정의되지 않은 동작이 발생할 수 있다

	arr[std::size(arr)]; //crash!

또한 C-style 배열과 같은경우에는 다음과 같이 사용이 가능하다 (decay)

	int arr[7];
    int* end{ arr + std::size(arr) };

STL iterator

모든 STL 컨테이너는 순회를 지원한다, 위 코드처럼 직접 begin과 end를 계산하는 방식보다 컨테이너의 begin()과 end() 멤버함수를 통해 더 편리하게 시작점과 끝점을 얻을 수 있다

	#include <iterator>

	std::array arr{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	auto begin{ arr.begin()};
	auto end{ arr.end()};

	for (auto ptr{ begin }; ptr != end; ++ptr)
	{
		std::cout << *ptr << std::endl; //역참조로 값 가져오기
	}

C-style 배열을 위한 begin()과 end()는 < iterator > 헤더에 존재하며 std::로 사용이 가능하다 (물론 STL 컨테이너에 사용도 가능함)

	int temparr[10]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	std::begin(temparr);
	std::end(temparr);

std::array외에 vector나 다른 컨테이너들도 begin과 end가 멤버함수로 정의되어 있다 (해당 컨테이너 헤더파일에 정의됨, 결국 이러한 헤더파일들은 내부적으로 < iterator >헤더를 include 하고 있음)

iterator 사용 시 operator >와 operator !=

일반적으로 for-loop에서 숫자 비교를 할 때 !=보다는 >를 권장한다, 하지만 iterator는 !=를 더 권장한다 (원하는 곳까지 도달했는지 체크하기 위해서)

	for(auto it{ begin }; it != end; ++it)

왜냐하면 일부 iterator타입은 > 비교가 불가능하기 때문이다, !=는 모든 iterator 타입에 대해 잘 작동한다

for-each 동작

begin(), end() 멤버함수를 가지고 있거나 std::begin(), std::end()에 사용할 수 있는 타입은 전부 for-each loop에서 사용할 수 있다

	std::array arr{ 1, 2, 3 };
    for(int i : arr)
    {
    }

for-each loop는 내부적으로 순회할 컨테이너 타입의 begin()과 end()를 호출한다, 따라서 위에 arr은 std::array이고 begin(), end() 멤버 함수가 존재하기 때문에 for-each loop에서 사용이 가능하다

C-style 배열도 위에서 정리했듯 std::begin, std::end 사용이 가능한 컨테이너 타입이기 때문에 for-each loop에서 사용이 가능하다

단 동적 C-style 배열이나 포인터 타입으로 decay된 C-style 배열은 for-each에서 사용이 불가능하다 (std::end 개념이 없기 때문, 타입 정보에 길이 정보가 없다)

이러한 for-each loop 이외에도 다양한 알고리즘에서 iterator를 사용한다

iterator invalidated

순회하려는 컨테이너의 element가 파괴되거나 주소가 변경되면 기존의 iterator는 dangling 상태가 될 수 있다 (포인터, 참조와 같이)

이때 iterator가 invalidated되었다고 하며 invalidated 된 iterator에 접근 시 정의되지 않은 동작 및 크래시가 발생할 수 있다

컨테이너를 수정하는 작업 ex) std::vector에 capacity가 부족하여 메모리 재할당 후 element 추가가 될 때 컨테이너의 element주소가 변경되는 현상이 있을 수 있다(vector의 모든 element가 새 메모리 위치로 복사/이동 되기 때문에), 이렇게 되면 결국 기존 iterator는 invalidated되게 되고 사용하지 않아야 한다

    std::vector<int> v{ 1, 2, 3, 4, 5, 6, 7 };

    auto it{ v.begin() }; // it는 v의 첫 번째 요소(1)를 가리킴

    ++it; // 두 번째 요소(2)로 이동
    std::cout << *it << '\n'; // 정상: 2를 출력

    // v.erase(it)는 it가 가리키는 요소(2)를 삭제
    v.erase(it);

    // erase()는 삭제된 요소 (및 그 이후 요소들)에 대한 iterator를 무효화
    // 따라서 iterator "it"는 이제 무효화됨

     ++it;             // 정의되지 않은 동작: 무효화된 이터레이터를 증가시키려고 함
     std::cout << *it << '\n'; // 정의되지 않은 동작: 무효화된 이터레이터를 역참조

여기서 erase()는 삭제된 element 바로 다음 element를 가리키는 iterator를 return한다 (이때 마지막 element가 erase()되면 end()를 return한다)

	std::vector<int> v{ 1, 2, 3, 4, 5, 6, 7 };

    auto it{ v.begin() };

    ++it;
    
    std::cout << *it << '\n'; //2

    it = v.erase(it); //3을 가리키는 iterator

    ++it;             
    std::cout << *it << '\n'; //4

3. STL algorithm

STL algorithm

컨테이너를 정렬, 카운팅, 검색 등과 같은 작업은 굉장히 자주 사용되는 작업인 만큼 STL에 이미 정의되어 있다 (프로그래머가 직접 함수를 만들어 사용하면 휴먼 에러가 발생할 가능성이 높다, 이미 검증된 STL algorithm을 사용하는걸 권장한다)

사전에 테스트되어 검증되고 효율적이며 다양한 컨테이너에서 작동한다, 또한 다수의 algorithm은 멀티 스레딩을 지원한다

대부분의 STL algorithm은 다음 세 가지 카테고리에 속하게 된다

• Inspector (검사)
  컨테이너의 데이터를 보기 위해 사용된다 (수정은 아님), 검색이나 갯수 카운팅이 있다

• Mutator (변경)
  컨테이너의 데이터를 수정하기 위해 사용된다 (정렬, 셔플링)

• Facilitator (조력)
  데이터 멤버의 값을 기반으로 결과를 생성한다 (값을 곱해주는 객체, element쌍이 어떤 순서로 결정되어야 하는지 결정하는 객체)

std::find

std::find는 컨테이너에서 특정 값의 첫 번째 발생을 검사한다, 총 3개의 매개변수를 받는다 (시작 element를 가리키는 iterator, 끝 element를 가리키는 iterator, 검색할 값)

element를 찾으면 해당 element를 가리키는 iterator를 return하고 찾지 못한다면 해당 컨테이너의 end iterator를 return한다

	std::array array1{ 1, 4, 3, 4, 5 };

	auto found{ std::find(array1.begin(), array1.end(), 4) };

	std::cout << *found << std::endl; //제일 앞에있는 4를 가리키는 iterator임

std::find_if

정확한 값 대신 특정 조건을 만족하는 값이 컨테이너에 있는지 확인하고 싶을때 사용한다

std::find와 유사하게 동작하지만 검색할 특정 값을 전달하는 대신 함수 포인터나 람다 함수 전달이 필요하다, find_if는 이렇게 전달된 함수를 호출하고 true/false를 return할 수 있다

    bool containBlue(std::string_view str)
    {
        return str.find("blue") != std::string_view::npos;
    }

    int main() 
    {
        std::array<std::string_view, 4> arr{ "red", "redorange", "blue", "bluegreen" };

        auto found{ std::find_if(arr.begin(), arr.end(), containBlue) };

        std::cout << *found << std::endl; //blue

        return 0;
}

string_view::find()로 부분 문자열을 찾지 못하면 std::strig_view::npos를 return하고 찾으면 해당 부분 문자열이 발생한 index를 return한다

containBlue에서 "blue" element가 조건을 만족하여 true를 return했기 때문에 *found 역참조 값은 blue가 된다

std::count & std::count_if

std::count와 std::count_if는 특정 element 혹은 조건을 만족하는 모든 element의 발생을 검색하여 카운팅한다

	bool containBlue(std::string_view str)
    {
        return str.find("blue") != std::string_view::npos;
    }

    int main() 
    {
        std::array<std::string_view, 4> arr{ "red", "redorange", "blue", "bluegreen" };

        auto blues{ std::count_if(arr.begin(), arr.end(), containBlue) }; //2
        auto reds{ std::count(arr.begin(), arr.end(), "red") }; //2

        std::cout << blues << std::endl;

        return 0;
    }

std::sort

이전에 std::sort를 이용하여 오름차순 정렬을 했는데, std::sort에도 함수 포인터나 람다를 넘겨서 원하는대로 정렬이 가능하다

    bool greater(int a, int b)
    {
        return a > b;
    }

    int main() 
    {
        std::array arr{ 20, 10, 30, 60, 40 };
        std::sort(arr.begin(), arr.end(), greater); //60, 50, 30, 20, 10

        return 0;
    }

greater는 분명 2개의 인자를 넘겨야 하지만 아무런 인자도 전달하지 않아도 잘 동작한다, 이는 함수 포인터로 전달하기 때문이다 (배열의 임의의 두 element를 가지고 함수를 호출한다)

이러한 내림차순은 std::greater라는 사용자 정의 타입을 C++에서 제공한다 (< functional > 헤더의 일부임)

	std::array arr{ 20, 10, 30, 60, 40 };
	std::sort(arr.begin(), arr.end(), std::greater{});

C++17 이전에는 std::greater{} 사용 시 element 타입을 반드시 명시해야 했다 (std::greater< int >{})

std::sort가 비교함수를 어떻게 사용하는지 자세히 확인해보자

	//기존의 sort구현
    void sort(int* begin, int* end) 
    {
      // end-1 까지 반복하는 이유는 마지막 요소는 비교 대상이 하나뿐이므로
      // 그 이전까지만 정렬되면 자동으로 정렬되기 때문
      for (auto startElement{ begin }; startElement != end -1; ++startElement) 
      {
          auto smallestElement{ startElement };

          // std::next는 (startElement + 1)과 같이 다음 요소를 가리키는 포인터(iterator)를 반환한다
          for (auto currentElement{ std::next(startElement) }; currentElement != end; ++currentElement) 
          {
              if (*currentElement < *smallestElement) 
              {
                  smallestElement = currentElement;
              }
          }
          std::swap(*startElement, *smallestElement);
      }
	}

    int main() 
    {
        int array[]{ 2, 1, 9, 4, 5 };

        sort(std::begin(array), std::end(array)); // 배열의 시작과 끝 이터레이터(여기서는 포인터)를 전달

        for (auto i : array) {
            std::cout << i << ' ';
        }
        std::cout << '\n';

        return 0;
    }

이제 기존의 sort()에 비교함수를 넣는 방식으로 구현해보자

비교함수를 넣기 위해서는 std::function< bool(int, int)>를 넣어주어야 한다 (추후에 설명)

	#include <functional> // std::function, std::greater를 사용하기 위함
    #include <iostream>
    #include <iterator>   // std::begin, std::end, std::next
    #include <utility>    // std::swap

    void sort(int* begin, int* end, std::function<bool(int, int)> compare) 
    {
        for (auto startElement{ begin }; startElement != end - 1; ++startElement) 
        {
            auto biggestElement{ startElement };

            for (auto currentElement{ std::next(startElement) }; currentElement != end; ++currentElement) 
            {
                // compare는 currentElement가 biggestElement보다 먼저 정렬되어야 하는지 확인
                if (compare(*currentElement, *biggestElement)) 
                {
                    biggestElement = currentElement;
                }
            }
            std::swap(*startElement, *biggestElement);
        }
    }

    int main() 
    {
        int array[]{ 2, 1, 9, 4, 5 };

        // std::greater를 사용하여 내림차순 정렬
        // 직접 만든 sort 함수와 std::sort 간의 충돌을 방지하기 위해
        // 전역 네임스페이스 선택자(::)를 사용
        ::sort(std::begin(array), std::end(array), std::greater{}); // std::greater{} 객체 전달

        for (auto i : array) 
        {
            std::cout << i << ' ';
        }
        std::cout << '\n';

        return 0;
    }

std::for_each

std::for_each는 컨테이너의 모든 element를 사용자 정의 함수에 적용한다

	void doubleNum(int& i) //원본 수정을 위한 참조타입
    {
        i *= 2;
    }

    int main() 
    {
        std::array arr{ 20, 10, 30, 60, 40 };
        std::for_each(arr.begin(), arr.end(), doubleNum); //전부 2배가 됨

        return 0;
    }

그렇다면 그냥 for_each loop을 사용하는것보다 좋은점은 뭘까?

우선 std::for_each를 사용하게 되면 의도가 명확해진다 (모든 element에 대해 특정 함수를 호출하여 적용하라)

for_each loop에는 새로운 변수를 추가해야 한다, 이는 곧 휴먼 에러로 직결될 수 있다

또한 std::for_each는 컨테이너의 시작이나 끝에 있는 element를 건너뛸 수 있다

	std::array arr{ 20, 10, 30, 60, 40 };
	std::for_each(std::next(arr.begin()), arr.end(), doubleNum); //20, 20, 60, 120, 80

C++20부터는 begin()과 end()를 사용하지 않아도 된다, for_each 뿐 아니라 begin, end가 필요한 부분에 std::ranges::를 사용하게 되면 단순하게 컨테이너만 전달해서 사용이 가능하다

	std::ranges::for_each(arr, doubleNum);

std::next()는 다음 element를 가리키는 iterator를 return한다

STL 알고리즘의 많은 알고리즘은 성능이나 실행 순서에 대한 보장을 한다 (std::for_each는 각 element에 한번씩 순차적으로 접근될 것을 보장한다)

따라서 반드시 순차적으로 접근해서 동작해야하는 상황이라면 순차적 실행 순서에대한 보장이 있는 알고리즘을 사용해야 한다
(std::for_each, std::copy, std::copy_backward, std::move, std::move_backward)

이 이외에도 다양한 순방향 iterator를 사용하는 알고리즘들은 암묵적으로 순방향이다