模板和容器

95 阅读 0 评论 63 点赞

我是靠谱客的博主糟糕月光，最近开发中收集的这篇文章主要介绍模板和容器，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1. 什么是模板
模板定义：模板就是实现代码重用机制的一种工具，它可以实现类型参数化，即把类型定义为参数，从而实现了真正的代码可重用性。
我们知道，C++ 是一种“强类型”的语言，也就是说一个变量，编译器必须确切的知道它的类型，而模板就是构建在这个强类型语言基础上的泛型系统。
2. 模板的语法

模板函数
template < typename {类型参数名称}, [ int {Name}=...][, ...] > {函数定义}
模板类
template < typename ... , [ int {Name}=...] > class ...
模板的参数可以是类型，或者是一个 int 型的值（或者可以转换为int 型的，比如 bool）。
3. 模板的使用－－模板库只能通过头文件库的形式来提供

显式类型参数：
对于模板函数，在函数名后添加 < {类型参数表} >。例如：int z=max <int> ( x, y );
对于模板类，在类后添加 < {类型参数表} >

隐式类型参数：对于模板函数，如果类型参数可以推导，那么可以省略类型参数表，举个例子:
template < typename T >
T max( T a, T b )
{
return a < b ? b : a;
}
这个 max 函数就是一个模板函数，它可以传入一个 “类型”的参数，以便实现任意类型求最大值的效果。假设我们这样使用它：
int x=5, y=10;
int z=max <int>( x, y );
这时候发生了什么呢？我们传入的“类型参数”是int，因此编译器在编译这段代码时会使用 int 来构造一个新函数：
int max( int a, int b )
{
return a < b ? b : a;
}
后面的事就和编译普通的函数一样了，C++编译器继续使用强类型系统编译这个函数，由强类型系统来检查这个函数是否正确。

这个过程叫做模板的“特化”，它发生在编译期，当编译器发现模板函数、模板类被使用（注意，不是定义）的时候进行的。这个系统实际上比较像宏，但是比宏更为智能。很明显，编译器必须知道模板如何特化这个函数，因此模板函数的实现，必须在“使用点”之前，因此模板库只能通过头文件库的形式来提供。

//更为准确的解释 C++ Primer 3 10.5

C++支持两种模板编译模式包含模式Inclusion Model 和分离模式Separation Mode。

包含模式: 像内联函数那样将模板的说明和定义全部放在头文件中.

分离模式：将模板说明放在头文件中，但是将模板实现放在c文件中，但是需要加"export"关键字，告诉编译器在生成被其他文件使用的函数模板实例时可能需要这个模板定义。

可见使用包含模式比较简洁，所以推荐使用包含模式，将模板的说明和定义全部放在头文件中发布。除非出于软件商业化目的，不希望暴露模板定义代码给用户，需要采用分离模式。

4. 模板的类型推导－根据用户传送过来的行参推导
对于函数，编译器是知道传入参数的类型的，比如上面的max，max < ? >( x, y )，由于第一个参数 x 是 int 类型的，那么 ? 这里需要填写什么呢？我们可以很明显的推断出应该是 "int"，否则，后面的强类型系统将无法编译这个函数。编译器同样知道 x 的类型，因此它也能推导出“类型参数”，这时候我们调用时就可省略模板参数了。

这个推导是按顺序来的，因此如果上面的 y 是其他类型，? 仍然会被推导为 int，如果y无法隐性转换为int，强类型编译时就会报错。
5. 类型推导的隐式类型转换
在决定模板参数类型前，编译器执行下列隐式类型转换：
左值变换
修饰字转换
派生类到基类的转换
见《C++ Primer》（[注2]，P500）对此主题的完备讨论。
简而言之，编译器削弱了某些类型属性，例如我们例子中的引用类型的左值属性。举例来说，编译器用值类型实例化函数模板，而不是用相应的引用类型。
同样地，它用指针类型实例化函数模板，而不是相应的数组类型。
它去除const修饰，绝不会用const类型实例化函数模板，总是用相应的非const类型，不过对于指针来说，指针和 const 指针是不同的类型。
底线是：自动模板参数推导包含类型转换，并且在编译器自动决定模板参数时某些类型属性将丢失。这些类型属性可以在使用显式函数模板参数申明时得以保留。

