鱼C论坛

 找回密码
 立即注册

扫一扫,访问微社区

查看: 492|回复: 6

C++标准库

[复制链接]
最佳答案
2 
发表于 2019-2-18 09:42:05 | 显示全部楼层 |阅读模式
10鱼币
RT

关于note中: 标准库算法对迭代器而不是容器进行操作。因此算法不能(直接)添加或删除元素。

我的理解:
因为 : 标准库算法对迭代器而不是容器进行操作 ;
所以 : 算法不能(直接)添加或删除元素。

为什么?

A1B61682-7EC2-496d-B706-8B1B81966360.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
34 
发表于 2019-2-18 16:18:37 | 显示全部楼层
因为算法是把内存中的 数据进行排序,因此在排序的过程中可能会覆盖一些元素而不是真正的删除,当然啦,算法也不可能添加元素的(毕竟算法只是起到一个排序的作用)。

所以算法并不能删除或添加元素。

PS: 这里的算法是指 排序算法。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
67 
发表于 2019-2-18 17:03:09 | 显示全部楼层
本帖最后由 行客 于 2019-2-18 17:21 编辑

你在学习STL是吗?

首先你必须清楚为什么会出现迭代器。

“指针”对全部C/C++的程序员来说,一点都不陌生。

在接触到C语言中的malloc函数和C++中的new函数后。我们也知道这两个函数返回的都是一个指针。该指针指向我们所申请的一个“堆”。提到“堆”。就不得不想到“栈”。从C/C++程序设计的角度思考,“堆”和“栈”最大的差别是“栈”由系统自己主动分配而且自己主动回收,而“堆”则是由程序员手动申请。而且显示释放。假设程序员不显示释放“堆”,便会造成内存泄漏。内存泄漏的危害大家知道,严重时会导致系统崩溃。

既然“指针”的使用者一不小心就可能导致内存泄漏,那么我们怎样可以使得指针的使用变得更安全呢?从C++面向对象的角度分析,我们有没有可能将“指针”封装起来,使得用户不直接接触指针,而使用一个封装后的对象来替代指针的操作呢?

答案是显然的,“智能指针”(smart pointer)正解决这类问题,尤其是在防止内存泄漏方面做得很突出。

C++标准库std中提供了一种“智能指针类”名为"auto_ptr",先看以下的代码:
  1. void f()
  2. {
  3.         int *p=new int(42);
  4.         ////////此处发生异常////
  5.         delete p;
  6. }
复制代码


正如上面的代码所看到的。假设在两条语句中间发生异常,会导致指针p所指的那块内存泄漏。由于在执行delete之前发生异常,就不会自己主动释放堆。然而。假设使用auto_ptr对象取代常规指针,将会自己主动释放内存,由于编译器可以保证提前执行其析构函数。这样,我们就行将上述代码改为:

  1. #include<memory>//auto_ptr的头文件
  2. void f()
  3. {
  4.         auto_ptr<int>p(new int (42));
  5. }
复制代码


通过以上的分析。我们便对智能指针有了一定的了解:

迭代器iterator就是一种智能指针。它对原始指针进行了封装,而且提供一些等价于原始指针的操作,做到既方便又安全。

一提到STL,必需要立即想到其基本的6个组成部件,各自是:容器、算法、迭代器、仿函数、适配器和空间分配器。

迭代器是连接容器和算法的一种重要桥梁。

为什么这样说呢?我们举个样例来说明原因。
  1. #include<iostream>
  2. #include<algorithm>//用到find函数
  3. #include<vector>
  4. using namespace std;
  5. int main()
  6. {
  7.         vector<int>vec;
  8.         int i;
  9.         for(i=0;i<10;i++)
  10.         {
  11.                 vec.push_back(i);
  12.         }
  13.         if(vec.end()!=find(vec.begin(),vec.end(),7))
  14.         {
  15.                 cout<<"find!"<<endl;
  16.         }
  17.         else
  18.         {
  19.                 cout<<"not find!"<<endl;
  20.         }
  21.         system("pause");
  22.         return 0;
  23. }
