C++ STL unique和unique_copy 使用说明

1. 说明

1.1 std::unique()

std::unique()是C++17引入，用于去除相邻的重复元素。

比较是否相等的函数，默认是使用operator==，可以自定义比较函数。

所以常用的函数签名有如下两种：

1. 使用默认的比较函数operator==

template< class ForwardIt >
ForwardIt unique( ForwardIt first, ForwardIt last );

2. 使用自定义的比较函数

template< class ForwardIt, class BinaryPredicate >
ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );

其中BinaryPredicate p为自定义的比较函数。

前两个参数定义了作用范围[first, last)，只在作用范围内去重。
而且这个去重只是跟相邻的元素比，所以如果要整体去重，先对数组进行个排序。

函数有返回值，返回值是指向范围新结尾的迭代器。新结尾的老结尾之间的元素为不确定值，一般为原来元素的内容，尽量不要去使用。

1.2 std::unique_copy()

std::unique_copy()相对于std::unique()多了个copy操作，用于去除相邻的重复元素后，把元素复制到结果容器中去。
所以函数参数也比std::unique()多了结果容器的参数。如下：

1. 使用默认的比较函数operator==

template< class InputIt, class OutputIt >
OutputIt unique_copy( InputIt first, InputIt last, OutputIt d_first );

其中OutputIt d_first指定了结果容器的起始迭代器。

2. 使用自定义的比较函数

template< class InputIt, class OutputIt, class BinaryPredicate >
OutputIt unique_copy( InputIt first, InputIt last, OutputIt d_first, BinaryPredicate p );

其中BinaryPredicate p为自定义的比较函数。

从范围 [first, last) 复制元素到始于 d_first 的另一范围，使得无连续的相等元素。

注意点：

1. 去重只是跟相邻的元素比，所以如果要整体去重，先对数组进行个排序。
2. 放入的结果容器要有足够的容量赋值新元素，或者使用std::back_inserter()进行插入新元素
3. std::unique_copy()不会破坏原先数组的顺序

2. 头文件

#include <algorithm>

3. 例子

3.1 std::unique 使用默认比较函数

#include <iostream>     // std::cout
#include <algorithm>    // std::unique
#include <vector>       // std::vector


int main()
{
    std::vector<int> nums = { 10,20,20,20,30,30,20,20,10 };  // 10 20 20 20 30 30 20 20 10

    // using default comparison:
    std::vector<int>::iterator last;
    last = std::unique(nums.begin(), nums.end());   // 10 20 30 20 10 x x x x
                                                    //                ^
    nums.erase(last, nums.end());                   // 10 20 30 20 10

    // print out content:
    std::cout << "nums contains:";
    for (int num : nums) {
        std::cout << ' ' << num;
    }        
    std::cout << std::endl;

    return 0;
}

输出结果如同右边注释所示。

3.2 std::unique 使用默认自定义函数

#include <iostream>     // std::cout
#include <algorithm>    // std::unique
#include <vector>       // std::vector

int main()
{
    std::vector<int> nums = { 10,20,20,20,30,30,20,20,10 };  // 10 20 20 20 30 30 20 20 10

    // using custom comparison function:
    auto mycompare = [](int i, int j) { return (i == j); };
    std::vector<int>::iterator last;
    last = std::unique(nums.begin(), nums.end(), mycompare);   // 10 20 30 20 10 x x x x
                                                               //                ^
    nums.erase(last, nums.end());                              // 10 20 30 20 10

    // print out content:
    std::cout << "nums contains:";
    for (int num : nums) {
        std::cout << ' ' << num;
    }        
    std::cout << std::endl;

    return 0;
}

自定义比较函数可以使用上面的lambda表达式，也可以如下定义：

bool myfunction (int i, int j) {
  return (i==j);
}

输出结果如同右边注释所示。

3.3 std::unique 在类中的使用

比如加入立方体有边长和重量属性，想要去掉边长相同的相邻元素，操作如下：

#include <iostream>     // std::cout
#include <algorithm>    // std::unique_copy
#include <vector>       // std::vector

class Cube {
public:
    Cube(int length, int weight): length_(length), weight_(weight){}
    
    // custom comparison function
    bool operator==(const Cube& other) const {
        return (length_ == (other.length_));
    }

    int length_;
    int weight_;
};

