C++ STL算法系列4---unique , unique_copy函数

简介:  一.unique函数 类属性算法unique的作用是从输入序列中“删除”所有相邻的重复元素。 该算法删除相邻的重复元素,然后重新排列输入范围内的元素,并且返回一个迭代器(容器的长度没变,只是元素顺序改变了),表示无重复的值范围得结束。

 

 一.unique函数

类属性算法unique的作用是从输入序列中“删除”所有相邻的重复元素

该算法删除相邻的重复元素,然后重新排列输入范围内的元素,并且返回一个迭代器(容器的长度没变,只是元素顺序改变了),表示无重复的值范围得结束。

 1 // sort words alphabetically so we can find the duplicates 
 2 sort(words.begin(), words.end()); 
 3      /* eliminate duplicate words: 
 4       * unique reorders words so that each word appears once in the 
 5       *    front portion of words and returns an iterator one past the 
 6 unique range; 
 7       * erase uses a vector operation to remove the nonunique elements 
 8       */ 
 9  vector<string>::iterator end_unique =  unique(words.begin(), words.end()); 
10  words.erase(end_unique, words.end());
在STL中unique函数是一个去重函数, unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除,是把重复的元素移到后面去了,然后依然保存到了原数组中,然后 返回去重后最后一个元素的地址,因为unique去除的是相邻的重复元素,所以一般用之前都会要排一下序。

若调用sort后,vector的对象的元素按次序排列如下:

sort  jumps  over quick  red  red  slow  the  the turtle

则调用unique后,vector中存储的内容是:

 

 

 

 

 

 

注意,words的大小并没有改变,依然保存着10个元素;只是这些元素的顺序改变了。调用unique“删除”了相邻的重复值。给“删除”加上引号是因为unique实际上并没有删除任何元素,而是将无重复的元素复制到序列的前段,从而覆盖相邻的重复元素。unique返回的迭代器指向超出无重复的元素范围末端的下一个位置。

注意:算法不直接修改容器的大小。如果需要添加或删除元素,则必须使用容器操作。

example:

 

 1 #include <iostream>
 2 #include <cassert>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <string>
 6 #include <iterator>
 7  using namespace std;
 8 
 9  int main()
10 {
11     //cout<<"Illustrating the generic unique algorithm."<<endl;
12     const int N=11;
13     int array1[N]={1,2,0,3,3,0,7,7,7,0,8};
14     vector<int> vector1;
15     for (int i=0;i<N;++i)
16         vector1.push_back(array1[i]);
17 
18     vector<int>::iterator new_end;
19     new_end=unique(vector1.begin(),vector1.end());    //"删除"相邻的重复元素
20     assert(vector1.size()==N);
21 
22     vector1.erase(new_end,vector1.end());  //删除(真正的删除)重复的元素
23     copy(vector1.begin(),vector1.end(),ostream_iterator<int>(cout," "));
24     cout<<endl;
25 
26     return 0;
27 }

 

运行结果为:

 

 

二、unique_copy函数

算法标准库定义了一个名为unique_copy的函数,其操作类似于unique。

唯一的区别在于:前者接受第三个迭代器实参,用于指定复制不重复元素的目标序列。

unique_copy根据字面意思就是去除重复元素再执行copy运算。

编写程序使用unique_copy将一个list对象中不重复的元素赋值到一个空的vector对象中。

 1 //使用unique_copy算法
 2 //将一个list对象中不重复的元素赋值到一个空的vector对象中
 3 #include<iostream>
 4 #include<list>
 5 #include<vector>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 int main()
10 {
11     int ia[7] = {5 , 2 , 2 , 2 , 100 , 5 , 2};
12     list<int> ilst(ia , ia + 7);
13     vector<int> ivec;
14 
15     //将list对象ilst中不重复的元素复制到空的vector对象ivec中
16     //sort(ilst.begin() , ilst.end());  //不能用此种排序,会报错
17     ilst.sort();  //在进行复制之前要先排序,切记
18     unique_copy(ilst.begin() , ilst.end() , back_inserter(ivec));
19 
20     //输出vector容器
21     cout<<"vector: "<<endl;
22     for(vector<int>::iterator iter = ivec.begin() ; iter != ivec.end() ; ++iter)
23         cout<<*iter<<" ";
24     cout<<endl;
25 
26     return 0;
27 }

 假如

list<int> ilst(ia , ia + 7);
改为:vector<int> ilst(ia , ia + 7);

则排序时可用:

sort(ilst.begin() , ilst.end());

 这里要注意list和vector的排序用什么方法。

《Effective STL》里这些话可能有用处:
item 31
  
  “我们总结一下你的排序选择:
   ● 如果你需要在vector、string、deque或数组上进行完全排序,你可以使用sort或stable_sort。
   ● 如果你有一个vector、string、deque或数组,你只需要排序前n个元素,应该用partial_sort
   ● 如果你有一个vector、string、deque或数组,你需要鉴别出第n个元素或你需要鉴别出最前的n个元素,而不用知道它们的顺序,nth_element是你应该注意和调用的。
   ● 如果你需要把标准序列容器的元素或数组分隔为满足和不满足某个标准,你大概就要找partition或stable_partition。
   ● 如果你的数据是在list中,你可以直接使用partition和stable_partition,你可以使用list的sort来代替sort和stable_sort。如果你需要partial_sort或nth_element提供的效果,你就必须间接完成这个任务,但正如我在上面勾画的,会有很多选择。
  
  另外,你可以通过把数据放在标准关联容器中的方法以保持在任何时候东西都有序。你也可能会考虑标准非STL容器priority_queue,它也可以总是保持它的元素有序。


微信公众号: 猿人谷
如果您认为阅读这篇博客让您有些收获,不妨点击一下右下角的【推荐】
如果您希望与我交流互动,欢迎关注微信公众号
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。

目录
打赏
0
0
0
0
30
分享
相关文章
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
71 1
Windows共享文件:探秘C++实现的B树索引算法奇境
在数字化时代,Windows共享文件的高效管理至关重要。B树算法以其自平衡多路搜索特性,在文件索引与存储优化中表现出色。本文探讨B树在Windows共享文件中的应用,通过C++实现具体代码,展示其构建文件索引、优化数据存储的能力,提升文件检索效率。B树通过减少磁盘I/O操作,确保查询高效,为企业和个人提供流畅的文件共享体验。
解读 C++ 助力的局域网监控电脑网络连接算法
本文探讨了使用C++语言实现局域网监控电脑中网络连接监控的算法。通过将局域网的拓扑结构建模为图(Graph)数据结构,每台电脑作为顶点,网络连接作为边,可高效管理与监控动态变化的网络连接。文章展示了基于深度优先搜索(DFS)的连通性检测算法,用于判断两节点间是否存在路径,助力故障排查与流量优化。C++的高效性能结合图算法,为保障网络秩序与信息安全提供了坚实基础,未来可进一步优化以应对无线网络等新挑战。
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
110 2
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
86 17
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
219 73
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
35 0
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
43 0
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
81 4
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问