vector下标操作不添加元素,属于安全的泛型编程。相对于普通数组,vector定义的数据线性序列,可以动态使用push_back添加元素。这是普通数组所没有的功能。

关联容器中的元素不是顺序排列,而是按键(key)排序的。关联容器共享了许多顺序容器提供的操作,此外,还定义了自己特殊的操作。

C++ 定义的容器类型中,只有 vector 和 deque 容器提供下面两种重要的运算集合:迭代器算术运算,以及使用除了 == 和 != 之外的关系操作符来比较两个迭代器(== 和 != 这两种关系运算适用于所有容器)。

vector 和 deque 容器都支持对其元素实现高效的随机访问。也就是说,我们可以高效地先访问 5 号元素,然后访问 15 号元素,接着访问 7 号元素,等等。 由于 vector 容器的每次访问都是距离其起点的固定偏移,因此其随机访问非常有效率。在 list 容器中,上述跳跃访问会变得慢很多。在 list 容器的元素之间移动的唯一方法是顺序跟随指针。从 5 号元素移动到 15 号元素必须遍历它们之间所有的元素。

默认的 stack 和 queue 都基于 deque 容器实现,而 priority_queue 则在 vector 容器上实现。在创建适配器时,通过将一个顺序容器指定为适配器的第二个类型实参,可覆盖其关联的基础容器类型:

// empty stack implemented on top of vector

stack< string, vector<string> > str_stk;

// str_stk2 is implemented on top of vector and holds a copy of svec

stack<string, vector > str_stk2(svec);

支持先进先出或后进后出或优先的顺序操作;

最经常使用的容器类型是 vector,它支持对元素的快速随机访问。可高效地在 vector 容器尾部添加和删除元素,而在其他任何位置上的插入或删除运算则要付出比较昂贵的代价。deque 类与 vector 相似,但它还支持在 deque 首部的快速插入和删除运算。list 类只支持元素的顺序访问,但在 list 内部任何位置插入和删除元素都非常快速。

容器定义的操作非常少,只定义了构造函数、添加或删除元素的操作、设置容器长度的操作以及返回指向特殊元素的迭代器的操作。其他一些有用的操作,如排序、查找,则不是由容器类型定义,而是由标准算法定义。

priority_queue(优先级队列)

Adaptor for the sequential containers that yields a queue in which elements are inserted, not at the end but according to a specified priority level. By default, priority is determined by using the less-than operator for the element type.

一种顺序容器适配器。在这种队列中,新元素不是在队列尾部插入,而是根据指定的优先级级别插入。默认情况下,元素的优先级由元素类型的小于操作符决定。

stack(栈)Adaptor for the sequential containers that yields a type that lets us add and remove elements from one end only.一种顺序容器适配器,这种类型只能在一端插入和删除元素。

关联容器(Associative containers)支持通过键来高效地查找和读取元素。两个基本的关联容器类型是 map set。map 的元素以键-值(key-value)对的形式组织:键用作元素在 map 中的索引,而值则表示所存储和读取的数据。set 仅包含一个键,并有效地支持关于某个键是否存在的查询。

关联容器支持很多顺序容器也提供的相同操作,此外,还提供管理或使用键的特殊操作。

pair 包含两个数据值。与容器一样,pair 也是一种模板类型。但又与之前介绍的容器不同,在创建 pair 对象时,必须提供两个类型名:pair 对象所包含的两个数据成员各自对应的类型名字,这两个类型必相同。

关联容器共享大部分——但并非全部——的顺序容器操作。关联容器不提供 front、 push_front、 pop_front、back、push_back 以及 pop_back 操作。

“容器元素根据键的次序排列”这一事实就是一个重要的结论:在迭代遍历关联容器时,我们可确保按键的顺序的访问元素,而与元素在容器中的存放位置完全无关。

map 容器是键-值对的集合,好比以人名为键的地址和电话号码。相反地,set 容器只是单纯的键的集合。例如,某公司可能定义了一个名为 bad_checks 的 set 容器,用于记录曾经给本公司发空头支票的客户。当只想知道一个值是否存在时,使用 set 容器是最适合的。例如,在接收一张支票前,该公司可能想查询 bad_checks 对象,看看该客户的名字是否存在。

