标准模板库数据结构-数据结构和数据库一样吗

admin

作者

C++ 标准模板库

1. 容器

容器用于存储数据元素，它们是由长度（元素个数）可变的同类型的元素所构成的序列，如向量、 *** 、栈、队列等。

vector<元素类型>：用于快速定位（访问）任意位置上的元素以及主要在元素序列的尾部增加/删除元素的场合。在vector头文件中定义，用动态数组实现。

map<关键字类型，值类型> 和 multimap<关键字类型，值类型>：元素按关键字排序，multimap中不同元素的关键字可以相同，在map头文件中定义，常常用某种二叉树实现。

set<元素类型>和multiset<元素类型>：在set头文件中定义，set可以用于去重。

basic_string<元素类型>：与vector相似，不同之处在于其元素类型是字符类型，并提供一系列与字符串相关的操作。string和wstring是它的两个实例basic_string<char>和basic_string<wchar_t>。在string头文件中定义。

list<元素类型>：用于经常在元素序列中任意位置上插入/删除元素的场合。在list头文件中定义，用双向链表实现。

deque<元素类型>：用于主要在元素序列的两端增加/删除元素以及需要快速定位（访问）任意位置上的元素的场合。在deque头文件定义，用分段的连续空间结构实现。

stack<元素类型>：用于仅在元素序列的尾部增加/删除元素的场合，在stack头文件中定义，一般基于deque来实现。

queue<元素类型>：用于仅在元素序列的尾部增加，头部删除元素的场合。在queue头文件中定义，一般基于deque来实现。

priority_queue<元素类型>：与queue的操作类似，不同之处在于每次增加元素之后，它将对元素位置进行调整，使得头部元素总是最大的。也就是说，每次删除的总是最大的元素。在queue头文件中定义，一般基于vector和heap结构来实现。

2. 迭代器

迭代器实现了抽象的指针（智能指针），它们指向容器中的元素，用于对容器中的元素进行访问和遍历。

输入迭代器：只能用于读取它所指向的容器元素。

输出迭代器：只能用于修改它所指向的容器元素。

前向迭代器：可以用于读取和修改它所指向的容器元素。

双向迭代器：可以用于读取/修改它所指向的容器元素。

随机访问迭代器：可以用于读取/修改它所指向的容器元素。

3. 算法

调序算法：改变容器中元素的次序。如sort reverse random_shuffle等

编辑算法：用于实现对容器元素的复制、替换、删除、交换、合并、赋值等操作。如copy replace remove unique swap等

查找算法：用于在容器中查找元素或子元素序列。如find count search等

算术算法：用于对容器内的元素进行求和、内积和、差等。如accumulate partial_sum inner_product等

*** 算法：用于实现 *** 的运算。如include set_union set_intersection等

堆算法：用于实现按对结构存储和操作容器中的元素，具有堆结构的容器的主要特点之一是：第一个元素总是最大的。如make_heap pop_heap等

元素遍历并操作算法：依次访问一个范围内的每个元素，并对每个元素调用某个指定的操作函数或函数对象f。for_each

————————————————

C++标准模板库(STL)学习精要

这一篇主要对C++中使用最广泛的STL进行学习梳理，参照此文再配合STL参考手册，轻松掌握编程精要标准模板库数据结构！

1、STL基本头文件

STL主要包含容器、算法和迭代器三个部分。容器实现了大多数数据结构标准模板库数据结构；迭代器类似指针，通过它的有序移动将容器中的元素与算法关联起来，是实现STL的基础。常用的STL包含头文件如下：

image.png

STL包含文件均不含扩展名，其源文件位置一般是在编译器VC安装目录的include内。

2、模板

模板分为函数模板和类模板。函数模板与预处理的用法类似，提供编译过程中的文本替换功能，对类型有一定的保护标准模板库数据结构；类模板可以编写通用的、类型安全的类。

STL的思想就是内存的动态分配、销毁、再分配，将内存管理部分进一步抽象，编成系统代码，应用过程中用户可不必明白内存的变化，不必自己编写代码来管理内存。

STL标准模板库强调软件的复用。Traits技术是采用的重要手段，它提取不同类的共性，以便能统一处理，它依赖将显式模板特殊化将不同的部分用统一接口来包装。STL中有大量的模板函数，故很多时候要重载与之对应的操作符。函数模板相当于应用框架，操作符重载相当于调用接口。

3、迭代器

迭代器是STL重要的核心技术，提供了统一访问容器元素的 *** 。迭代器即指针，可以是所需的任何类型，它是最大好处是使容器与算法分离。因为不同容器中完成相同功能代码的思路大体相同，将其抽象出来就产生了迭代器，这是泛型编程的思想。

在自己动手编写迭代器时，要在类中增加begin()、end()函数，用于获取起止迭代指针，要增加相应迭代器类，重载相关运算符，从而可以调用。

特定容器有特定的迭代器，故将迭代器作为内部类更适合应用。每个容器均有对应的迭代器，容器通过迭代器共享某一具体算法，而算法不具体依赖某一具体容器。由此可见，STL的编程思想是：1.形成容器元素；2.取出所需的迭代指针；3.调用通用算法。STL迭代器共分五大类型：

输入迭代器istream_iterator，按其顺序只能读取一次。构造函数可参阅STL库；