6. 模板的实例化，特化

函数模板

实例化：函数模板指定了实际类型或值构造出独立的函数的过程，称为实例化，即模板的使用过程。模板的实例化可以通过隐式推导实现，也可以通过显示指定实现。

特化：我们并不总是能够写出对所有可能被实例化的类型都是最合适的函数模板在某些情况下，我们可能想利用类型的某些特性来编写一些比模板实例化的函数更高效的函数，这时，就为某种类型，显式定义模板的实现，成为显式特化，所以模板特还还是模板行为的定义过程。

#include <cstring>
// const char* 显式特化定义了max的字符串实现
typedef const char *PCC;
template<> PCC max< PCC >( PCC s1, PCC s2 )
{
return ( strcmp( s1, s2 ) > 0 ? s1 : s2 );
}

类模板

特化和部分特化

7. 仿函数
仿函数这个词经常会出现在模板库里（比如 STL），那么什么是仿函数呢？
顾名思义：仿函数就是能像函数一样工作的东西，请原谅我用东西这样一个代词，下面我会慢慢解释。
void dosome( int i )
这个 dosome 是一个函数，我们可以这样来使用它： dosome(5);
那么，有什么东西可以像这样工作么？

答案1：重载了 () 操作符的对象，比如：
struct DoSome
{
void operator()( int i );
}
DoSome dosome;
这里类(对 C++ 来说，struct 和类是相同的) 重载了 () 操作符，因此它的实例 dosome 可以这样用 dosome(5); 和上面的函数调用一模一样，不是么？所以 dosome 就是一个仿函数了。
实际上还有答案2：
函数指针指向的对象。
typedef void( *DoSomePtr )( int );
typedef void( DoSome )( int );
DoSomePtr *ptr=&func;
DoSome& dosome=*ptr;
dosome(5); // 这里又和函数调用一模一样了。
当然，答案3 成员函数指针指向的成员函数就是意料之中的答案了。
8. 仿函数的用处
不管是对象还是函数指针等等，它们都是可以被作为参数传递，或者被作为变量保存的。因此我们就可以把一个仿函数传递给一个函数，由这个函数根据需要来调用这个仿函数（有点类似回调）。
STL 模板库中，大量使用了这种技巧，来实现库的“灵活”。
比如：
for_each, 它的源代码大致如下：
template < typename Iterator, typename Functor >
void for_each( Iterator begin, Iterator end, Fucntor func )
{
for( ; begin!=end; begin++ )
func( *begin );
}
这个 for 循环遍历了容器中的每一个元素，对每个元素调用了仿函数 func，这样就实现了对“每个元素做同样的事”这样一种编程的思想。
特别的，如果仿函数是一个对象，这个对象是可以有成员变量的，这就让仿函数有了“状态”，从而实现了更高的灵活性。

模板用法：定义、使用示例

#include <iostream>
using namespace std;

template < typename A, typename B>
class test
{
public:
     test();
     ~test();
     int gX();
};

template < typename A, typename B>
test< A, B >::test()
{
}

template < typename A, typename B>
test< A, B >::~test()
{
}

template < typename A, typename B>
int test< A, B >::gX()
{
    cout<< sizeof(A)<<endl;
    cout<< sizeof(B)<<endl;
    return 0;
}

int main ( void )
{
test<int,char> x;
x.gX();
return 0;
}

/List.h///