map 和 multimap 类型存储的元素是键-值对。它们使用在 utility 头文件中定义的标准库 pair 类,来表示这些键-值对元素。对 map 或 multimap 迭代器进行解引用将获得 pair 类型的值。pair 对象的 first 成员是一个 const 键,而 second 成员则是该键所关联的值。set 和 multiset 类型则专门用于存储键。在 map 和 set 类型中,一个键只能关联一个元素。而 multimap 和 multiset 类型则允许多个元素拥有相同的键。

关联容器的元素可用迭代器访问。标准库保证迭代器按照键的次序访问元素。begin 操作将获得拥有最小键的元素,对此迭代器作自增运算则可以按非降序依次访问各个元素。

pair Type that holds two public data members named first and second. The pair type is a template type that takes two type parameters that are used as the types of these members.一种类型,有两个 public 数据成员,分别名为 first 和 second。pair 类型是带有两个类型形参的模板类型,它的类型形参用作数据成员的类型。

除了模板形参表外,类模板的定义看起来与任意其他类问相似。类模板可以定义数据成员、函数成员和类型成员,也可以使用访问标号控制对成员的访问,还可以定义构造函数和析构函数等等。在类和类成员的定义中,可以使用模板形参作为类型或值的占位符,在使用类时再提供那些类型或值。

Queue qi;

编译器自动创建名为 Queue 的类。实际上,编译器通过重新编写 Queue 模板,用类型 int 代替模板形参的每次出现而创建 Queue 类。实例化的类就像已经编写的一样:

容器可以理解为特定的泛型数据结构与特定的泛型算法、特定的迭代器的组合

C++类模板实例化时为什么需要具体类型

类成员的泛类型;

typename这个关键字,它的作用同class一样表明后面的符号为一个类型,这样在定义模板的时候就可以使用下面的方式了: template.在模板定义语法中关键字class与typename的作用完全一样。

一个类模板(也称为类属类或类生成类)允许用户为类定义一种模式,使得类中的某些数据成员、默认成员函数的参数、某些成员函数的返回值,能够取任意类型(包括系统预定义的和用户自定义的)。

如果一个类中数据成员的数据类型不能确定,或者是某个成员函数的参数或返回值的类型不能确定,就必须将此类声明为模板,它的存在不是代表一个具体的、实际的类,而是代表着一类类。

类模板的使用实际上是将类模板实例化成一个具体的类,它的格式为:类名<实际的类型>.

函数模板可以用来创建一个通用的函数,以支持多种不同的形参,避免重载函数的函数体重复设计。它的最大特点是把函数使用的数据类型作为参数。

STL deque,double-ended queue,双端队列,可以实现队列两端快速插入和删除操作的功能;

map可以通过下标操作符直接存取元素。下标操作符并非元素整数位置,而是元素的键值key。

STL会提供适当的构造函数、普通成员函数、迭代器函数来进行构造、插入、删除、访问(查找)、修改数据元素的操作;

STL的算法函数设计,都使用模板来提供通用类型,都使用迭代器来提供访问容器中数据的通用表示。

仿函数:使用一个类(假设类名字是classname),好像调用一个函数。类的实现里包含函数operator(),之后这个类就有了类似函数的行为(使用类就如同调用operator()函数),这个类就是一个仿函数类。当使用类似函数调用形式classname()时,函数operator()被自动执行。

最简单的迭代器是指针。给定一个指向数组中的第一个元素的指针,可递增该指针使其指向下一个元素,还可直接对当前位置的元素进行操作。

STL中的迭代器是模板类,从某种程序上说,它们是泛型指针。这些模板类让程序员能够对STL容器进行操作。注意,操作也可以是以模板函数的方式提供的STL算法,迭代器是一座桥梁,让这些模板函数能够以一致而无缝的方式处理容器,而容器是模板类。

