_C++_알고리즘_Part_2

비교 알고리즘

항목열 간 비교를 하기 위해 equal, mismatch, lexicographical_compare 함수 중 하나를 선택하여 사용하면 된다.

equal, mismatch는 첫 컨테이너에 대해 두 개의 반복자를 필요로하며 두 번째 컨테이너에 대해서는 끝 반복자를 선택적으로 받는다.

두 번째 컨테이너의 시작 반복자만 제공한 경우에는 첫 번째 항목열의 크기만큼만 비교한다. (비교에 사용할 함수를 함수 객체로 전달하여 커스텀이 가능하다.)

비교알고리즘 대신 operator==, operator<를 바로 사용할 수 있다.

 

equal()

두 항목열이 완전히 같으면 true를 리턴한다.

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

using namespace std;

int main(){
    vector<int> v { 1, 2, 3, 4, 5 };
    list<int> l { 1, 2, 3, 4, 5, 6 };
    array<int, 5> a {-1, -2, -3, 4, -5};

    cout << boolalpha;
    cout << equal(v.begin(), v.end(), l.begin(), l.end()) << endl; // false
    cout << equal(v.begin(), v.end(), l.begin()) << endl; // true
    cout << equal(v.begin(), v.end(), a.begin(), [](int a, int b) { //비교 함수
        return abs(a) == abs(b); // v의 첫 번째와 a의 첫 번째 항목을 절대값으로 비교
    }) << endl; // true
    return 0;
}

mismatch()

항목열을 서로 비교하다가 불일치가 처음 발생하는 위치의 반복자를 리턴한다.

이 때, pair로 리턴된다.

- first: 첫 번째 항복열에 대한 반복자

- second: 두 번째 항목열에 대한 반복자.

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

using namespace std;

int main(){
    vector<int> v {1, 2, 3, 4, 5};
    list<int> l {1, 2, 3, 5, 5};
    auto miss = mismatch(v.begin(), v.end(), l.begin()); // 4번째에서 mismatch 발생
    for (auto iter = v.begin(); iter != miss.first; ++iter)
    {
        cout << *iter << ' ';// 1 2 3출력
    }
    return 0;
}

 

lexicographical_compare()

두 항목열을 사전순으로 비교한다.

- 첫 번째 항목열이 사전순으로 앞서는 경우: true

- 그렇지 않는 경우: false

이때 기본적으로 대소문자를 구분하고 대문자가 소문자보다 사전순으로 앞서는 것으로 취급한다.

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

using namespace std;

int main(){
    string s { "String" };
    list<char> l {'s', 't', 'r'};

    cout << lexicographical_compare(s.begin(), s.end(), l.begin(), l.end()) << endl; //true
    cout << lexicographical_compare(s.begin(), s.end(), l.begin(), l.end(), [](char a, char b) {
        return tolower(a) < tolower(b);
    }) << endl; // false
    return 0;
}

---

변경 알고리즘

copy()

copy함수는 특정 범위의 항목들을 다른 범위로 차례로 복제한다.

#include <iostream>
#include <vector>

using namespace std;

int main(){
    vector<int> vec1{ 1, 2, 3 }, vec2;
    vec2.resize(vec1.size());
    copy(vec1.cbegin(), vec1.cend(), vec2.begin());
    for (auto& item : vec2)
        cout << item << ' ';
    return 0;
}

copy_n함수는 원본 범위를 반복자 쌍이 아닌, 시작반복자와 개수를 인자로 넘겨서 복제한다.

만약 원본 범위에서 특정 조건에 해당하는 항목만 사용하고 싶다면, copy_if함수를 사용하면 된다.

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

using namespace std;

int main(){
    vector<int> vec1{ 1, 2, 3 }, vec2;
    vec2.resize(vec1.size());// vec1의 크기만큼 확보

    //copy_n
    copy_n(vec1.begin(), 2, vec2.begin()); //처음부터 count의 개수만큼 vec2에 복사
    vec2.erase(vec2.begin() + 2, vec2.end());
    for (auto item : vec2)
        cout << item << " "; // 1, 2
    cout << "\n";
    vec2.clear();

    //copy_if
    auto endIter = copy_if(vec1.cbegin(), vec1.cend(), vec2.begin(), [](int i){
        return (i & 1) == 0;
    }); // 짝수만 복사
    vec2.erase(endIter, vec2.end()); 
    //copy_if는 마지막 복제 항목 직후 위치에 접근하는 반복자를 리턴하는데
    //이를 통해 삭제해야할 범위를 알 수 있음
    for (auto item : vec2)
        cout << item << ' '; // 2
}

 

