큰 STL 알고리즘 튜토리얼: 시퀀스 수정 작업 - 다른 요소를 얻는 방법

본문은 최초로 나의 blog에 발표되었다.최신 기사를 받고 싶으면 sign up to my newsletter으로 오세요.
the big STL algorithm tutorial의 다음 섹션에서는 컨테이너의 고유한 요소를 가져오는 데 도움이 되는 두 가지 수정 시퀀스 알고리즘을 살펴보겠습니다.

unique

unique_copy

우리 시작합시다!
uniqueunique--사실 unique_copy--두 가지 알고리즘으로 실현할 수 있다. 마치 remove과 remove_if은 두 가지 다른 알고리즘과 같다.
일치성은 <algortihms> 헤더의 가장 강력한 기능이 아니다.
이런 상황에서 우리는 단지 두 개의 단독 재부팅 서명을 가지고 있을 뿐이지만, 우리는 이 알고리즘의 목표를 계속할 것이다.unique은 컨테이너에서 모든 중복 요소를 제거합니다.하지만 전제는 연속적이다.이 경우 같은 두 개의 요소가 서로 인접하지 않고 보존되어야 합니다.검사를 해봐야겠어요.
이 두 가지 상황에서 되돌아오는 값은 모두 같다. 이것은 용기의 새 end()을 가리키며, 복제된 용기가 새 단위로 옮겨진 후.
In the first example, 우리는 더욱 간단한 서명을 사용할 것입니다. 그 중에서 우리는 하나의 입력 범위만 전달할 것입니다. 이 범위는 지향 범위에서 시작하고 끝나는 두 개의 교체기로 정의됩니다.

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


int main()
{
    std::vector<int> numbers{9, 1, 3, 3, 3, 5, 1, 6, 1};
    std::cout << "Original values: " << std::endl;
    std::for_each(numbers.begin(), numbers.end(), [](auto i) {std::cout << i << " ";});
    std::cout << std::endl;
    std::cout << std::endl;
    
    std::cout << "size: " << numbers.size() << ", capacity: " << numbers.capacity() << std::endl;
    auto oldEnd = numbers.end();
    auto newEnd = std::unique(numbers.begin(), numbers.end());
    std::cout << "same values are only removed if they are next to each other:" << std::endl;
    std::for_each(numbers.begin(), newEnd, [](auto i) {std::cout << i << " ";});
    std::cout << std::endl;
    std::cout << std::endl;
    
    std::cout << std::boolalpha << "oldEnd == newEnd? :" << (oldEnd == newEnd) << std::endl;
    std::cout << "In fact, the end hasn't changed. oldEnd == numbers.end(): " << (oldEnd == numbers.end()) << std::endl;
    std::cout << "number of elements removed: " << std::distance(newEnd, oldEnd) << std::endl;
    std::cout << "Though if you use the end, stranfe results are there..." << std::endl;
    std::for_each(numbers.begin(), oldEnd, [](auto i) {std::cout << i << " ";});
    std::cout << std::endl;
    std::cout << std::endl;
    
    std::cout << "size: " << numbers.size() << ", capacity: " << numbers.capacity() << ", these values haven't changed" << std::endl;
    numbers.erase(newEnd, oldEnd);
    numbers.shrink_to_fit();
    std::cout << "size: " << numbers.size() << ", capacity: " << numbers.capacity() << ", we should erase what is between the return value of unique() and the old end" << std::endl;
}

벡터의 끝인 changed numbers.end()이 std::unique()을 호출하는 전후가 같지 않음에도 불구하고 되돌아오는 교체기와 (원시) 단점 사이의 내용이 무의미해진다는 흥미로운 사실을 알 수 있습니다.우리도 그것을 사용하는 것은 위험하다고 말할 수 있다.
사실 STL이 어떻게 디자인되었는지 우리에게 일깨워 준다면 매우 의미가 있다.알고리즘은 집합에서 실행되지 않고 교체기에서 실행된다.std::unique은 요소를 서로 이동하지만 기본 집합에서 어떤 내용도 제거하지 않습니다.이것은 std::remove을 사용하여 요소를 삭제할 수 없는 이유와 완전히 같지만 반드시 remove-erase idiom을 사용해야 한다.
그래서 만약에 우리가 이 지역 unique 알고리즘을 사용하고 싶다면 우리는 이 용기를 하나의 전체로 사용해서는 안 된다고 말하고 싶다.교체기 이외의 요소를 삭제하거나 사용하지 마십시오.
만약 우리가 원시 용기를 다시 사용하고 싶다면 std::unique_copy을 사용하는 것이 가장 좋다. 그러나 그 전에 unique의 다른 버전을 보면 우리는 요소의 비교 방식을 사용자 정의할 수 있다.
선택할 수 있는 세 번째 매개 변수로서 우리는 이진 술어를 전입할 수 있다.더 쉽게 이해할 수 있는 영어로 함수, 함수 대상, lambda function을 입력할 수 있으며, 두 개의 매개 변수 (집합 중 두 요소가 인접한 것) 를 가지고 브리 값을 되돌려줄 수 있다.만약 두 요소가 같은 것으로 여겨진다면, 술어는true를 되돌려야 하고, 그렇지 않으면false를 되돌려야 한다.
다음은 간단한 예이다.

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