输入迭代器:通过对输入迭代器解除引用,它将引用对象,而对象可能位于集合中。最严格的输入迭代器确保只能以只读的方式访问对象。

迭代器的分类:输入、输出、前向、双向、随机访问五种,是只读、只写、递增操作、递减操作、加减偏移量操作的5个功能的叠加组合。

查找、排序、反转等都是标准的编程需求,不应让程序员重复实现这样的功能。因此STL以STL算法的方式提供这些函数,通过结合使用这些函数和迭代器,程序员可对容器执行一些最常见的操作。

简单地说,标准模板库(STL)是一组模板类和函数,向程序员提供了:

用于存储信息的容器;

用于访问容器存储的信息的迭代器;

用于操作容器内容的算法;

STL(Standard Template Library,标准模板库)是惠普实验室开发的一系列软件的统称。现然主要出现在C++中,但在被引入C++之前该技术就已经存在了很长的一段时间。

STL的从广义上讲分为三类:algorithm(算法)、container(容器)和iterator(迭代器),容器和算法通过迭代器可以进行无缝地连接。几乎所有的代码都采 用了模板类和模板函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中,STL被组织为下面的13个头文 件:<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack> 和<utility>。

STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念,但是这种分离确实使得STL变得非常通用。例如,在STL的vector容器中,可以放入元素、基础数据类型变量、元素的地址;STL的sort()函数可以用来操作vector,list等容器。

经典的数据结构数量有限,但是我们常常重复着一些为了实现向量、链表等结构而编写的代码,这些代码都十分相似,只是为了适应不同数据的变化而在 细节上有所出入。STL容器就为我们提供了这样的方便,它允许我们重复利用已有的实现构造自己的特定类型下的数据结构,通过设置一些模板,STL容器对最常用的数据结构提供了支持,这些模板的参数允许我们指定容器中元素的数据类型,可以将我们许多重复而乏味的工作简化。

在STL中,容器一般用模版类来实现。不过STL并没有采用面向对象的技术,所以在STL中并没有一个通用的容器类,各种具体的容器也没有统一的基类。

容器可以视为是数组的扩展,即对象的数组(广义数组),其中的元素(对象)通过容器对“[]”的重载,可以和数组一样利用下标(索引)来访问。

注意:STL中的容器可以包含的类型有内置的基本数据类型和带有公用拷贝构造函数和赋值操作符的类。

顺序容器,指的是将一组具有相同类型T的对象,以严格的线性形式组织在一起。顺序由容器可以视为数组和链表的推广。包括有以下3种顺序容器。

vector

deque

list

(2)关联容器,提供一个key(键)实现对元素的随机访问,其特点是key是有序的,即元素是按预定义的键顺序(例如升序)插入的。关联容器具有从基于键的集合中快速提取对象的能力,其中集合的大小在运行时是可变的。关联容器可以视为关联数组、映射或字典的推广,它们保存的都是键值对,给定了其中的一个被称为键(key)的值,就可以快速访问与其对应的另一个值的值。STL中的关联容器有以下4种。

set<Key>(集合): 支持唯一键值,并提供对键本身的快速检索;例如set<long>:{学号}(set类的头文件<set>);

multiset<Key>(多重集合):支持可重复键值,并提供对键本身的快速检索;例如set<string>:{姓名}(可能有同名的)(multiset类的头文件是<set>);

map<Key,T>:支持唯一Key类型的键值,并提供对另一个基于键的类型T的快速检索;例如map<long,string>:{(学号,姓名)}、{(电话号码,姓名)}等(map类的头文件是<map>);

multimap<Key,T>(多重映射):支持可重复Key类型的键值,并提供对另一个基于键的类型T的快速检索;例如map<string,string>:{(姓名, 地址)}、{(姓名, 年龄)}等(multimap类的头文件是<map>)。

除了这两种以外,还有一种容器是容器适配器。不过容器适配器不是独立的容器,只是某种容器的变种,它提供原容器的一个专用的受限接口。特别是,容器适配器和普通容器的不一样是在于不提供迭代器。在STL中有3种容器适配器,具体如下。