复制代码

上述代码中。值得注意的是用到的find函数,find函数的函数原型为:template<class _InIt,class _Ty> _InIt find(_InIt _First, _InIt _last, const _Ty & _val),从find函数原型能够看出find函数是一个函数模板,函数的形參中前两个參数为_InIt。该參数是InputIterator的缩写。最后一个參数则是一个随意类型变量的引用。而我们的程序在使用find函数实。传入的实參为find(vec.begin(),vec.end(),7)。这样我们的形參迭代器就将算法find和容器vector联系起来了,从这个角度我们能够非常easy理解为什么说迭代器是算法和容器的联系的桥梁了。

所以:STL中,算法不直接操作容器,是间接通过迭代器来进行处理的。也就是,算法最终的操作结果是受迭代器的操作情况而确定的。因此,“标准库算法对迭代器而不是容器进行操作。因此算法不能(直接)添加或删除元素”。
但是,并非就完全不能实现添加或删除容器元素。只要迭代器的具体操作中实现了容器的添加或删除,就达到了算法操作的目的。

其实这里的Note本意是为了解释为什么容器还剩下10个元素,为什么“此位置之后的元素仍然存在”。

如有不明白的地方,请继续跟帖。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
67 
发表于 2019-2-18 17:26:44 | 显示全部楼层
我们再来看一下unique:

unique函数属于STL中比较常用函数,它的功能是元素去重。即”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除,并不是真的删除,而是指重复元素的位置被不重复的元素给占领了。(备注一下:由于它”删除”的是相邻的重复元素,所以在使用unique函数之前,一般都会将目标序列进行排序。)

我们来看其中一个unique函数的函数原型,如下:
  1. iterator unique(iterator it_1,iterator it_2);
复制代码

这种类型的unique函数是我们最常用的形式。其中这两个参数表示对容器中[it_1,it_2)范围的元素进行去重(注:区间是前闭后开,即不包含it_2所指的元素),返回值是一个迭代器,它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。

前面我们介绍了unique函数的功能和原型,那么,它到底是如何进行去重的呢?即“删除”的具体操作是怎样的呢?

关于这个问题,http://www.cplusplus.com/reference/algorithm/unique/给了我们一种解释,即unique函数是完全等价于下面这个函数的:

  1. template <class ForwardIterator>
  2.   ForwardIterator unique (ForwardIterator first, ForwardIterator last)
  3. {
  4.   if (first==last) return last;

  5.   ForwardIterator result = first;
  6.   while (++first != last)
  7.   {
  8.     if (!(*result == *first))  // or: if (!pred(*result,*first)) for version (2)
  9.       *(++result)=*first;
  10.   }
  11.   return ++result;
  12. }
复制代码


分析这段代码,我们可以知道,unique函数的去重过程实际上就是不停的把后面不重复的元素移到前面来,也可以说是用不重复的元素占领重复元素的位置。

同时,我们可以看到,容器中不重复的元素都移到了前面,至于后面的元素,实际上并没有改变。

注:

1.有很多文章说的是,unique去重的过程是将重复的元素移到容器的后面去,实际上这种说法并不正确,应该是把不重复的元素移到前面来。

2.一定不要忘记的是,unique函数在使用前需要对容器中的元素进行排序(当然不是必须的,但我们绝大数情况下需要这么做),由于本例中的元素已经是排好序的,所以此处我没排序,但实际使用中不要忘记。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
67 
发表于 2019-2-18 17:27:18 | 显示全部楼层
请注意有两个回复。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2 
 楼主| 发表于 2019-3-12 14:47:50 | 显示全部楼层
行客 发表于 2019-2-18 17:27
请注意有两个回复。

还没看到那么深, 如果看到了理解了在给您回复或取为最佳。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2 
 楼主| 发表于 2019-3-12 14:48:42 | 显示全部楼层
行客 发表于 2019-2-18 17:27
请注意有两个回复。

我看的是C++primer  是STL 整个看完在请教您
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2019-3-20 05:04

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表