int main()
{
    std::vector<Cube> cubes;  
    cubes.push_back(Cube(10, 300));
    cubes.push_back(Cube(10, 200));
    cubes.push_back(Cube(20, 300));
    cubes.push_back(Cube(20, 200));
    cubes.push_back(Cube(30, 300));
    cubes.push_back(Cube(30, 200));

    std::vector<Cube>::iterator last;
    last = std::unique(cubes.begin(), cubes.end());   
                                                      
    cubes.erase(last, cubes.end());

    // print out content:
    std::cout << "cubes contains:" << std::endl;
    for (Cube cube : cubes) {
        std::cout << "length: " << cube.length_ << "\tweight: " << cube.weight_;
        std::cout << std::endl;
    }        

    return 0;
}

输出结果如下：

cubes contains:
length: 10      weight: 300
length: 20      weight: 300
length: 30      weight: 300

在类中自定义bool operator==(const Cube& other) const函数，用于判断是否是相同元素

3.3 std::unique_copy 使用默认比较函数

#include <iostream>     // std::cout
#include <algorithm>    // std::unique_copy
#include <vector>       // std::vector

int main()
{
    std::vector<int> nums_ori = { 10,20,20,20,30,30,20,20,10 };  // 10 20 20 20 30 30 20 20 10
    std::vector<int> nums_new(9);                                // 0  0  0  0  0  0  0  0  0

    // using default comparison:
    std::unique_copy(nums_ori.begin(), nums_ori.end(), nums_new.begin());   
    
    std::cout << "nums_ori contains:\t";
    for (int num : nums_ori) {
        std::cout << ' ' << num;
    }
    std::cout << std::endl;

    std::cout << "nums_new contains:\t";
    for (int num : nums_new) {
        std::cout << ' ' << num;
    }
    std::cout << std::endl;

    return 0;
}

输出结果如下：

nums_ori contains:       10 20 20 20 30 30 20 20 10
nums_new contains:       10 20 30 20 10 0 0 0 0

从结果容器nums_new的起始位置开始写入结果，不会破坏原先数组nums_ori

但是上面要先结果容器nums_new有足够的容量，否则数组越界。
这时可以使用std::back_inserter()来避免预先分配容量，用多少就实际插入多少，可参考 https://www.jianshu.com/p/6862a79eba0a

#include <iostream>     // std::cout
#include <algorithm>    // std::unique_copy
#include <vector>       // std::vector
#include <iterator>     // std::back_inserter

int main()
{
    std::vector<int> nums_ori = { 10,20,20,20,30,30,20,20,10 };  // 10 20 20 20 30 30 20 20 10
    std::vector<int> nums_new;  

    // using default comparison:
    std::unique_copy(nums_ori.begin(), nums_ori.end(), std::back_inserter(nums_new));
    
    std::cout << "nums_ori contains:\t";
    for (int num : nums_ori) {
        std::cout << ' ' << num;
    }
    std::cout << std::endl;

    std::cout << "nums_new contains:\t";
    for (int num : nums_new) {
        std::cout << ' ' << num;
    }
    std::cout << std::endl;

    return 0;
}

输出结果如下：

nums_ori contains:       10 20 20 20 30 30 20 20 10
nums_new contains:       10 20 30 20 10

3.3 std::unique_copy 使用自定义比较函数

#include <iostream>     // std::cout
#include <algorithm>    // std::unique_copy
#include <vector>       // std::vector
#include <iterator>     // std::back_inserter

int main()
{
    std::vector<int> nums_ori = { 10,20,20,20,30,30,20,20,10 };  // 10 20 20 20 30 30 20 20 10
    std::vector<int> nums_new;  

    // using custom comparison function:
    auto mycompare = [](int i, int j) { return (i == j); };
    std::unique_copy(nums_ori.begin(), nums_ori.end(), std::back_inserter(nums_new), mycompare);
    
    std::cout << "nums_ori contains:\t";
    for (int num : nums_ori) {
        std::cout << ' ' << num;
    }
    std::cout << std::endl;

    std::cout << "nums_new contains:\t";
    for (int num : nums_new) {
        std::cout << ' ' << num;
    }
    std::cout << std::endl;

    return 0;
}

输出结果如下：

nums_ori contains:       10 20 20 20 30 30 20 20 10
nums_new contains:       10 20 30 20 10

自定义比较函数可以使用上面的lambda表达式，也可以如下定义：

bool myfunction (int i, int j) {
  return (i==j);
}

4. 参考

http://www.cplusplus.com/reference/algorithm/unique/
https://zh.cppreference.com/w/cpp/algorithm/unique
http://www.cplusplus.com/reference/algorithm/unique_copy/
https://zh.cppreference.com/w/cpp/algorithm/unique_copy