[C++] 두 배열을 비교할 수 있는 함수 equal

1. equal

C++의 알고리즘 관련 여러 함수들이 담긴 헤더 에서의 equal 함수는 다음과 같은 두 가지 구조를 가진다.

1] equality - bool equal (InputIterator first1, InputIterator last1, InputIterator first2)

2] predicate - bool equal (InputIterator1 first1, InputIterator last1, InputIterator first2, BinaryPredicate pred)

 

equal은 쓰임에 따라 3개 혹은 4개의 인자를 받는다.

• InputIterator first1 : 비교할 첫 번째 배열이나 어떤 container 자료형의 시작부 혹은 포인터
• InputIterator last1: 비교할 첫 번째 배열이나 어떤 container 자료형의 끝부 혹은 포인터
• InputIterator first2 : 비교할 두 번쨰 배열이나 어떤 container 자료형의 시작부 혹은 포인터

만약 equal이 C++의 비교 우선순위에 따르지 않고 직접 연산자 == 를 재정의하였다면, 마지막에 하나의 인자를 추가한다.

• BinaryPredicate pred : 첫 번째 배열과 두 번째 배열을 각각 첫 번째 인자 / 두 번째 인자로 받아 같은 지 비교하는 함수. 본래 인자를 수정하지 않는 함수여야 하며, 함수 객체 혹은 함수의 포인터 모두 사용가능하다.
• Return Value : 연산자 == 혹은 pred의 반환값이 모두 true이면 True, 하나라도 false이면 False

구체적으로 이 함수의 역할을 말하자면, 범위 [first1, last1)의 iterator를 차례로 first2의 iterator와 비교하여모두 true를 반환하면 True를 반환하고, 아니라면 False를 반환한다.  first1의 iterator가 last1에 도달하면 비교를 멈춘다.

// 1. equality
template <class InputIterator1, class InputIterator2>
bool equal ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 ) {
  while (first1!=last1) {
    if (!(*first1 == *first2)) // equal
      return false;
 
    ++first1; ++first2;
  }
 
  return true;
}
 
// 2. predicate
template <class InputIterator1, class InputIterator2>
bool equal ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 ) {
  while (first1!=last1) {
    if (!pred(*first1,*first2)) // custom equal
      return false;
 
    ++first1; ++first2;
  }
 
  return true;
}

2.  예제 코드

먼저, equal - (1) equality를 활용하는 예시를 들어보자.

bool is_equal = equal(vec.begin(), vec.end(), vec2.begin());

 

이처럼 특정 배열이나 container 두 개를 비교할 때 유용할 때 사용할 수 있는 함수이다. 만약, 일부만 비교하고 싶다면 vec.end() 대신 vec.begin() + k로 작성하여도 가능하다.

 

다음으로, equal - (2) predicate를 사용할 때를 알아보자. 만약 C++ 기본 비교가 불가능하거나(struct...) 자료형끼리 직접 custom으로  배열을 비교하고 싶을 때는 다음과 같은 방법들이 있다.

예를 들어, x좌표, y좌표의 데이터를 담고있는 struct point를 담을 배열 두 개가 있을 때, 여러 가지 방법으로 equal을 사용할 수 있다.

2-1) Using lambda function

람다 함수를 사용하여 임시로 필요한 함수를 생성한다면 두 struct간 equal 여부를 알 수 있다.

#include <iostream>  // cout
#include <vector>    // vector
#include <algorithm> // equal
using namespace std;
 
struct point{
    int y, x;
    point(int _y, int _x) {
        this->y = _y;
        this->x = _x;
    }
};
 
int main() {
    vector<point> points1 = {{1, 2}, {2, 3}, {3, 4}};
    vector<point> points2 = {{1, 2}, {2, 3}, {3, 4}};
 
    if(equal(points1.begin(), points1.end(), points2.begin(), 
        [](point p1, point p2) { return p1.x==p2.x && p1.y == p2.y; })) {
            cout << "Equal!";        
    }
 
    // cout : "Equal!"
}

2-2) Using operator overriding

struct나 class 내의 '==' 연산자 오버라이딩을 통해 두 자료형을 비교할 수 있다. 이 경우 내부적으로 '==' 연산이 이루어지기에 따로 네 번째 인자를 넣어줄 필요가 없다.

#include <iostream>  // cout
#include <vector>    // vector
#include <algorithm> // equal
using namespace std;
 