#include <iostream.h>
template<class T>
class List
{
public:
List();
~List();
void Add(T&);
                                void Remove(T&);
T* Find(T&);
void PrintList();
protected:
struct Node{
Node* pNext;
                                                T* pT;
};
Node* pFirst;
};
template<class T>
List<T>::List()
{
pFirst = 0;
}
template<class T>
void List<T>::Add(T& t)
{
Node* temp = new Node;
temp->pT = &t;
temp->pNext = pFirst;
pFirst = temp;
}
template<class T>
void List<T>::Remove(T& t)
{
Node* q = 0;
if(*(pFirst->pT) == t)
{
q = pFirst;
pFirst = pFirst->pNext;
}
                 else
    {
for(Node* p = pFirst;p->pNext;p = pNext)
if(*(p->pNext->pT) == t)
{
q = p->pNext;
p->pNext = q->pNext;
break;
}
}
if(q)
{
                                delete q->pT;
delete q;
}
}
template<class T>
T* List<T>::Find(T& t)
{
for(Node* p = pFirst;p;p = p->pNext)
{
if(*(p->pT) == t)
return p->pT;
}
return 0;
}
template<class T>
void List<T>::PrintList()
{
for(Node* p = pFirst;p;p = p->pNext)
{
cout<<*(p->pT)<<" ";
}
cout<<endl;
}
template<class T>
List<T>::~List()
{
Node* p;
while(p = pFirst)
{
pFirst = pFirst->pNext;
delete p->pT;
delete p;
}
}

///List. c//

#Include list.h

void main()
{
List<float>floatList;
for(int i = 1;i<7;i++)
{
floatList.Add(*new float(i+0.6));
}
floatList.PrintList();
float b = 3.6;
float* pa = floatList.Find(b);
if(pa)
floatList.Remove(*pa);
floatList.PrintList();
}

Visual C++的模板和泛型如何配合使用
本篇教程来源于完全教程网原文链接：http://www.pcstu.com/program/Cjj/jc/20071027/61279.html

我将演示模板和泛型在何种情况下能配合使用，在何种情况下不能配合使用，并指明在 Visual C++ 2005 下当前模板实现方式的缺陷，以此来结束这一系列有关在 Microsoft .NET Framework 中进行泛型编程的专栏。

我选择通过讨论将标准模板库 (STL) 引入 .NET 的过程中进行的工作，来介绍这份材料。首先，我将回顾 STL 的基本元素，这样所有人都将站在同一起跑线上。

STL 的 CAI
有三个主要元素可用于标准模板库的设计：容器、算法和迭代器 (CAI)。

顺序容器

STL 矢量vector 和 List 类表示顺序容器。顺序容器保存第一个元素、第二个元素等等，直到最后一个元素。用程序来表示的函数参数列表通常作为包含字符串类型的元素的矢量来实现。例如：
以下是引用片段：
vector paramlist;

关联容器

Map 和 Set 类表示关联容器。关联容器支持快速查找。例如，Map 表示键/值对：键用于查找，而值表示存储和检索的数据。要表示电话号码簿，您需要声明一个带有字符串键和整数值的 Map：
以下是引用片段：
map phonedir;
多重映射可使单一键支持多个电话条目。

泛型算法

STL 还提供一个算法集，其中包含用于查找、排序、替换和合并的算法(可以对容器进行运算)。这些算法称为泛型算法，因为它们独立于正在其上进行运算的元素类型(例如整型、双精度类型或字符串类型)和包含元素的容器类型(例如无论容器是矢量、列表还是内置数组)。
泛型算法通过直接在容器上进行运算来实现容器独立性。程序不向算法传递容器，而是向它们传递标记了要通过其进行迭代的元素范围的迭代器对 (第一个, 最后一个]，其中最后一个元素充当终结标志或一个标记，以表明元素集之后的元素并将停止算法：
以下是引用片段：
sort( paramlist.begin(), paramlist.end() );
此处，begin() 和 end() 是所有 STL 容器提供的方法，会将迭代器返回到元素集第一个元素和位于末尾元素之后的元素。例如，看一下以下声明序列：

以下是引用片段：
void f()
{
int ia[4] = {21, 8, 5, 13 };
vector ivec( ia, ia+4 ); //将 ivec 初始化为 ia...
list ilist( ia, ia+4); //将 ilist 初始化为 ia ...
// ...
}
注意：ia+4 实际指向最后一个元素 (13) 之后的地址。使用 STL 的人们最初可能被这种区别所蒙蔽，例如，传递截止到 ia+3 处，这将使元素 13 不能包括在一系列值中。