输出迭代器ostream_iterator，按顺序只写一次。构造函数可参阅STL库；

前向迭代器，这种迭代器包含了输入输出迭代器两者所有可能，可以对一个值多次读写。前向迭代器只能向前移动；

双向迭代器，具有前向迭代器的全部功能，它也可以向后移动操作；

随机访问迭代器，具有双向迭代器的全部功能，再加上一个指针的所有功能。

从以上可以看出，从前到后迭代器是一步步细化的，编程时根据实际情况选择适宜的迭代器，从而达到最高的效率。

4、输入输出流

标准输入流cin指键盘，标准输出流cout指显示器。运算符”<<”用作输入输出流的插入符，表明“输出到”；运算符”>>”用作提取符，表明“赋值给”。cin输入时，各数值间默认以空格为分界符的。

在交互过程中，一般要一次输入一行字符，为弥补cin的缺陷，可以改用get系统函数。get和getline函数的区别在于，get遇停止符时，不从输入流中提取界定符，而直接在末尾加”\0”标志，getline则从输入流中提取界定符，但不会将其放入结果缓冲区。

处理流错误：

C++对每次输入输出操作的结果都记录了其状态信息，主要函数如下：

image.png

文件输入输出流：

C++中文件读写用到的很多常数都在基类ios被定义出来，ifstream类只用于读取文件数据，ofstream类只用于写入数据到文件，fstream类则可以用于读取和写入文件数据。

文件打开的三个流都是用构造函数或open函数来实现，第一个参数是文件名，第二个参数是打开方式，打开方式如下：

image.png

文件关闭的三个流都是用close()函数释放文件资源；

文件的读写分为两种情况：当读写文本文件时，可直接创建输入输出文件对象来完成操作；当读写二进制文件时，主要通过流对象中的read、write函数实现，不过也要创建流对象；

定位输入输出流。流的位置标识有三个：

image.png

字符串输入输出流：

字符串输入输出流类是直接对内存而不是对文件或标准输出进行的操作。它使用cin、cout相同的格式函数来操作内存中的数据。全部的字符串流类声明都包含在标准头文件<sstream>中，标准库定义了三种串流：

Istringstream：字符串输入流，提供读string功能；

Ostringstream：字符串输出流，提供string写功能；

Stringstream：字符串输入输出流，提供读写string功能；

利用字符串输入输出流，可以方便地将多种基本数据类型组合成字符串，也可以反解字符串。

5、函数对象

将函数作为对象是程序设计的新的思维，STL通过重载类中operator函数实现函数对象的功能。标准C++库根据operator()参数个数为0，1，2划分，有如下几种函数对象：

a. 发生器：没有参数且返回任意类型值的函数对象，如随机函数发生器；

b. 一元函数：只有一个任意类型的参数，返回一个可能不同类型的函数对象；

c. 二元函数：两个任意类型参数，且返回一个任意类型的函数对象；

d. 一元判定函数：返回bool类型的一元函数；

e. 二元判定函数：返回bool类型的二元函数；

6、通用容器

STL提供了专家级的各种容器，功能更好，复用性更强，在应用程序开发过程中尽可能应用STL。

容器可以分为以下三类：

a. 序列性容器：按线性序列来存储某类型值的 *** ，每个元素都有自己特定的位置，顺序容器主要有vector、deque、list；

b. 关联式容器：它更注重快速高效的检索数据的能力，根据键值key来检索数据。容器中成员在初始化后都是按一定顺序排好的，关联式容器主要有set、multiset、map、multimap；

c. 容器适配器：对已有容器进行某些特性的再封装，它不是一个新容器，主要有stack、queue；

各容器的共性和区别：

各容器一般来说都有下列函数：默认构造函数、复制构造函数、析构函数、empty()、max_size()、size()、operator=、operator<、operator<=、operator>、operator>=、operator==、operator!=、swap()。

顺序容器和关联容器都共有下列函数：

image.png

a. vector容器是动态数组，在堆中分配内存，元素连续存放，有保留内存。若减少大小后内存也不会释放，当元素个数大于当前容量时，会分配原来2倍容量，从而将元素复制到新空间，原空间释放。可以快速随机访问元素，快速在末尾插入删除元素，此过程中不用移动内存；对中间元素插入删除时要移动内存。若元素是结构体类型或类，移动内存时还要进行构造和析构操作。vector可以使用[]操作符。

b. deque是双端队列，可以快速地随机访问元素，快速地在开始和末尾插入删除元素。随机插入比两端插入要慢，重新分配内存比vector要快。重新分配空间后，原空间保持，只是新建立了一个内存块，将新数据插入这个内存块，没有空间的复制删除过程，故deque是由多个分段连续的内存空间组成。因此，deque在某一位置上的操作是线性的，各小片内存间用链表相连，还是可以使用[]，只是没有vector快。对deque排序，可以将其复制到vector中排完序后再复制回去。

c. list是一种双线性列表，只能顺序访问，不支持随机访问。对每个元素分配空间，不存在空间不够和重新分配的情况。

d. set是 *** ，支持快速查找，不允许有重复值，用平衡树结构来存储；multiset支持快速查找，允许有重复值。

e. map是映射，一对一映射，支持关键字快速查找，不允许有重复值；multimap是一对多映射，基于关键字查找，允许有重复值。

===================本篇完结======================