STL实践与分析

--初窥算法【下】

一、写容器元素的算法

一些算法写入元素值。在使用这些算法写元素时一定要当心，必须确保算法所写的序列至少足以存储要写入的元素。

1、写入输入序列的元素

写入到输入序列的算法本质上是安全的——只会写入与指定输入范围数量相同的元素。

写入到输入序列的一个简单算法是fill函数：

    fill(iVec.begin(),iVec.end(),10);
    fill(iVec.begin(),iVec.begin()+iVec.size()/2,0);

fill带有一对迭代器形参，用于指定要写入的范围，而所写的值是它的第三个形参的副本。如果输入范围有效,则可安全写入。这个算法只会对输入范围内已存在的元素进行写入操作。

2、不检查写入操作的算法

fill_n函数带有的参数包括：一个迭代器、一个计数器以及一个值。fill_n函数假定对指定数量的元素做写操作是安全的。

    vector
  
    iVec;
    /**Error
    *但是编译器不会报错，
    *很可能导致严重的运行时错误
    */
    fill_n(iVec.begin(),10,0);

  

对于指定数目的元素做写入运算，或者写到目标迭代器的算法，都不检查目标的大小是否足以存储要写入的元素。

3、引入back_inserter

确保算法有足够的元素存储输出数据的一种方法是使用插入迭代器。在使用插入迭代器赋值时，会在容器中添加一个新元素，其值等于赋值运算的右操作数的值。

使用back_inserter的程序必须包含iterator头文件。

back_inserter函数是迭代器适配器。迭代器适配器使用一个对象作为实参,并生成一个适应其实参行为的新对象。在本例中,传递给back_inserter的实参是一个容器的引用。back_inserter生成一个绑定在该容器上的插入迭代器。在试图通过这个迭代器给元素赋值时,赋

值运算将调用push_back在容器中添加一个具有指定值的元素。使用 back_inserter可以生成一个指向fill_n写入目标的迭代器:

    vector
  
    iVec;
    fill_n(back_inserter(iVec),10,0);

  

效果相当于在vec上调用push_back,在vec末尾添加10个元素,每个元素的值都是0。

4、写入到目标迭代器的算法

第三类算法向目标迭代器写入未知个数的元素。如：copy函数。copy带有三个迭代器参数:头两个指定输入范围,第三个则指向目标序列的一个元素。传递给copy的目标序列必须至少要与输入范围一样大。假设ilst是一个存放int型数据的 list对象,可如下将它copy给一 个vector对象:

    vector
  
    iVec;
    copy(iList.begin(),iList.end(),back_inserter(iVec));

  

copy从输入范围中读取元素,然后将它们复制给目标ivec。

当然,这个例子的效率比较差，最好应该对新构造容器的初始化式:

    vector
  
    iVec(iList.begin(),iList.end());

  

5、算法的_copy版本

有些算法提供所谓的“复制(copying)”版本。这些算法对输入序列的元素做出处理,但不修改原来的元素,而是创建一个新序列存储元素的处理结果。

replace算法就是一个很好的例子。该算法对输入序列做读写操作,将序列中特定的值替换为新的值。该算法带有四个形参:一对指定输入范围的迭代器和两个值。每一个等于第一值的元素替换成第二个值。

    replace(iList.begin(),iList.end(),0,42);

如果不想改变原来的序列，则调用replace_copy函数。这个算法接受第三个迭代器实参，指定要保存调整后序列的位置：

vector
  
    iVec;    replace_copy(iList.begin(),iList.end(),back_inserter(iVec),0,42);

  

//P343 习题11.6
int main()
{
    int ia[] = {1,3,5,7,9,2,4,6,8,10};
    fill_n(ia,sizeof(ia)/sizeof(*ia),0);

    for (size_t index = 0;index != sizeof(ia)/sizeof(*ia); ++index)
    {
        cout << *(ia + index) << endl;
    }
}

//或者
int main()
{
    vector
  
    iVec;
    iVec.resize(10);
    fill_n(iVec.begin(),iVec.size(),0);

    for (vector
   
    ::iterator iter = iVec.begin(); iter != iVec.end(); ++iter) { cout << *iter << endl; } } 
   
  

二、对容器元素重新排序的算法

问题：

我们要分析一组儿童故事中所使用的单词。例如：它们使用了多少个由六个或以上字母组成的单词。每个单词只统计一次。要求以长度的大小输出这些单词,对于同样长的单词,则以字典顺序输出。

分析：

为 了解此问题,要做下面几项操作:

1.去掉所有重复的单词。

2.按单词的长度排序。

3.统计长度等于或超过6个字符的单词个数。

上述每一步都可使用泛型算法实现。

样例：

为了说清楚,使用下面这个简单的故事作为我们的输入:

	the quick red fox jumps over the slow red turtle

对于这个输入,我们的程序应该产生如下输出:

	1 word 6 characters or longer

1）、去除重复

假设我们的输入存储在一个名为words的 vector对象中,第一个子问题是将words中重复出现的单词去除掉:

    sort(words.begin(),words.end());
    vector
  
   ::iterator iter = unique(words.begin(),words.end());

    words.erase(iter,words.end());

  

vector对象包含使用的所有单词。首先对此vector对象排序。sort算法带有两个迭代器实参,指出要排序的元素范围。这个算法使用默认的小于(<)操作符比较元素。在本次调用中,要求对整个vector对象排序。

此时，vector对象内：

注意：red和the重复了。

2）、unique的使用

unique算法带有两个指定元素范围的迭代器参数。该算法删除相邻的重复元素，然后重新排列输入范围内的元素，并且返回一个迭代器，表示无重复的值范围的结束。

	unique(words.begin(),words.end());

语句调用结束后：