stack<T>(栈):只支持top()(读取栈顶元素)、push()(在栈顶处加入新元素)和pop()(取出栈顶元素)操作(先入后出)的一种序列容器。(stack类的头文件是);

queue<T>(队列):与stack类似,queue也是对序列容器的限制实现。与栈相比,队列也支持back()(读取队尾处的元素)和push_back()(在队尾处插入新元素)操作,但是不再支持pop_back()(取出队尾处的元素)操作。不过,队列允许front()(读取队首处的元素)和pop_front()(取出队首处的元素)操作(前出后入)。(queue类的头文文件是<queue>);

priority_queue<T>(优先队列):也是一种队列queue,不过其中的每个元素都被给定了一个优先级,用来控制元素到达队首top()的顺序。默认情况下,优先队列简单地使用运算符<进行元素比较,top()返回最大的元素。

注意:优先队列,并不要求其全部元素都是有序的,而只要求其第一个元素是最大的。

vector使用allocator来进行内存管理,使用3个迭代器来引用这段内存。vector的iterator其实就是T*的别名。在一个连续的内存里(数组),指针是可以做算术运算的,也支持[]操作,由此,vector的iterator也支持算术运算,++,--,+=,-=,[]。vector的迭代器就是通常的随机访问迭代器了。

Vector<T>容器表示一个在必要时可自动增加容量的数组,该数组存储T类型的元素。只能在矢量容器的末尾添加新元素。

aray<T,N>容器表示一个数组N,它存储指定数量的T类型元素。与普通数组相比,这个容器的一个优点是它知道其大小,所以把array<>容器传递给函数时,它仍知道所存储元素的个数。array<>容器优于vector<>的一个优点是,它可以完全在栈上分配内存,而vector<>总是需要访问堆。

deque<T>容器实现一个双端队列,它存储T类型的元素。它等价于一个矢量,但增加了向容器开头添加元素的能力。

list<T>容器是一个双向链表,它存储T类型的元素。

forward_list<T>容器是一个单向链表,它存储T类型元素。只要以前向方式处理链表中的元素,在forward_list<T>中插入和删除元素就比在list<T>中快。

map<K,T>是一个关联容器,用关联键(类型为K)存储T类型的每个元素。键/对象对在映射中存储为pair<K,T>类型的对象,pair<K,T>是另一个STL模板类型。键确定键/对象对的位置,用于检索对象。映射中的每个键必须唯一。这个头文件也定义了multimap<K,T>容器,其中键/对象对中的键不需要唯一。

大多数STL容器都会自动增大其容量来容纳所存储的元素。这些容器的附加内存用一个名为分配器的对象来提供,分配器一般会在需要时分配堆上的内存。这可以通过一个额外的类型形参,提供自己的分配器对象类型。例如,创建向量的vector<T>模板实际上是一个vector<T,A<T>>模板,其中的第二个类型参数A<T>就是分配器类型。第二个类型形参的默认值是allocator<T>,所以没有指定自己的分配器时,这就是所使用的分配器类型。

容器适配器是包装了现有STL容器类的模板类,提供了一个不同的、通常更有限制性的功能。

queue容器由deque容器中的适配器定义,但可以用list容器来定义它。只能访问队列中的第一个和最后一个元素,而且只能从后面添加元素,从前面删除元素。因此queue容器的运行过程或多或少就像我们在咖啡店排队一样。

stack容器用deque容器中的适配器定义,但可以用vector或list容器定义它。栈是一种后进先出容器,因此添加或删除元素总是发生在顶点,并且只能访问顶点的元素。

容器由怎样操作来定义,如怎样访问?怎样增加元素?怎样删除元素?怎样附加内存来增大容量由分配器来定义,存储何种类型由类型参数T来定义。

容器的遍历使用迭代器,迭代器都定义了==、!=、=等操作符,而不同的迭代器定义了其它不同的操作符,如++、--、*、--、+、-、<、[]等操作符。

1 元素数量弹性;(分配器实现内存增加)