move()

move함수는 두가지 버전이 있다.

1. 입력: 하나의 임의의 타입을 갖는 인자를 받음, 출력: 우측값으로 캐스팅해줌.(컴파일러에게 이동해도 좋은 객체임을 알려줌.)
2. 입력: 세개의 반복자를 받음. 출력: 항목열 전체 또는 항목열 일부를 다른 컨테이너로 옮김.

#include <iostream>
#include <vector>

using namespace std;

class MyClass
{
	string mStr;
public:
	MyClass() = default;
	MyClass(const string& str) : mStr(str) {}
	MyClass(MyClass&& rhs) = default;
	MyClass& operator=(MyClass&& rhs) {
		if (this == &rhs) return *this;
		//하나의 인자를 받음.
		mStr = move(rhs.mStr);
		cout << "Move operator= (mStr=" << mStr << ')' << endl;
		return *this;
	}
	string getString() const { return mStr; }
};

int main()
{
	vector<MyClass> vecSrc;
	vecSrc.reserve(3);
	vecSrc.emplace_back("a");
	vecSrc.emplace_back("b");
	vecSrc.emplace_back("c");
	vector<MyClass> vecDst(vecSrc.size()); //이동할 객체 선택
	//verSrc.begin()부터 verSrc.end()까지, vecDst.begin()부터 하나씩 이동.
	move(vecSrc.begin(), vecSrc.end(), vecDst.begin());
	for (auto& c : vecDst)
		cout << c.getString() << ' ';
	vecSrc.erase(vecSrc.begin(), vecSrc.end()); 
	//이동 대입후 원본 객체는 내부 리소스를 리셋하기 때문에 빈 껍데기로 남는데
	//사용할 수 없는 객체이므로 삭제해주어야 함
    return 0;
}

 

remove(), remove_if()

remove와 remove_if는 함수를 삭제한다고 알고 있지만, 사실은 주어진 범위에 대해 삭제할 항목과 남겨둘 항목끼리 옮겨서 나누는 역할을 한다. 이는 vector와 배열과 같이 연속한 메모리 구조를 유지해야하는 경우 바로 삭제하는 것이 비효율적이기 때문이다.

remove: 값을 인자로 넘겨 동일한 값을 가지는 항목을 삭제할 항목으로 분류.

remove_if:  bool을 리턴하는 함수 객체 등을 인자로 받아 삭제할 항목의 조건을 커스텀할 수 있게 해줌.

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

using namespace std;

int main()
{
	vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8, 9, };
    auto it1 = remove(v.begin(), v.end(), 5); //5를 삭제할 항목으로 분류
    v.erase(it1, v.end());

    for(int num : v) cout << num; // 12346789
    cout << "\n";

    auto it2 = remove_if(v.begin(), v.end(), [](const int& a){
        return (a & 1) == 0;
    }); // 짝수 항목을 따로 모음.

    v.erase(it2, v.end());
    for(int num : v) cout << num; // 1379
    cout << "\n";

    return 0;
}

 

replace(), replace_if()

replace: 특정 값을 새로운 값으로 교체.

replace_if: 특정 조건에 맞는 항목을 새로운 값으로 교체.

find와 다르게 모든 항목을 찾아주기 때문에 찾아 바꾸기를 한다면 해당 함수를 사용하는게 좋다.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    string s = "Hellow world";
    string find_s = "world"; //찾을 문자열
    string replace_s = "blue"; //교체할 문자열
    //find_s의 위치와 길이를 찾고 문자열 교체
    s.replace(s.find(find_s), find_s.length(), replace_s);
    cout << s << "\n"; //Hellow blue

    vector<int> v { 1, 2, 3, 4, 5 };
    replace_if(v.begin(), v.end(), [](const int n) {
        return n <= 3;
    }, 0); // v내부의 값중 3보다 작거나 같다면 0으로 변환
    for(int& num : v) cout << num; //00045
    return 0;
}

 

unique()

