[C++ 프로그래밍 / STL] Chapter4. 알고리즘 Part.2

Chapter4. 알고리즘 Part.2

1. 비교 알고리즘

항목열 간 비교에는 equal 함수, mismatch 함수, lexicographical_compare 함수 중 하나를 선택할 수 있다. equal과 mismatch 함수의 경우 첫 번째 컨테이너에 대해서는 두개의 반복자를 필요로하며 두 번째 컨테이너에 대해서는 끝 반복자를 선택적으로 받는다. 두 번째 컨테이너의 시작 반복자만 제공한 경우 첫 번째 컨테이너의 항목열의 크기만큼만 비교한다. 또한 비교에 사용할 함수를 함수객체로 전달하여 커스텀이 가능하다.
같은 타입의 두 컨테이너 간에 항목들을 비교하고자 한다면 비교 알고리즘 대신 operator ==나 operator <를 바로 사용할 수 있다. 비교 알고리즘의 효용성은 서로 다른 타입의 컨테이너들을 비교할 수 있다는 데 있다.

---

1) equal()

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

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);
}) << endl; //true

---

2) mismatch()

항목열을 서로 비교하다가 불일치가 처음 발생하는 위치의 반복자를 리턴한다. 이때 pair로 리턴되며 first는 첫 번째 항목열에 대한 반복자, second는 두 번째 항목열에 대한 반복자이다.

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());
for (auto iter = v.begin(); iter != miss.first; ++iter)
{
	cout << *iter << ' ';
}
// 1 2 3

---

3) lexicographical_compare()

두 항목열을 사전순으로 비교하여 첫 번째 항목열이 사전순으로 앞서면 true를 그렇지 않으면 false를 리턴한다. 이때 기본적으로 대소문자를 구분하고 대문자가 사전순으로 앞서는 것으로 취급한다.

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

---

2. 변경 알고리즘

1) copy()

copy 함수는 특정 범위의 항목들을 다른 범위로 차례로 복제한다. 이때 원본 범위와 대상 범위는 같지 않아야 한다.

vector<int> vec1, vec2;
//...vec1에 대한 항목 삽입 생략
vec2.resize(vec1.size());
copy(vec1.cbegin(), vec1.cend(), vec2.begin());
for (auto item : vec2)
	cout << item << ' ';

copy_n 함수를 쓰면 원본 범위를 반복자 쌍이 아니라 시작 반복자와 개수를 인자로 넘겨서 복제한다.
만약 원본 범위에서 특정 조건에 해당하는 항목만 대상 범위로 복제하고 싶다면 copy_if 함수를 사용하면 된다.

vector<int> vec1, vec2;
//...vec1에 대한 항목 삽입 생략
vec2.resize(vec1.size()); //vec1 전체가 복사될 수도 있기 때문에 vec1의 크기만큼 우선 확보
auto endIter = copy_if(vec1.cbegin(), vec1.cend(), vec2.begin(), [](int i){
	return (i & i) == 0;
}); //짝수만 복사
vec2.erase(endIter, vec2.end());
//copy_if는 마지막 복제 항목 직후 위치에 접근하는 반복자를 리턴하는데
//이를 통해 삭제해야할 범위를 알 수 있음
for (auto item : vec2)
	cout << item << ' ';

---

2) move()

move 함수는 하나의 임의의 타입을 갖는 인자를 받는 버전이 있고 세개의 반복자를 받는 버전이 있다. 전자는 우측값으로 캐스팅해주는 함수이며 임시객체가 아니더라도 이를 이용하면 컴파일러에게 이동해도 좋은 객체임을 알려줄 수 있다. 후자는 항목열 전체 또는 항목열 일부를 다른 대상 컨테이너로 옮기는 함수이다.

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.reverse(3);
    vecSrc.emplace_back("a");
    vecSrc.emplace_back("b");
    vecSrc.emplace_back("c");
    vector<MyClass> vecDst(vecSrc.size());
    move(vecSrc.begin(), vecSrc.end(), vecDst.begin());
    for (auto& c : vecDst)
    	cout << c.getString() << ' ';
    vecSrc.erase(vecSrc.begin(), vecSrc.end());
    //이동 대입후 원본 객체는 내부 리소스를 리셋하기 때문에 빈 껍데기로 남는데
    //사용할 수 없는 객체이므로 삭제해주어야 함
}

---

3) remove(), remove_if()

remove와 remove_if 함수는 주어진 범위에 대해 삭제할 항목과 남겨둘 항목끼리 모이도록 옮겨서 나눈다. 이름과 달리 실제로 삭제를 수행해주지는 않는데 vector나 배열과 같이 연속한 메모리 구조를 유지해야하는 경우 그때 그때 삭제하는 것은 매우 비효율적이기 때문이다.
remove는 값을 인자로 넘겨 동일한 값을 가지는 항목을 삭제할 항목으로 분류해주고, remove_if는 bool을 리턴하는 함수 객체 등을 인자로 받아 삭제할 항목의 조건을 커스텀할 수 있게 해준다.
이들은 삭제해야 할 항목들이 시작하는 위치의 반복자를 반환해준다. 따라서 해당 반복자와 end 반복자를 범위로 하여 erase 메서드를 호출해주면 일괄적으로 항목들을 삭제할 수 있다.

void removeEmptyStrings(vector<string>& strings)
{
	auto it = remove_if(strings.begin(), strings.end(), [](const string& str){
    	return str.empty();
    });
    strings.erase(it, strings.end());
}