迭代器

迭代器提供了一种统一且独立于类型的方式来访问、遍历和比较容器的元素。迭代器是一种类抽象，可以提供统一的指针操作(例如 ++、--、*、==、!=)，无论容器是内置数组、列表还是其他任何一致的 STL 容器：
以下是引用片段：
void f()
{
// 每次调用相同的泛型算法...
sort( ia, ia+4 );
sort( ivec.begin(), ivec.end() );
sort( ilist.begin(), ilist.end() );
}

在每个排序调用中(共三个)，结果序列理所当然是：5、8、13、21(Fibonacci 序列的第四个到第七个元素)。
现在，这只是一种对 STL 的理想化观点，并不能证明在正式约束和实际约束下实际可行。正式约束是指：不是所有的容器类型均支持所有算法运算。例如，Map 或 Set 不支持 random_shuffle，因为对元素进行的任何重新排序均违反容器类型，这就像将索引编入堆栈中将违反堆栈的语义特征一样。

更实际地说，通过泛型算法，使用排序或查找来获得 List 容器中的元素，比在矢量上进行同一运算更加费力。因此，List 容器类型提供了自己的比泛型算法更高效的类方法。同样，使用 List 容器类型的查找方法来查找 Map 元素，比使用查找算法(通过向算法传递 Map 的开始和结束迭代器及其键)更快捷。

大家可能会希望算法在所有容器上的执行效果都相同，但实际上，算法更适合在 Block 容器和内置数组，而不是在 List 容器和关联容器类型上使用。实际上，当我在 Bell 实验室与 Alex Stepanov 一起工作时，他就把泛型算法称为 Block 算法。

为 .NET 重新设计 STL
要将 STL 合并到 .NET 中，首先要将容器作为公共语言运行库 (CLR) 类型重新实现。出于多种原因，我在本文中不会进行深入的讨论。总之，最好使容器成为引用类而不是值类。例如：
以下是引用片段：
// 暂时简化声明...
template
ref class vector { ... };
template
ref class map { ... };

在本机 STL 中，所有容器都是非多态的。矢量的声明将给定实际矢量对象。示例如下：
以下是引用片段：
// 本机 STL 矢量
// ivec.empty() == true
// ivec.size() == 0
vector< int > ivec;
// ivec2.empty() == false
// ivec2.size() == 10
vector< int > ivec2( 10 );

但是在 C++/CLI 下声明引用类型时，将定义一个跟踪句柄(矢量本身位于托管的堆中)。默认情况下，句柄将设置为 nullptr。请查看图 1。