2 元素类型参数化;(模板技术实现泛型)

3 算法独立于容器;(迭代器技术实现元素遍历)

三方面的泛化:

1 类型的泛化:模板技术让容器不局限于具体类型;

2 迭代器的泛化:迭代器是指针的泛化,如vector可以用指针实现迭代器,list可以通过类实现迭代器。迭代器的使用除了声明有所区别以外,其它方面基本一致,如:

vector::iterator pr;

//list::iterator pr;

for(pr=ins.begin(); pr != ins.end(); pr++)

{cout<<*pr<<endl}

3 算法的泛化:因为迭代器的泛化,可以让算法独立于具体的容器。也就是说,算法能够独立于具体的容器、独立于具体的类型。

The STL provides an alternative to arrays called the vector template class, and C++11 adds an array template class. These alternatives are more sophisticated and flexible than the built-in array composite type.

STL is a collection of useful templates for handling various kinds of container objects.

The StL exemplifies the programming paradigm called generic programming.

但如果站在代码重用的角度考虑,函数重载还是没有解决代码冗余的问题。因为重载的函数可以除了类型不同以外,剩下的函数名和函数体基本一样。这就是C++语言类型泛化的语法机制,用函数模板通过参数泛化在函数调用时由编译器去生成不同参数的函数。

STL算法是在一对迭代器指定的一个对象序列上操作的函数模板。

容器是一个存储和组织其他对象的类对象。序列容器用一个序列(如数组)存储对象。关联容器存储键/对象对的元素,其中键确定对存储在容器中的何处。

函数对象是重载()操作符(通过在类中实现函数operator()())的类型的对象。

编译器首先会为这一组重载函数中的每个函数取一个不同的内部名字。当发生函数调用时,编译器根据实际参数和形式参数的匹配情况确定具体调用的是那个函数,将这个函数的内部函数名取代重载的函数名。

如果一组重载函数仅仅是参数的类型不一样,程序的逻辑完全一样,那么这一组重载函数可以写成一个函数模版。

所谓的函数模版就是实现类型的参数化(泛型化),即把函数中某些形式参数的类型定义成参数,称为模版参数

在函数调用时,编译器根据实际参数的类型确定模版参数的值,生成不同的模版函数。

一 般的定义形式

template<类型形式参数表>
返回类型 FunctionName(形式参数表)
{
	//函数定义体
}
类型形式参数表可以包含基本数据类型,也可以包含类类型(需加前缀class)
template<class T>
T max(T a, T b)
{ return a>b ? a : b;}        

STL是用模板技术实现的数据结构和算法库。

vector容器相对于数组,在于其可以自动分配存储区和释放存储区,也就是相当于一个动态数组。

string、vector都是类,有重载构造函数,所以有多种初始化方式;

容器类函数一般可以分为以下几类:

1 构造类,构造函数有重载,所有有多种对象初始化方式;

2 迭代器函数:返回不同的迭代器,也就是指针指向不同的元素;

3 容量类函数,与size相关;

4 存取类,访问、查询相关;

5 操作类,增、删、改相关;

STL提供了大量的函数模板和类模板;

STL有助于提高算法和数据结构的重用性,将将开发者从这些通用而常见的问题中解放出来。STL提供的算法或数据结构在效率和性能上都是比较优秀的。

STL容器:数据存储方案及其对应操作;

STL容器的.begin()方法可以返回一个对应类型的迭代器,可以用此类型的迭代器被赋值。

vector vec;
vector::iterator itr = vec.begin();
for (vector::itertor itr = vec.begin(); itr != vec.end(); ++itr)
{
    cout<*itr<endl;
}

C++标准模板库里提供有3种顺序容器,vector以数组为基础,与数组不同的是,当内存不够时,vector会重新申请内存,把原来的数据复制到新的内存里面,并释放旧的内存区。list以双向链表为基础。

关联容器支持高效的关键字查找和访问。Map中的元素是关键字起到索引作用,值则表示和索引相关联的数据。而set中每个元素只包含一个关键字查询操作。