struct Person {
    long id;
    std::string name;
    std::string phoneNumber;
};

int main()
{
    std::vector<Person> people {{1, "John D Smith", "555-1234"}, {1, "John David Smith", "784-1234"}, {2, "Adam Jones", "555-7894"}};
    auto it = std::unique(people.begin(), people.end(), [](auto lhs, auto rhs){ return lhs.id == rhs.id; });
    std::for_each(people.begin(), it, [](auto i) {std::cout << i.name << " " << std::endl;});
}

위의 예에서 우리는 서로 다른 Person 대상이 있는데, 그것들은 같은 물리적 실체를 인용할 수 있다.그래서 이름이 다를 수도 있고, 전화번호가 다를 수도 있지만, 두 사람을 같은 사람으로 보고 싶다.이 특정한 예에서 우리는 id을 사용할 수 있고 우리는 id 필드를 바탕으로 비교할 수 있다.
그렇지 않으면 두 개의 서로 다른 서명 사이에는 차이가 없다.

unique_copy

std::unique_copy의 작업 원리는 std::unique과 유사하지만 후자가 원시 용기에서 값을 이동할 때 전자는 보류할 값을 목표 용기에 복제한다.
다른 알고리즘에서 알 수 있듯이 목표 용기는 입력한 후에 전달된다. 입력은 한 쌍의 연산자로 표시되지만 목표는 한 개의 연산자로만 표시된다.이 목표의 집합은 모든 원소를 수용할 수 있도록 충분해야 한다.가장 간단한 방법은 back_inserter을 사용하는 것이다.
반환값은 std::unique과 같고 후자는 교체기로서 마지막으로 복제된 원소의 정후방을 가리킨다.이게 의미가 있나요?네.첫째, 이것은 unique과 일치하고, 둘째, 목표 전달 삽입기 교체기로서 유일한 옵션이 아니다.아마도 모든 값을 위해 충분한 목표 집합을 만들었을 것입니다. 목표에 약간의 빈 용량이 있을 것입니다.이런 상황에서 자유용량은 제로 구조원소를 가리킨다.이 경우 복사 값의 끝 위치를 보는 것이 유용하다.
우리 예를 하나 봅시다.

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

int main()
{
    std::vector<int> numbers{9, 1, 3, 3, 3, 5, 1, 6, 1};
    std::vector<int> uniqueNumbers(numbers.size());
    
    auto it = std::unique_copy(numbers.begin(), numbers.end(), uniqueNumbers.begin());

    std::cout << "Content of uniqueNumbers: " << std::endl;
    std::for_each(uniqueNumbers.begin(), uniqueNumbers.end(), [](auto i) {std::cout << i << " ";});
    std::cout << std::endl << std::endl;
    
    std::cout << "Content of uniqueNumbers until the returned iterator: " << std::endl;
    std::for_each(uniqueNumbers.begin(), it, [](auto i) {std::cout << i << " ";});
    std::cout << std::endl;
}

위의 예에서 우리는 연속 중복항을 가진 원시 벡터의 크기를 사용하여 목표 벡터를 초기화합니다.따라서 unique_copy을 호출한 후에도 목표 벡터에 초기화 요소가 없습니다.
비록 우리가 unique_copy이라고 부르지만 복제된 요소가 반드시 유일한 것은 아니다. 왜냐하면 인접한 복사본만 삭제되었기 때문이다. unique* 알고리즘의 계약이 약속한 바와 같다.

결론
오늘 우리는 unique과 unique_copy을 배웠는데 이 두 가지 알고리즘은 중복값이 인접한 상황에서 범위에서 중복항목을 삭제할 수 있다.이것은 그들의 가장 큰 수확이다. 중복된 요소는 서로 붙어 있어야 하지만, 좋은 문서 기록이 있어야 한다.
다음에 우리는 우리에게 무작위적인 알고리즘을 가져다 줄 것이다.기대해주세요!
다음 C++ 면접을 준비하려면 Daily C++ Interview을 방문하세요!