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

코드를 작성하다 보면, 두 배열을 비교해야 하는 순간이 찾아온다. 두 배열의 원소가 같은 값인지, 아니면 다른 값인지 하여서 하나씩 비교해야 할 때, 우리는 다음과 같이 작성한다.

 

vector<int> 형인 두 배열 vec, vec2를 비교한다고 하고, 두 배열의 길이는 같다고 가정하자.

 

bool is_equal = true;
for (int i = 0; i < (int)vec.size(); i++) {
    if (vec[i] != vec2[i]) {
        is_equal = false;
        break;
    }
}

 

이런! 단순 비교인데 코드를 7줄이니 먹는다는게 불편하다. 이를 한 번에 해결할 수 있는 함수 equal을 소개하도록 하겠다.

 

1. equal

(※ https://www.cplusplus.com/reference/algorithm/equal/ 에서 함수에 대한 정보를 확인할 수 있다.)

 

C++의 알고리즘 관련 여러 함수들이 담긴 헤더 <algorithm.h>에서의 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;
}

 

쉽게 말해, 두 배열을 iterator를 이용해 비교해주는 함수라 생각하면 쉽다.

 

2.  예제 코드

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

 

위에서 7줄이나 된 코드를 단 한 줄로 바꿀 수 있다.

 

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

 

정말 너무나도 간단하게 7줄이나 되는 코드를 한 줄로 압축하였다. 이처럼 특정 배열이나 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!"
}

 

실제 코드를 실행하여보면 "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!"
}

 

실제 코드를 실행하여보면 "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!"
}

 

실제 코드를 실행하여보면 "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$는 비교 연산의 시간 복잡도)라고 쓸 수 있다.

 

도움이 되었다면 지나가는 길에 하트 하나 눌러주세요, 양질의 글을 쓰는데 하나의 동기부여가 됩니다😍

지적이나 오타 수정 댓글 환영합니다!!