《C++笔记第二部分数据结构及STL容器篇》第1章数据结构及STL容器简介

PHP小丑

1.1数据结构简介

数据结构起源

计算机从解决数值计算问题到解决生活中的问题；现实生活中的问题涉及不同个体间的复杂联系；需要在计算机程序中描述生活中个体间的联系；数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系；不是研究复杂的算法。

数据结构中的基本概念

数据是程序的操作对象，用于描述客观事物 (int a, int b,)。数据的特点：可以输入到计算机，可以被计算机程序处理。数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：int，float，char等等
数据元素：组成数据的基本单位
数据项：一个数据元素由若干数据项组成
数据对象：性质相同的数据元素的集合（比如：数组，链表）

图1
数据元素之间不是独立的，存在特定的关系，这些关系即结构。数据结构指数据对象中数据元素之间的关系。

数据的逻辑结构

指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：

数据的物理结构（存储结构）

【注】物理结构指存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。

数据的运算

数据的运算指数据在逻辑结构上定义的操作，它在数据的存储结构上实现。

1.2 STL简介
STL（Standard Template Library）即标准模板库，惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。
作为一个C++程序设计者，STL是一种不可忽视的技术。Standard Template Library (STL)：标准模板库，更准确的说是 C++ 程序设计语言标准模板库。学习过MFC的人知道，MFC是微软公司创建的 C++ 类库。而与之类似的是 STL 是模板库，只不过 STL 是 ANSI/ISO 标准的一部分，而 MFC 只不过是微软的一个产品而已。也就是说STL是所有C++编译器和所有操作系统平台都支持的一种库，说它是一种库是因为，虽然STL是一种标准，也就是说对所有的编译器来说，提供给C++程序设计者的接口都是一样的。也就是说同一段STL代码在不同编译器和操作系统平台上运行的结果都是相同的，但是底层实现可以是不同的。令人兴奋的是，STL的使用者并不需要了解它的底层实现。
容器，置物之所也。像桶可装水，碗可盛汤，C++的容器，可以存储对象。容器有多种，用来处理不同的元素操作诉求。按照元素存储到容器中以及访问方式的差异，容器分为顺序容器与关联容器。顺序容器也称为序列式容器。序列式容器按元素插入的顺序存储元素，这些元素可以进行排序，但未必是有序的。C++本身内置了一个序列式容器array（数组），STL另外提供了vector,list,forward_list,deque,stack,queue,priority-queue，string等等序列式容器。所有的容器都是基于模板实现的，因为容器必须保证能装得下各种各样的类型。其中，stack，queue都是基于deque来实现的，priority-queue基于heap来实现，从技术上来说它们属于容器适配器（adapter）。其中array与forward_list是C++11添加的新容器类型。STL也是算法和其他一些组件的集合，是世界上顶级C++程序员多年的杰作，是泛型编程的一个经典范例。
STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL现在是C++的一部分，内建在C++编译器中，因此不用额外安装什么。
STL可分为六个部分：

 容器(containers)：特殊的数据结构，实现了数组、链表、队列、等等，实质是模板类
 迭代器(iterators)：一种复杂的指针，可以通过其读写容器中的对象，实质是运算符重载
 算法(algorithms)：读写容器对象的逻辑算法：排序、遍历、查找、等等，实质是模板函数
 空间配置器(allocator)：容器的空间配置管理的模板类
 配接器(adapters)：用来修饰容器、仿函数、迭代器接口
 仿函数(functors)：类似函数，通过重载（）运算符来模拟函数行为的类

组件间的关系：
container（容器）通过 allocator（配置器）取得数据储存空间，algorithm（算法）通过 iterator（迭代器）存取 container（容器）内容，functor（仿函数）可以协助 algorithm（算法）完成不同的策略变化，adapter（配接器）可以修饰或套接 functor（仿函数）。
STL标准模版库是一种泛型编程（generic programming）。泛型编程关注的是算法，在C++中，利用模版完成编写独立于数据类型的代码。
STL容器包括：数组、链表、队列，等等；能进行查找、排序、随机排队，等等。
STL序列容器：vector、deque、list
 vector
将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速，但是在中部或头部安插元素比较费时
 deque
是“double-ended queue”的缩写，可以随机存取元素（用索引直接存取），数组头部和尾部添加或移除元素都非常快速，但是在中部或头部安插元素比较费时。
 list
双向链表，不提供随机存取（按顺序走到需存取的元素），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针
STL关联容器：set、multiset、map、multimap
 set/multiset
内部的元素依据其值自动排序，set内的相同数值的元素只能出现一次，multisets内可包含多个数值相同的元素，内部由二叉树实现（实际上基于红黑树(RB-tree）实现），便于查找
 map/multimap
map的元素是成对的键值/实值，内部的元素依据其值自动排序，map内的相同数值的元素只能出现一次，Multimap内可包含多个数值相同的元素，内部由二叉树实现（实际上基于红黑树(RB-tree）实现），便于查找
其他一些容器：
hash_map,hash_set,hash_multiset,hash_multimap
STL迭代器：iterator
表

[Unix] 《C++笔记第二部分数据结构及STL容器篇》第1章数据结构及STL容器简介

相关帖子

recuva怎么用 recuva使用方法

excel怎么设置下拉菜单的数据设置下拉数据方法

MySQL数据库如何给表设置约束详解

MySQL Server 层和存储引擎层是怎么交互数据的？

2min速览：从设计、实现和优化角度浅谈Alluxio元数据同步

MySQL由浅入深掌握连接查询

Mysql8导入数据到Mysql5.7的实现步骤

MySQL数据库触发器从小白到精通

一篇带给你MySQL索引知识详解

Windows系统怎么才能和苹果系统相连进行数据互通？

PHP小丑 LV3

[Unix] 《C++笔记 第二部分 数据结构及STL容器篇》第1章 数据结构及STL容器简介