【C++12】C++ STL概论

帆舟

复用性必须建立在某种标准之上。但在许多环境下，就连软件开发最基本的数据结构(data structures) 和算法(algorithm)都未能有一套标准。大量程序员被迫从事大量重复的工作，竟然是为了完成前人已经完成而自己手上并未拥有的程序代码，这不仅是人力资源的浪费，也是挫折与痛苦的来源。
为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹性、交互操作性（相互合作性,interoperability）,诞生了STL。
1、概述

1 STL基本概念

STL(Standard Template Library,标准模板库),STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator),容器和算法之间通过迭代器进行无缝连接。
STL提供了六大组件，彼此之间可以组合套用，这六大组件分别是:容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器。

• 容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据，从实现角度来看，STL容器是一种class template。
  
• 算法：各种常用的算法，如sort、find、copy、for_each。从实现的角度来看，STL算法是一种function tempalte。
  
• 迭代器：扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将operator* , operator-> , operator++,operator--等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。
  
• 仿函数：行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的class 或者class template
  
• 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。
  
• 空间配置器：负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte。
  

STL六大组件的交互关系，容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数。
2 STL优点

• 内建在C++编译器中，不需要安装额外内容
  
• 不需要了解具体实现内容，只要熟练运用即可
  
• 高复用，可移植，高性能
  
  
  
  • 高可重用性：STL 中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。
    
  • 高性能：如 map 可以高效地从十万条记录里面查找出指定的记录，因为 map 是采用红黑树的变体实现的。
    
  • 高移植性：如在项目 A 上用 STL 编写的模块，可以直接移植到项目 B 上。
    
  
  

2、STL三大组件

1 容器

容器，置物之所。
容器划分

• 序列式容器： 序列式容器强调值的排序，序列式容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。Vector容器、Deque容器、List容器等。
  
• 关联式容器    关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器另一个显著特点是：在值中选择一个值作为关键字key，这个关键字对值起到索引的作用，方便查找。Set/multiset容器 Map/multimap容器
  

2 算法

算法，问题之解法。

• 质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
  
• 非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等
  

3 迭代器

迭代器(iterator)是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。其中iterator模式定义如下：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。
迭代器的种类:

输入迭代器	提供对数据的只读访问	只读，支持++、==、！=
输出迭代器	提供对数据的只写访问	只写，支持++
前向迭代器	提供读写操作，并能向前推进迭代器	读写，支持++、==、！=
双向迭代器	提供读写操作，并能向前和向后操作	读写，支持++、--，
随机访问迭代器	提供读写操作，并能以跳跃的方式访问容器的任意数据，是功能最强的迭代器	读写，支持++、--、[n]、-n、<、<=、>、>=

3、STL初识

1 原始指针也是一种迭代器

//原生指针也是迭代器
void test01()
{
        int arr[5] = { 1, 2, 3, 4, 5 };
        int* p = arr;
        for (int i = 0; i < 5; i++)
        {
                //cout << arr << endl;
                cout << *(p++) << endl;
        }
}
2 容器遍历三种方法

• vector容器
  
  
  
  • vector::iterator  itBegin = v.begin(); //v.begin() 起始迭代器，指向容器中第一个数据
    
  • vector::iterator  itEnd = v.end(); //v.end()；结束迭代器，指向的是容器中最后一个元素的下一个位置
    
  
  
• for (vector<int>::iterator it = v.begin(); it != v.end(); it++)    --这种最为常见，推荐掌握
  
• 利用算法遍历容器  for_each(v.begin(),v.end() , myPrint )  头文件    algorithm
  

void myPrint(int val)
{
        cout << val << endl;
}

void test02()
{
        vector<int>v; //创建一个vector容器，容器中存放元素类型是int类型
        //插入元素
        v.push_back(10);
        v.push_back(30);
        v.push_back(20);
        v.push_back(40);

        //遍历元素
        vector<int>::iterator  itBegin = v.begin(); //v.begin() 起始迭代器，指向容器中第一个数据
        vector<int>::iterator  itEnd = v.end(); //v.end()；结束迭代器，指向的是容器中最后一个元素的下一个位置

        //第一种遍历
        //while (itBegin!=itEnd)
        //{
        //        cout << *itBegin << endl;
        //        itBegin++;
        //}

        //第二种遍历
        //for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
        //{
        //        cout << *it << endl;
        //}

        //第三种遍历
        for_each(v.begin(), v.end(), myPrint);
}
3 容器中存放自定义数据类型

//自定义数据类型
class Person
{
public:
        Person(string name, int age)
        {
                this->m_Name = name;
                this->m_Age = age;
        }
        string m_Name;
        int m_Age;
};

void test03()
{
        vector<Person> v;

        Person p1("aaa", 10);
        Person p2("bbb", 20);
        Person p3("ccc", 30);
        Person p4("ddd", 40);

        v.push_back(p1);
        v.push_back(p2);
        v.push_back(p3);
        v.push_back(p4);

        //每个容器都有自己专属的迭代器
        for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
        {
                // *it 等价于 Person
                cout << "姓名： " << (*it).m_Name << " 年龄： " << it->m_Age << endl;
        }
}
4 容器中存放自定义数据类型指针

//借用上例中的 class Person
//存放自定义数据类型指针
void test04()
{
        vector<Person*> v;  //定义位指针类型

        Person p1("aaa", 10);
        Person p2("bbb", 20);
        Person p3("ccc", 30);
        Person p4("ddd", 40);

        v.push_back(&p1);  //这里需要插入地址
        v.push_back(&p2);
        v.push_back(&p3);
        v.push_back(&p4);

        for (vector<Person*>::iterator it = v.begin(); it != v.end(); it++)
        {
                // *it  等价于 Person *
                cout << "姓名： " << (*it)->m_Name << " 年龄： " << (*it)->m_Age << endl;
        }
}
5 容器嵌套容器

//容器嵌套容器
void test05()
{
        vector<vector<int>>v;

        vector<int>v1;
        vector<int>v2;
        vector<int>v3;

        for (int i = 0; i < 5; i++)
        {
                v1.push_back(i + 1);
                v2.push_back(i + 10);
                v3.push_back(i + 100);
        }

        //将小容器放入到大容器中
        v.push_back(v1);
        v.push_back(v2);
        v.push_back(v3);

        //遍历大容器
        for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++)
        {
                // *it 等价于 vector<int>
                for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++)
                {
                        cout << *vit << " ";
                }
                cout << endl;
        }
}


相关链接

• 【C++00】C++从入门到实践
  

若觉得有用，欢迎 点赞/收藏  ~~~

一生的最爱

垃圾内容，路过为证。