struct point{
    int y, x;
    point(int _y, int _x) {
        this->y = _y;
        this->x = _x;
    }
    bool operator==(const point& other) {
        return x == other.x && y == other.y;
    }
};
 
 
int main() {
    vector<point> points1 = {{1, 2}, {2, 3}, {3, 4}};
    vector<point> points2 = {{1, 2}, {2, 3}, {3, 4}};
 
    bool is_equal = equal(points1.begin(), points1.end(), points2.begin());
 
    if(is_equal) {
        cout << "Equal!";        
    } else {
        cout << "Not Equal!";
    }
 
    // cout : "Equal!"
}

2-3) Using custom compare function

custom 비교 함수를 직접 작성하여 네 번째 인자로 넣어줄 수 있다. 이 경우 BinaryPredicate pred 자리에 직접 함수를 넣어주어야 한다.

#include <iostream>  // cout
#include <vector>    // vector
#include <algorithm> // equal
using namespace std;
 
struct point{
    int y, x;
    point(int _y, int _x) {
        this->y = _y;
        this->x = _x;
    }
};
 
inline bool cmp (const point& p1, const point& p2) {
    return p1.x == p2.x && p1.y == p2.y;
}
 
int main() {
    vector<point> points1 = {{1, 2}, {2, 3}, {3, 4}};
    vector<point> points2 = {{1, 2}, {2, 3}, {3, 4}};
 
    bool is_equal = equal(points1.begin(), points1.end(), points2.begin(), cmp);
 
    if(is_equal) {
        cout << "Equal!";        
    } else {
        cout << "Not Equal!";
    }
 
    // cout : "Equal!"
}

3) 주의할 점

equal 함수를 활용할 때는 고려해야하는 점이 몇 가지 있다.

 

1. equal 함수는 연산자 '=='를 활용하기에, '=='에서 문제가 발생할 수 있다.

예를 들어, 실수와 실수 간의 비교를 할 때, 부동 소수점 및 정밀도 문제로 인하여 잘못된 결과를 출력할 수 있다.

 

2. 위에 직접 equal을 구현할 코드를 살펴보면 while문이 (first1 != last1)이 조건으로 들어있다. 다른 말로, first1과 last1문이 동일하지 않을 때 까지 반복문이 실행된다는 의미이다.

 

이는 두 배열간 길이가 다를 때 문제가 발생할 수 있다.

다음 예제를 보자. 길이가 다른 두 vector<int> nums, num2를 비교할 때 equal을 활용하면 다음과 같다.

#include <iostream>  // cout
#include <vector>    // vector
#include <algorithm> // equal
using namespace std;
 
int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> num2 = {1, 2, 3};
 
    if (equal(nums.begin(), nums.end(), num2.begin())) {
        cout << "True";
    } else {
        cout << "False";
    }
 
    // cout : "False"
}

반환값으로 "False"가 발생했음을 알 수 있다. 이 경우 nums의 첫 원소부터 네 번째 원소까지 비교하였을 때 일치하지 않은 부분이 발생한 것이다.

 

이 경우 네 번째 원소에서 불일치가 발생하였지만, num2의 원소는 세 개이므로 nums의 네 번째 원소는 무엇과 비교한 것인가? num2 배열 안에서의 참조가 아닌 다른 어딘가에서의 참조를 한 것이다. 이처럼 undefined behavior가 발생할 수 있다.

반대로, num2에서 nums를 비교하여보면 다음과 같이 코드를 작성할 수 있다.

#include <iostream>  // cout
#include <vector>    // vector
#include <algorithm> // equal
using namespace std;
 
int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> num2 = {1, 2, 3, 4};
 
    if (equal(nums.begin(), nums.end(), num2.begin())) {
        cout << "True";
    } else {
        cout << "False";
    }
 
    // cout : "True"
}

위 코드에서 함수 equal은 nums의 첫 번째 원소부터 세 번째 원소까지 iterator가 움직인다. 이에 따른 num2는 같은 값을 가지므로 True를 반환한 모습을 확인할 수 있지만, num2의 네 번째 원소는 비교되지 않았기에 우리가 원하는 결과(False)를 얻을 수 없었다. 이처럼 equal을 사용할 때는 배열 길이 등 여러 예외 사항들을 미리 처리하거나, 배열의 길이가 같다는 보장 하에 사용하여야 한다.

 

equal 함수는 데이터 하나씩 배열에 접근하여 비교하기에 시간 복잡도는 배열의 길이인 O(n)을 가진다. 만약, predicate 템플릿 방식으로 비교를 한다면 O(nK) (K는 비교 연산의 시간 복잡도)라고 쓸 수 있다.

 

 

[C++] 두 배열을 함수 한 방에 아주 쉽게 비교하자! equal (tistory.com)