下一个设计要求是：使不支持模板的其他语言(例如 C# 和 Visual Basic?)能够使用容器。最简单的策略是：使模板容器实现一个或多个系统容器接口(分到两个命名空间中)，如图 2 中所示。

通常，您将希望同时支持收集和泛型接口，以使当前使用收集接口的客户端能够使用您的类型。以下是声明支持两种接口的方法：
以下是引用片段：
template
ref class vector :
System::Collections::ICollection,
System::Collections::Generic::ICollection
{ ... };

要实现系统收集命名空间的容器接口，还必须实现 IEnumerator 和 IEnumerator 的实例：
以下是引用片段：
generic
ref class vector_enumerator :
System::Collections::IEnumerator,
System::Collections::Generic::IEnumerator
{ ... };

实现系统容器接口的弊端是：虽然使得元素可用，但是无法操作 STL/CLR 类型的容器。因此，额外的设计支持还应该提供泛型阴影容器类型，以使其他语言可以使用实际的容器类型。有两个常规策略可以实现这种支持：Plauger 方式和 Tsao 方式(以两个主要设计师 P. J. Plauger 和 Anson Tsao 的姓名来命名)。
可以认为 Plauger 方式提供泛型阴影类型。也就是说，您将创建阴影泛型类(可以将其称为 generic_vector)。它包含矢量模板的副本。示例如下：
以下是引用片段：
generic
public ref class vector_generic
{
vector^ m_templ; // 哎呀...
public:
vector_generic( vector^ );
};

m_templ 声明行上的“哎呀”注释表示在 .NET 下对模板使用的约束。由于存在这种约束，您不能以泛型类型存储要求实例化的模板。这是因为，两个参数化类型功能的实例化时间不同。泛型由运行时来实例化;而模板由编译器来实例化。因此，模板可以包含泛型，而泛型不能包含模板。

Plauger 方式下的解决方案为：创建一个公共泛型接口，模板和泛型均通过该接口派生。有关示例，请参阅图 3。Tsao 方式下的解决方案是根据以下事实得出的：接口始终为模板容器(在特定程序集中实例化)的引用。因此，您只需提供一个接口并实现模板即可。泛型阴影类型将被消除。
以下是引用片段：
generic
interface class vector_interface :ICollection {...};
template
ref class vector :vector_interface, ICollection {...};

在任何情况下，除了那些使用程序集的人们以外，所有人都可以执行泛型实例而不是 STL/CLR 容器。这是因为，C++/CLR 下的模板不能成为公共程序集成员。下一部分中讨论了此问题。

模板为非公共程序集类型
要使 .NET 识别类型，它需要两个元素：程序代码(表示要转换为公共中间语言 (CIL) 的类型)和元数据(描述类型的详细信息)。不幸的是，模板此时还不能通过任何一个元素提供给 .NET。与析构函数一样，模板并不是为 .NET 而存在的。
.NET 仅能识别模板的具体实例; 而不能识别出它们是一种模板。例如，.NET 可以识别 vector 和 vector 的 CIL 和元数据，但是不能识别共享的模板矢量，CIL 和元数据都是该模板矢量的实例。这种不可识别性的副作用是，您不能辨别模板。也就是说，您不能询问 vector 实例：“您是模板吗?如果是，请把您的参数列表和类定义传递给我好吗?”
另一方面，泛型在 CLR 2.0 中直接支持 CIL，并且具有完全支持泛型反射的扩展反射命名空间。这是您在选择设计方式(在应用程序中使用模板还是泛型类型)时，应该考虑的一个方面。还应考虑是否需要跨程序集共享。模板不能跨程序集共享，而泛型可以。因此，如果跨程序集共享对您的设计非常重要，则应选择泛型类而不是模板类。否则，您将需要提供某种形式的公共接口，来实现跨程序集的共享，正如我所介绍的有关 STL/CLR 设计的内容。

模板不能跨程序集识别的原因是：.NET 具有一个包含其源的扩展类型概念。也就是说，在 .NET 下与在本机C++ 中不同，类型具有一个位置，在此位置名称可在共享的全局空间中自由浮动。这种全局名称混乱使得将各种组件合并到一个工作应用程序中非常困难。进一步的区别在于：命名空间将提供程序级别的解决方案，而为类型添加位置将提供程序集级别的解决方案。

也就是说，全局公共名称实际上由其程序集分配，从而避免在合并程序集时发生名称冲突。在 .NET 下，类型具有一个位置。这意味着，一个程序集的 vector 不会被识别为另一个程序集的相同 vector，因为类型已由单独的程序集名称标记。由于 CLR 提供的运行时实例化，泛型不会出现这种问题。

那么，既然存在这些约束，为什么我们还选择同时提供模板和 STL/CLR 呢?执行工作的C++ 程序员已建立起该库和现有代码体的专业知识。我们不仅希望提供现有代码的迁移路径，还希望提供现有专业知识的迁移路径。如果您以前在 C++ 编程过程中依靠 STL，则会感到在 .NET 下缺少 STL 是一种损失。而使用 STL/CLR 则不会这样。我后来听说，计划在 STL 完成后使其可以下载使用。

什么是模板、泛型(Generic)技术、STL，它们有什么关联

泛型技术是一种设计理念，是一种将具体数据类型参数化的思维模式；模板是实现这种理念的一个途径，一种方式； STL是标准模板库就是将各种函数用模板来实现的类库。

STL 容器,算法,迭代器总结

一、容器
作为STL的最主要组成部分－－容器，分为向量（vector），表(list)，映射(map)，多重映射(multimap), 集合(set)，多重集合(multiset), 队列（queue）, 双端队列(deque)，堆栈(stack)。
容器特性所在头文件
1向量vector－－利用连续的内存空间存储
相当与数组，快速的访问随机的元素，快速的在末尾插入元素，但是在序列中间岁间的插入，删除元素要慢，而且如果一开始分配的空间不够的话，有一个重新分配更大空间，然后拷贝的性能开销。

<vector> 对于小数据存储，即对象所占空间不大的情况下选择vecotor比较合适，如若对象size较大，还是利用列表使用指针操作效率更高。
2列表list
list 容器是一个双向链表, 除了实际的数据, 每个元素维持着两个分别指向下一个和上一个链表元素的指针,（每个元素间用链表相连）, 访问随机元素不如vector快，随机的插入元素比vector快，对每个元素分配空间，所以不存在空间不够，重新分配的情况。
<list>

3映射map

map 也叫关联数组associative array , 提供一个键/值对, 键用来索引, 而值用作被存储和检索的数据. map 中键/值对构成好比一个地址和电话号码以人名为键值,具有快速查找能力
<map>
多重集合multimap
比起映射，一个键可以对应多了值。具有快速查找能力
<map>

4集合set, 即一堆值的集合
与map相比, set 只是键的集合. 例如一个公司可能定义一个集合bad_checks 由在过去两年中有过不良账单的人名构成当只想知道一个值是会存在时set 是最合适的

另外, set内部元素唯一，用一棵平衡树结构来存储，因此遍历的时候就排序了，查找也比快的哦。但是它插入和删除操作的效率不高.

还有, set可以进行集合的各种操作（交并补等）
<set>
多重集合multiset
和集合基本相同，但可以支持重复元素具有快速查找能力
<set>

5队列queue
双队列，从前面或后面快速的插入与删除，直接访问任何元素
插入只可以在尾部进行，删除、检索和修改只允许从头部进行。按照先进先出的原则。
<queue>

双端队列deque
基本上与向量相同，唯一的不同是，其在序列头部插入和删除操作也具有常量时间复杂度
<deque>
6堆栈stack
堆栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则
<stack>
考虑到不同的实际需要，更主要的是效率的需要，我们可以选择不同的容器来实现我们的程序，以此达到我们提高性能的目的。这也是用好STL的一个难点，但这也是关键。
二、算法
算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。<algorithm>是所有STL头文件中最大的一个，它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。

<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。

<functional>中则定义了一些模板类，用以声明函数对象。
STL的算法也是非常优秀的，它们大部分都是类属的，基本上都用到了C＋＋的模板来实现，这样，很多相似的函数就不用自己写了，只要用函数模板就OK了。
我们使用算法的时候，要针对不同的容器，比如：对集合的查找，最好不要用通用函数find（），它对集合使用的时候，性能非常的差，最好用集合自带的find（）函数，它针对了集合进行了优化，性能非常的高。
三、迭代器
它的具体实现在<itertator> 中，我们完全可以不管迭代器类是怎么实现的，大多数的时候，把它理解为指针是没有问题的（指针是迭代器的一个特例，它也属于迭代器），但是，决不能完全这么做。
迭代器功能（Abilities Of Iterator Gategories）
输入迭代器 Input iterator

向前读 Reads forward istream

输出迭代器 Output iterator

向前写    Writes forward     ostream,inserter
前向迭代器   Forward iterator
向前读写       Read and Writes forward
双向迭代器      Bidirectional iterator
向前向后读写   Read and Writes forward and      backward    list,set,multiset,map,multimap
随机迭代器      Random access iterator
随机读写        Read and Write with random
access        vector,deque,array,string