21xrx.com
2025-03-31 03:49:23 Monday
文章检索 我的文章 写文章
C++中unique函数详解
2023-06-23 22:43:36 深夜i     12     0
C++ unique函数

在C++中,STL(Standard Template Library)中的unique函数是一种十分常用的算法函数。它可以帮助程序员在处理连续的元素时,快速地去重并返回一个指向新序列的迭代器。

unique函数的语法如下:

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

其中,参数first、last用于指定区间的头和尾,即对[first, last)内的元素进行去重。

unique函数的返回值是一个指向最后一个非重复元素的迭代器。

这里我们着重对unique函数的使用方法和内部实现进行详细解析。

## 使用方法

在实际使用中,unique函数在去重前需要将待去重的序列进行排序,以便相邻元素的比较。因此,在使用unique函数前,一般需要先调用sort或者stable_sort等排序函数。

以下是unique函数的完整使用示例:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
  vector<int> v = 1;
  sort(v.begin(), v.end());
  auto last = unique(v.begin(), v.end());
  v.erase(last, v.end());
  for (auto& e : v)
    cout << e << " ";
  
  cout << endl;
  return 0;
}

在上述示例中,首先将vector v进行了排序,然后调用unique函数对v进行去重,并返回一个指向最后一个非重复元素的迭代器。最后再通过vector的erase函数,将该迭代器之后的所有元素删除。

输出结果为:1 2 3 4 5。

## 内部实现

在实际使用中,unique函数的内部实现也十分关键。一般情况下,unique函数会利用两个指针进行去重。它会将当前指针指向的元素与上一个指针指向的元素进行比较,如果相同则当前指针继续向后移动;如果不同,则将上一个指针的下一位赋值为当前指针所指向的元素,并将当前指针向后移动。

以下是unique函数的简化版实现:

template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last)
{
  if (first == last)
    return last;
  ForwardIterator result = first;
  while (++first != last) {
    if (*result != *first) {
      *(++result) = *first;
    }
  }
  return ++result;
}

在上述代码中,result指向上一个指针,first指向当前指针。当两者所指向的元素不同时,result会向后移动,并将当前指针指向的元素赋给它;否则,当前指针会继续向后移动。

unique函数的时间复杂度为O(n),空间复杂度为O(1)。在实际使用中,unique函数可以方便地进行去重操作,极大提升程序的效率。

  
  

评论区

请求出错了