20130404-STL学习1 下载本文

内容发布更新时间 : 2024/12/23 12:59:47星期一 下面是文章的全部内容请认真阅读。

C++模板与STL库介绍

C++ 语言的核心优势之一就是便于软件的重用

C++中有两个方面体现重用:

1. 面向对象的思想:继承和多态,标准类库

2. 泛型程序设计(generic programming) 的思想:模板机制,以及标准模板库 STL

泛型程序设计

1. 泛型程序设计,简单地说就是使用模板的程序设计法。

将一些常用的数据结构(比如链表,数组,二叉树)和算法(比如排序,查找)写成模板,以后则不论数据结构里放的是什么对象,算法针对什么样的对象,则都不必重新实现数据结构,重新编写算法。

2. 标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合。主要由 Alex Stepanov 开发,于1998年被添加进C++标准

3. 有了STL,不必再从头开始编写繁多的标准数据结构和算法,并且一样可获得非常高的性能。

模板工作方式

1. 函数模板只是说明,不能直接执行,需要实例化为模板函数后才能执行

2. 在说明了一个函数模板后,当编译系统发现有一个对应的函数调用时,将根据实参中的类型来确认是否匹配函数模板中对应的形参,然后生成一个重载函数。该重载函数的定义体与函数模板的函数定义体相同,它称之为模板函数

模板优缺点

1. 函数模板方法克服了C语言解决上述问题时用大量不同函数名表示相似功能的坏习惯

2. 克服了宏定义不能进行参数类型检查的弊端

3. 克服了C++函数重载用相同函数名字重写几个函数的繁琐 4. 缺点,调试比较困难

一般先写一个特殊版本的函数 运行正确后,改成模板函数

STL中的几个基本概念

1. 容器:可容纳各种数据类型的多元素数据结构。

2. 迭代器:可依次存取容器中元素的东西(指针?下标?) 3. 算法:用来操作容器中的元素的函数模板。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象。 函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。

1

容器概述

可以用于存放各种类型的数据(基本类型的变量,对象等)的数据结构。 容器分为三大类: 1) 顺序容器

vector:后部插入/删除,直接访问 deque:前/后部插入/删除,直接访问 list:双向链表,任意位置插入/删除 2)关联容器

set:快速查找,无重复元素

multiset :快速查找,可有重复元素

map:一对一映射,无重复元素,基于关键字查找

multimap :一对一映射,可有重复元素,基于关键字查找 前2者合称为第一类容器 3)容器适配器 stack:LIFO queue:FIFO

priority_queue:优先级高的元素先出

对象被插入容器中时,被插入的是对象的一个复制品。

许多算法,比如排序,查找,要求对容器中的元素进行比较,所以,放入容器的对象所属的类,还应该实现 == 和 < 运算符。

顺序容器简介

1) vector 头文件 实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。 2) deque 头文件

也是个动态数组,随机存取任何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。 3) list 头文件

双向链表,在任何位置增删元素都能在常数时间完成。不支持随机存取。 上述三种容器称为顺序容器,是因为元素的插入位置同元素的值无关。

关联容器简介

关联式容器内的元素是排序的,插入任何元素,都按相应的排序准则来确定其位置。关联式容器的特点是在查找时具有非常好的性能。 1) set/multiset: 头文件

set 即集合。set中不允许相同元素,multiset中允许存在相同的元素。 2) map/multimap: 头文件

map与set的不同在于map中存放的是成对的key/value。 并根据key对元素进行排序,可快速地根据key来检索元素

map同multimap的不同在于是否允许多个元素有相同的key值。

2

上述4种容器通常以平衡二叉树方式实现,插入和检索的时间都是 O(logN)

容器适配器简介

1) stack :头文件

栈。是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则 2) queue :头文件

队列。插入只可以在尾部进行,删除、检索和修改只允许从头部进行。按照先进先出的原则。

3)priority_queue :头文件

优先级队列。最高优先级元素总是第一个出列

容器的共有成员函数

1) 所有标准库容器共有的成员函数:

相当于按词典顺序比较两个容器大小的运算符: =, < , <= , > empty : 判断容器中是否有元素

max_size: 容器中最多能装多少元素 size: 容器中元素个数 swap: 交换两个容器的内容 2) 只在第一类容器中的函数:

begin 返回指向容器中第一个元素的迭代器

end 返回指向容器中最后一个元素后面的位置的迭代器 rbegin 返回指向容器中最后一个元素的迭代器

rend 返回指向容器中第一个元素前面的位置的迭代器 erase 从容器中删除一个或几个元素 clear 从容器中删除所有元素

比较两个容器的例子: #include #include int main() {

std::vector v1; std::vector v2; v1.push_back (5); v1.push_back (1); v2.push_back (1); v2.push_back (2); v2.push_back (3); std::cout << (v1 < v2); return 0; } 输出:0

3

, >=, == , !=