C++的STL开端

目录

STL 基本概念

STL 中容器、算法、迭代器

vector 存放内置数据类型

vector 存放自定义数据类型

vector 容器中嵌套容器

STL 基本概念

• STL 是什么？

1. STL（Standard  Template  Library，标准模板库）

--------------------------

• STL 广义分为：

1. 容器（container）
2. 算法（algorithm）
3. 迭代器（iterator）

--------------------------

• STL 的作用：

1. 提升代码复用性
2. 建立数据结构和算法的一套标准

--------------------------

• STL 的实现？

1. 几乎所有的代码都是采用类模板和函数模板实现
2. 容器和算法之间通过迭代器进行连接

--------------------------

• STL 六大组件

1. 容器：各种数据结构，如 vector、list、deque、set、map等，存放数据
2. 算法：常用算法，如 sort、find、copy、for_each等
3. 迭代器：扮演容器与算法之间的胶合剂
4. 仿函数：行为类似函数，可作为算法的某种策略
5. 适配器（配接器）：修饰容器或者仿函数或者迭代器的东西
6. 空间配置器：负责空间的配置与管理

---

STL 中容器、算法、迭代器

• 容器（container）：

简单说就是放数据的地方

STL 容器就是运用最广泛的一些数据结构实现出来的

常用的数据结构：数组、链表、树、栈、队列、集合、映射表 等

这些容器分为序列式容器和关联式容器两种：

1. 序列式容器：强调值的排序，序列式容器中的每个元素均有固定的位置
2. 关联式容器：二叉树结构，各元素之间没有严格的物理上的顺序关系

-------------------

• 算法（algorithm）：

简单说就是解决问题的方法

有限的步骤，解决逻辑或数学上的问题，这门学科叫算法

算法分为质变算法和非质变算法两种：

1. 质变算法：会改变区间内元素的内容，如：拷贝、替换、删除等
2. 非质变算法：不会改变区间内的元素内容，如：查找、计数、遍历、寻找等

-------------------

• 迭代器（iterator）:

容器和算法之间的连接

提供一种方法，使之能依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。

每个容器都有自己专属的迭代器

迭代器使用类似指针

迭代器种类

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

常用的容器迭代器为后两种

---

vector 存放内置数据类型

容器：vector

-

算法：for_each

-

迭代器：vector::iterator

-

第一种遍历方式代码：

vector<数据类型> 变量名，使用尾插法添加，需要用到 vector 容器头文件

利用 v.end() 是指向容器中最后一个元素的下一个位置，可以运用这一点，while 循环让指向第一个位置的 v.begin() 与 v.end() 进行比较，对起始位置进行更新，当两者相等时就不进行循环，就不会超出容器大小。

#include
using namespace std;
#include // vector 容器头文件

void test() {
    // 创建一个 vector 容器
    vector v;
    
    // 尾插法向容器中插入数据
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    // 通过迭代器访问容器中数据
    vector::iterator itBegin = v.begin(); // 起始迭代器，指向容器第一个元素
    vector::iterator itEnd   = v.end();   // 结束迭代器，指向容器中最后一个元素的下一个位置

    // 第一种遍历方式
    while (itBegin != itEnd) {
        cout << *itBegin << " ";
        itBegin++; // 更新起始迭代器
    }
    cout << endl;
    
}

int main() {
    test();
    system("pause");
    return 0;
}

运行结果：

 第二种遍历方式代码：

运用 for 循环，创建一个 vector::iterator it 类型的起始值 v.begin()，和 v.end() 进行比较，起始位置进行调整。和第一种方法大同小异

#include
using namespace std;
#include // vector 容器头文件

void test() {
    // 创建一个 vector 容器
    vector v;
    
    // 尾插法向容器中插入数据
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    // 通过迭代器访问容器中数据
    vector::iterator itBegin = v.begin(); // 起始迭代器，指向容器第一个元素
    vector::iterator itEnd   = v.end();   // 结束迭代器，指向容器中最后一个元素的下一个位置

    // 第二种遍历方式
    for (vector::iterator it = itBegin; it != itEnd; it++)
    {
        cout << *it << " ";
    }
    cout << endl;   
}

int main() {
    test();
    system("pause");
    return 0;
}

运行结果：

第三种方式遍历代码：

运用算法，需要加上标准算法头文件  

使用 for_each(起始迭代器，结束迭代器，函数名)；

#include
using namespace std;
#include // vector 容器头文件
#include //标准算法头文件

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

void test() {
    // 创建一个 vector 容器
    vector v;
    
    // 尾插法向容器中插入数据
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    // 通过迭代器访问容器中数据
    vector::iterator itBegin = v.begin(); // 起始迭代器，指向容器第一个元素
    vector::iterator itEnd   = v.end();   // 结束迭代器，指向容器中最后一个元素的下一个位置

    // 第三中遍历方式
    for_each(v.begin(), v.end(), myPrint);
    cout << endl;
}

int main() {
    test();
    system("pause");
    return 0;
}

运行结果：

---

vector 存放自定义数据类型

测试代码：

类 类型 vector

和上面的方法几乎一样。

#include
using namespace std;
#include // vector 容器头文件
#include //标准算法头文件

class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age  = age;
    }
    string m_Name;
    int m_Age;
};

void test() {
    // 创建 vector 容器
    vector v;

    // 实例化对象
    Person p1("zh", 20);
    Person p2("li", 18);
    Person p3("wa", 19);

    // 尾插法插入 Person 类型数据
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);

    // 迭代器 vector 
    vector::iterator itBegin = v.begin();
    vector::iterator itEnd   = v.end();

    // 遍历方式
    for (vector::iterator it = itBegin; it != itEnd; ++it) {
        cout << it->m_Name << " ";
        cout << it->m_Age  << endl;
    }
    cout << endl;
}

int main() {
    test();
    system("pause");
    return 0;
}

运行结果：

测试代码：

类指针 类型 vector 

#include
using namespace std;
#include // vector 容器头文件

class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age  = age;
    }
    string m_Name;
    int m_Age;
};

void test() {
    // 创建 vector 容器
    vector v;

    Person p1("zh", 20);
    Person p2("li", 18);
    Person p3("wa", 19);

    // 尾插法插入 Person* 类型数据
    v.push_back(&p1);
    v.push_back(&p2);
    v.push_back(&p3);

    // 遍历方式
    for (vector::iterator it = v.begin(); it != v.end(); ++it) {
        cout << (*it)->m_Name << " ";
        cout << (*it)->m_Age  << endl;
    }
    cout << endl;
}

int main() {
    test();
    system("pause");
    return 0;
}

运行结果：

---

vector 容器中嵌套容器

测试代码：

vector<类型>::iterator  后的变量解引用后的数据类型就是 <> 中的类型

#include
using namespace std;
#include // vector 容器头文件

void test() {
    // 小容器
    vector v1;
    vector v2;
    vector v3;

    // 小容器添加数据
    for (int i = 0; i < 3; ++i) {
        v1.push_back(i + 1); // 1-3
        v2.push_back(i + 4); // 4-6
        v3.push_back(i + 7); // 7-9
    }

    // 大容器
    vector> v;

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

    for (vector>::iterator it = v.begin(); it != v.end(); ++it) {
        // *it —— 容器 vector，尖括号里的数据类型就是 *it 的数据类型
        for (vector::iterator vit = (*it).begin(); vit != (*it).end(); vit++) {
            // *vit 数据类型是 int
            cout << *vit << " ";
        }
        cout << endl;
    }
}

int main() {
    test();
    system("pause");
    return 0;
}

运行结果：

---