주어진 항목내에서 연속적으로 중복되는 값을 제거해준다.

remove처럼 중복되는 값을 뒤쪽으로 모아서 따로 분리하고 중복 항목이 시작하는 위치를 가르키는 반복자를 리턴한다.

연속적으로 중복된 값만 처리하므로, 이산적인 컨테이너를 sort로 정렬하고 사용해야한다.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v { 1, 2, 3, 4, 5, 1, 3 };
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int& num : v) cout << num; //12345
    return 0;
}

 

reverse()

주어진 항목열을 반전시켜주는 함수이다. 단순히 역방향의 순회를 목적으로 사용한다면, 해당 함수를 권장하지 않는다.

양방향 반복자를 요구하는 함수이기 때문에 forward_list의 항목열에 대해서는 이 함수를 사용할 수 없고 메서드로 reverse를 제공한다.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v { 1, 2, 3, 4, 5 };
    reverse(v.begin(), v.end());
    for(int& num : v) cout << num; //54321
    return 0;
}

 

next_permutation(), prev_permutation()

주어진 항목열을, 그 항목들로 생성 가능한 다음 순열 조합, 또는 이전 순열 조합으로 변환해준다.

양방향 반복자를 요구하는 함수이기 때문에 forward_list는 사용할 수 없다.

bool타입 반환값이 있어서 순열 조합의 마지막에 도달하면, false를 반환, 그렇지 않다면 true를 반환한다.
주로 do - while()과 함께 사용한다.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v { 1, 2, 3 };
    do{
        for(int& num : v)
            cout << num;
        cout << endl;
    }while(next_permutation(v.begin(), v.end()));
    return 0;
} // 123, 132, 213, 231, 312, 321

 

---

집합 알고리즘

집합 알고리즘은 정렬된 상태의 항목열을 대상으로 사용한다.

비순차 연관 컨테이너에서는 올바르게 작동하지 않는다.

includes()

부분 집합 여부를 판정한다.

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main()
{
    vector<int> v1 { 3, 4, 2, 1, 5 };
    set<int> s1 {5, 2, 1}; // set은 자동으로 정렬해줌
    sort(v1.begin(), v1.end());
    cout << boolalpha << includes(v1.begin(), v1.end(), s1.begin(), s1.end()); // true   
}

 

set_union()

합집합을 구해 결과집합에 담아준다.

결과 집합의 크기는 미리 확보되어야 한다.(두 집합의 크기 합과 같도록 준비)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v1 { 1, 3, 5, 8, 10 }, v2{ 1, 2, 3, 4, 5 }, result(10);
    auto eIter = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    result.erase(eIter, result.end()); // 빈부분 제거
    for(int& num : result) cout << num << " ";
    cout << "\n"; // 1 2 3 4 5 8 10
    return 0;
}

 

set_intersection()

교집합을 구해 결과 집합에 담아준다.

결과 집합의 크기는 미리 확보되어야 한다.(두 집합 중 큰 것과 같도록 준비)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v1 { 1, 3, 5, 8, 10 }, v2{ 1, 2, 3, 4, 5 }, result(5);
    auto eIter = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    result.erase(eIter, result.end()); // 빈부분 제거
    for(int& num : result) cout << num << " ";
    cout << "\n"; // 1 3 5
    return 0;
}

 

set_difference()

차집합을 구해 결과 집합에 담아준다.

결과 집합의 크기는 미리 확보되어야 한다.(첫 번째 집합의 크기와 같도록 준비)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v1 { 1, 3, 5, 8, 10 }, v2{ 1, 2, 3, 4, 5 }, result(5);
    auto eIter = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    result.erase(eIter, result.end()); // 빈부분 제거
    for(int& num : result) cout << num << " ";
    cout << "\n"; // 8 10
    return 0;
}

 

set_symmetric_difference()

대칭 차집합을 구해 결과 집합에 담아준다.

결과 집합의 크기는 미리 확보되어야 한다.(두 집합의 크기 합과 같도록 준비)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v1 { 1, 3, 5, 8, 10 }, v2{ 1, 2, 3, 4, 5 }, result(10);
    auto eIter = set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    result.erase(eIter, result.end()); // 빈부분 제거
    for(int& num : result) cout << num << " ";
    cout << "\n"; // 2 4 8 10
    return 0;
}