---

4) replace(), replace_if()

특정 값 또는 특정 조건에 맞는 모든 항목을 새로운 값으로 교체한다. find와 다르게 모든 항목을 찾아주기 때문에 찾아 바꾸기 동작이 필요하다면 이 함수들을 사용하는 것이 가장 간단한 방법일 것이다.

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

using namespace std;

int main()
{
	vector<int> v;
    //...항목 삽입 생략
    
    int lower = numeric_limits<short>::min();
    int upper = numeric_limits<short>::max();
    
    replace_if(v.begin(), v.end(), [lower](int i) {return i < lower; }, lower);
    replace_if(v.begin(), v.end(), [upper](int i) {return i > upper; }, upper);
}

위 코드는 replace_if를 통해 클램핑(clamping)을 수행하는 예를 보여준다.

---

5) unique()

주어진 항목열 내에서 연속적으로 중복되는 값들을 제거하기 위한 함수이다. remove 함수와 마찬가지로 실제로 항목을 삭제해주지는 않고 중복되는 값들을 뒤쪽에 모아 분리해주고 중복 항목들이 시작하는 위치를 가리키는 반복자를 리턴해준다.
연속적으로 중복되는 값만 처리되기 때문에 이산적인 중복 값들을 처리하고 싶다면 정렬 등의 작업을 선행하여 중복 값들이 모여있도록 만들어 주어야 한다.

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

using namespace std;

int main()
{
	vecotr<int> v { 1, 1, 0, 6, 6, 2 };
    v.erase(unique(v.begin(), v.end()), v.end()); //중복 항목 삭제
    for (auto val : v)
    	cout << val << ' '; // 1 0 6 2
}

---

6) reverse()

주어진 항목열을 앞뒤로 반전시켜주는 함수이다. 단순히 역방향의 순회를 목적으로 이 함수를 사용하는 것은 권장하지 않는다. 그런 경우는 역방향 반복자를 이용하여 순회하는 것이 바람직하다.
양방향 반복자를 요구하는 함수이기 때문에 forward_list의 항목열에 대해서는 이 함수를 사용할 수 없고 forward_list는 메서드로서 reverse를 제공한다.

---

7) next_permutation 함수, prev_permutation()

주어진 항목열을, 그 항목들로 생성 가능한 다음 순열 조합 또는 이전 순열 조합으로 변환해준다. 양방향 반복자를 요구하기 때문에 forward_list는 사용할 수 없다.
bool 타입의 반환값이 있는데 순열 조합의 마지막에 도달한 경우 false를 반환하고 그렇지 않다면 true를 반환한다.
만약 주어진 항목열의 조합(combination)에서 가능한 모든 순열을 순회하고 싶다면 항목열을 정렬하는 선행 작업이 필요하다.

#include <algorithm>
#include <string>
#include <iostream>

using namespace std;

int main()
{
	string s = "aba";
    sort(s.begin(), s.end()); //정렬 안하면 aab 순열이 제외됨
    do {
    	cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));
    //s == "aab"
}

---

3. 집합 알고리즘

집합 알고리즘은 정렬된 상태의 항목열을 대상으로 한다. 따라서 비순차 연관 컨테이너에서는 올바르게 동작하지 않는다. 집합 알고리즘에는 총 다섯 가지가 있다.

1) includes()

부분 집합 여부를 판정하는 함수이다.

vector<int> v {3, 4, 2, 1, 5};
set<int> s {5, 2, 1, 4};
sort(v.begin(), v.end()); //v는 정렬해야하지만 s는 내부적으로 이미 정렬된 컨테이너이므로 불필요
cout << boolalpha << includes(v.begin(), v.end(), s.begin(), s.end()); //true (s가 v의 부분집합임)

---

2) set_union()

합집합을 구해 결과 집합에 담아 준다. 결과 집합의 크기는 미리 확보되어 있어야 한다. 즉, 결과 집합의 크기는 두 집합의 크기 합과 같도록 준비해야 한다.

vector<int> v1 {1, 3, 5, 7, 9}, 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 (auto x : result)
	cout << x << ' ';
cout << endl;
// 1 2 3 4 5 7 9

---

3) set_intersection()

교집합을 구해 결과 집합에 담아 준다. 결과 집합의 크기는 미리 확보되어 있어야 한다. 즉, 결과 집합의 크기는 두 집합 중 큰 것과 같도록 준비해야 한다.

vector<int> v1 {1, 3, 5, 7, 9}, 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 (auto x : result)
	cout << x << ' ';
cout << endl;
// 1 3 5

---

4) set_difference()

차집합을 구해 결과 집합에 담아 준다. 결과 집합의 크기는 미리 확보되어 있어야 한다. 즉, 결과 집합의 크기는 첫 번째 집합의 크기와 같도록 준비해야 한다.

vector<int> v1 {1, 3, 5, 7, 9}, 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 (auto x : result)
	cout << x << ' ';
cout << endl;
// 7 9

---

5) set_symmetric_difference()

대칭 차집합을 구해 결과 집합에 담아 준다. 결과 집합의 크기는 미리 확보되어 있어야 한다. 즉, 결과 집합의 크기는 두 집합의 크기 합과 같도록 준비해야 한다.

vector<int> v1 {1, 3, 5, 7, 9}, v2 {1, 2, 3, 4, 5}, result(10);
auto eIter = set_symmertic_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
result.erase(eIter, result.end());
for (auto x : result)
	cout << x << ' ';
cout << endl;
// 2 4 7 9