《三十分钟掌握STL》(STL迭代器高级应用)-白红宇的个人博客

发布日期：2021-05-19 20:28:46 浏览次数：17 分类：精选文章

本文共 5159 字，大约阅读时间需要 17 分钟。

《三十分钟掌握STL》

译者：kary

电子书制作：冷寒生

contact:karymay@163.net

这是一本简小的技术小书，原名为《using stl》，不知谁编写的。翻译工作出于对STL的兴趣，耗时两个晚上完成。本人未对翻译内容进行校对，因此如果在短短三十分钟内无法获得收获，建议直接丢弃。文中省略了大量内容，尤其是对于STL的实现细节部分,…只是浪费了两晚的时间。

STL概述

STL的核心特点之一是将数据结构和算法分离。尽管这种分离看似简单，但它却为STL的通用性奠定了基础。例如，由于STL的sort()函数高度通用，你可以使用它来操作几乎任何数据集合，包括数组、容器以及链表等。

要点

模板特性：STL的算法以模板函数的形式提供。为了区分STL算法和其他组件，书中用一对圆括号来表示算法示例，如sort()。

非面向对象：STL的一个显著特性是它并非面向对象编程语言的延伸。它主要利用模板而非封装、继承或虚函数（OOP的三个关键要素），这使得STL的组件更具通用性。尽管这与OOP有点违背直觉，但正是这种特性让STL的组件能够在更广泛的场景中使用。

内联特性：STL通过内联机制实现代码的短小高效。开发者可以通过优化标志-O来确保编译后的STL程序能够有效内联扩展。

提示

确保在使用了STL的程序中至少使用-O优化标志以保证内联扩展。

STL提供了众多模板类和函数，无论是面向传统编程还是面向面向对象编程都可以使用。

其50多个算法全部通用，不依赖特定的数据类型。下面将从三个基本组件入手说明：迭代器、容器和算法。

迭代器

迭代器的定义

迭代器类似于指针，能够访问容器中对象的方法。例如，通过迭代器可以指定容器的某一范围内的对象。实际上，C++的指针本身也是一种迭代器类型。不过，STL中的迭代器不仅限于指针，还可以是其他定义了operator*()和相应操作符的类对象。

迭代器的创建与使用

