C++标准库

竟无语凝噎

RT

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

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

为什么？

qq1242009750

因为算法是把内存中的 数据进行排序，因此在排序的过程中可能会覆盖一些元素而不是真正的删除，当然啦，算法也不可能添加元素的(毕竟算法只是起到一个排序的作用)。

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

PS： 这里的算法是指 排序算法。

行客

你在学习STL是吗？

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

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

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

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

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

C++标准库std中提供了一种“智能指针类”名为"auto_ptr"，先看以下的代码：

void f()
{
        int *p=new int(42);
        ////////此处发生异常////
        delete p;
}

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

#include<memory>//auto_ptr的头文件
void f()
{
        auto_ptr<int>p(new int (42));
}

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

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

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

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

为什么这样说呢？我们举个样例来说明原因。

#include<iostream>
#include<algorithm>//用到find函数
#include<vector>
using namespace std;
int main()
{
        vector<int>vec;
        int i;
        for(i=0;i<10;i++)
        {
                vec.push_back(i);
        }
        if(vec.end()!=find(vec.begin(),vec.end(),7))
        {
                cout<<"find!"<<endl;
        }
        else
        {
                cout<<"not find!"<<endl;
        }
        system("pause");
        return 0;
}

上述代码中。值得注意的是用到的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个元素，为什么“此位置之后的元素仍然存在”。

如有不明白的地方，请继续跟帖。

行客

我们再来看一下unique：

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

我们来看其中一个unique函数的函数原型，如下：

iterator unique(iterator it_1,iterator it_2);

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

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

关于这个问题，http://www.cplusplus.com/reference/algorithm/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))  // or: if (!pred(*result,*first)) for version (2)
      *(++result)=*first;
  }
  return ++result;
}

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

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

注：

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

2.一定不要忘记的是，unique函数在使用前需要对容器中的元素进行排序(当然不是必须的，但我们绝大数情况下需要这么做)，由于本例中的元素已经是排好序的，所以此处我没排序，但实际使用中不要忘记。

行客

请注意有两个回复。

竟无语凝噎

行客 发表于 2019-2-18 17:27
请注意有两个回复。

还没看到那么深， 如果看到了理解了在给您回复或取为最佳。

竟无语凝噎

行客 发表于 2019-2-18 17:27
请注意有两个回复。

我看的是C++primer  是STL 整个看完在请教您