迭代器通常可以通过容器类提供的方法（如begin()和end()）获取。例如，使用vector::iterator可以创建以矢量为背景的迭代器。同样，反向迭代器（如rbegin()和`rend()``）允许从容器末尾开始反向迭代。

迭代器的类型

STL定义了五种迭代器类型：

Input迭代器：只能读取内容，典型用于查找操作。

Output迭代器：只能写入内容，通常用于拷贝操作。

Forward迭代器：支持读写操作，以及向前推进。

Bidirectional迭代器：支持读写操作，并支持向前向后移动。

Random-access迭代器：支持随机访问，并支持读写操作。
不过，虽然在不同的实现中迭代器细节可能有所不同，但它们之间可以采用继承关系。例如，Forward迭代器可以被视为Output或Input迭代器的子类。

容器

容器的特性

容器类（如deque、vector、list等）是STL中最核心的数据结构之一。它们通过模板的方式操作，使得算法无需关心容器的具体类型，只需通过迭代器访问数据即可。

容器与迭代器的关系

使用容器操作时，通常需要配合迭代器来获取数据。例如，使用容器的begin()和end()方法获取迭代器对象，进而进行操作。这种方式使得容器操作灵活且高效。

算法

算法的模板化

STL的算法以模板函数的形式存在，能够适用于不同的数据类型和容器。例如，find()函数可以在任何支持随机访问迭代器的数据结构上使用，无论是数组、容器还是其他结构。

算法的通用性

由于其模板特性，STL算法几乎可以操作任何数据结构。以下是一些常见算法的示例：

sort()：对数据集进行排序。

find()：搜索某个值的位置。

replace()：替换某个值或多个值。

reverse()：对数据集进行逆序排列。

头文件使用

为了避免头文件之间的冲突，STL的头文件不再使用.h扩展。常用的头文件类似于<string>、<vector>、<algorithm>、<iterator>等。例如：

#include 
   
      
#include 
    
       
#include 
     
        
#include

严格按照命名空间**

注意：为了确保可移植性，应避免直接引用像iterator.h或stl_iterator.h这样的具体实现头文件，而应该使用没有.h后缀的文件名。为了节省空间，表1列出了常用容器类及其头文件的对应关系。

名字空间

为了避免命名冲突，STL的所有标志符都被封装在std名字空间中。例如，std::sort()和std::find()与系统库中的相应函数不会重复。即使你的编译器不支持名字空间，也可以通过在源代码中包含using namespace std;来使用这些标志符。在实际编译时，这一行代码通常会放在所有#include指令的后面，例如：

#include 
   
      
#include 
    
       
#include 
     
        
...  
using namespace std;

迭代器的示例

指针作为迭代器

C++中的指针本身也是一种迭代器。例如，下面的程序可以使用指针迭代器来搜索数组中的值：

#include 
    
      #include 
     
        
#define SIZE 100  
int iarray[SIZE];  
int main() {  
    iarray[20] = 50;  
    int* ip = find(iarray, iarray + SIZE, 50);  
    if (ip != iarray + SIZE) {  
        std::cout << *ip << " found in array" << std::endl;  
    } else {  
        std::cout << "50 not found in array" << std::endl;  
    }  
    return 0;  
}

容器迭代器

使用容器迭代器的示例：

#include 
    
      #include 
     
       #include 
      
         
using namespace std;  
vector
       
         intVector(100);  
int main() {  
    intVector[20] = 50;  
    vector
        
         ::iterator intIter = find(intVector.begin(), intVector.end(), 50);  
    if (intIter != intVector.end()) {  
        cout << "Vector contains value " << *intIter << endl;  
    } else {  
        cout << "Vector does not contain 50" << endl;  
    }  
    return 0;  
}

追及其它内容

断言函数

断言函数允许对容器中的数据进行自定义操作。例如，使用for_each()可以调用用户定义的函数对容器中的每个元素执行某种操作：

#include 
    
      #include 
     
       #include 
      
         
using namespace std;  
void initialize(long &ri) {  
    ri = (random() - RAND_MAX / 2) % 100;  
}  
void show(const long &ri) {  
    cout << ri << " ";  
}  
bool isMinus(const long &ri) {  
    return ri < 0;  
}  
long sum = accumulate(vector
       
        ::begin(), vector
        
         ::end(), 0);

插入迭代器

插入迭代器可以将元素插入到容器的前后位置。例如，使用front_inserter()可以将元素插入容器的开头：

#include 
    
      #include 
     
       #include 
      
         
int iArray[5] = {1, 2, 3, 4, 5};  
list
       
         iList;  
copy(iArray, iArray + 5, front_inserter(iList));

绑定器与函数对象

使用绑定器可以将 Functor 与参数结合使用。例如，可以通过bind1nd(greater<int>(), 8)创建一个函数对象，来计算列表中大于8的元素数量：

#include 
    
      #include 
     
       #include 
      
         
using namespace std;  
int main() {  
    list
       
         aList({1, 2, 3, 4, 5, 6, 7, 8, 9, 10});  
    int k = 0;  
    count_if(aList.begin(), aList.end(), bind1nd(greater
        
         (), 8), k);  
    cout << "Number of elements < 8: " << k << endl;  
    return 0;  
}

发生器

发生器可以记住上一次调用的结果，并在下次调用时继续。这对于生成随机数等任务非常有用。例如，下面的发生器实现了一个斐波那契数列随机数生成器：

template 
    
       
class FiboRand : public unary_function
     
       {  
    int i, j;  
    Arg sequence[18];  
    FiboRand() {  
        sequence[17] = 1;  
        sequence[16] = 2;  
        for (int n = 15; n > 0; --n) {  
            sequence[n] = sequence[n+1] + sequence[n+2];  
        }  
        i = 17; j = 5;  
    }  
    Arg operator()(const Arg &arg) {  
        Arg k = sequence[i] + sequence[j];  
        sequence[i] = k;  
        i--; j--;  
        if (i == 0) i = 17; if (j == 0) j = 17;  
        return k % arg;  
    }  
};  
int main() {  
    FiboRand
      
        fibogen;  
    vector
       
         v({1,2,3,4,5,6,7,8,9,10});  
    random_shuffle(v.begin(), v.end(), fibogen);  
    return 0;  
}

总结

STL是一个功能强大的工具，它的核心理念是通过数据结构与算法的分离和模板机制实现对各种数据的通用处理能力。尽管它不具备面向对象编程的特性，但通过高效的模板内联机制和灵活的迭代器体系，STL在现代C++编程中得到了广泛应用。

上一篇：华三面试

下一篇：抓包工具tcpdump使用详解

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！