标准模板库

标准模板库（STL，即Standard Template Library），是一个C++软件库，也是C++标准程式库的一部分。

模板是C++程序设计语言的一个比较新的重要特征，而标准模板库（STL）正是基于此特征。标准模板库（STL）使得C++编程语言在有了同Java一样强大的类库的同时，保有了更大的可扩展性。

历史

STL系由Alexander Stepanov创造于1979年前后，这也正是Bjarne Stroustrup创造C++的年代。

虽然David R. Musser于1971开始即在计算机几何领域发展并倡导某些泛型程序设计观念，但早期并没有任何编程语言支援泛型程序设计。第一个支援泛型概念的语言是Ada Alex和Musser曾于1987开发出一套相关的Ada library.

STL之设计人——Stepanov的心路历程说起。他早期从事教育工作，1970年代研究泛型程序设计，那时他与其同事一起在GE公司开发出一个新的程序语言——Tecton。

1983 年，Stepanov先生转至Polytechnic大学教书，继续研究泛型程序设计，同时写了许多Scheme的程序，应用在graph与network的算法上，1985年又转至GE公司专门教授高阶程序设计，并将graph与network的Scheme程式，改用Ada写，用了Ada以后，他发现到一个动态(dynamically)类型的程序（如Scheme）与强制(strongly)类型的程序（如Ada）有多么的不同.

在动态类型的程序中，所有类型都可以自由的转换成别的类型，而强制类型的程序却不能。但是，强制类型在除错时较容易发现程序错误.

1988年Stepanov先生转至HP公司执行开发泛型程序库的工作。此时，他已经认识C语言中指针的威力，他表示一个程序员只要有些许硬件知识，就很容易接受C语言中指针的观念，同时也了解到C语言的所有数据结构均可以指针间接表示，这点是C与Ada、Scheme的最大不同.

Steepanov并认为，虽然C++中的继承功能可以表示泛型设计，但终究有个限制。虽然可以在基础类型(superclass)定义算法和接口，但不可能要求所有物件皆是继承这些，而且庞大的继承体系将减低虚拟(virtual)函数的执行效率，这便违反的前面所说的“效率”原则.

到了C++模版观念，Stepanov参加了许多有关的研讨会，与C++之父Bjarne讨论模版的设计细节。如，Stepanov认为C++的函数模版(function template)应该像Ada一样，在声明其函数原型后，应该显式的声明一个函数模版之实例(instance)；Bjarne则不然，他认为可以透过C++的多载(overloading)功能来表达。

Stepanov想像中的函数模版:

  in *.hpp
  template<class T>
  T square(T x) { return x*x; }

  in *.cpp
  double square(double);
  cout << square(3.3);
  int square(int);
  cout << square(3);

Bjarne认为的函数模版:

  in *.hpp
  template<class T>
  T square(T x) { return x*x; }

  in *.cpp
  cout << square(3.3);
  cout << square(3);

几经争辩，Stepanov发现Bjarne是对的（参考侯俊杰〈STL讲座·第三章〉）。事后Stepanov回想起来非常同意Bjarne的作法。

“

template 引数推导机制（arguments deduction ，在 STL中占非常重要的角色。Alexander Stepanov（STL 的创造者）在与Dr. Dobb's Journal进行的访谈中说道‘1992 我重回generic-library的开发工作。这时候C++有了template

我发现Bjarne完成了一个非常美妙的设计。之前我在Bell Lab曾参与数次template的相关设计讨论，并且非常粗暴地要求Bjarne应该将C++ template设计得尽可能像Ada generics那样。我想由于我的争辩是如此地粗暴，他决定反对。我了解到在C++中除了拥有template classes之外还拥有template functions的重要性。然而我认为template function应该像Ada generics一样，也就是说它们应该是显式实例，Bjarne没有听进我的话，他设计了一个template function机制，其中的template是以一个多载化机制（overloading mechanism来进行隐式实例这项特殊的技术对我的工作具有关键性的影响，因为我发现它使我得以完成Ada不可能完成的许多动作。我非常高兴Bjarne当初没有听我的意见。’（DDJ 1995 年三月号）

”

事实上，C++的模版，本身即是一套复杂的宏语言(macro language)，宏语言最大的特色为：所有工作在编译时期就已完成。显式的声明函数模版之实例，与直接透过C++的多载功能隐式声明，结果一样，并无很大区别，只是前者加重程序员的负担，使得程式变得累赘。

1992年Meng Lee加入Alex的专案，成为另一位主要贡献者。

1992年，HP泛型程序库计划结束，小组解散，只剩下Stepanov先生与Meng Lee小姐（她是东方人，STL的名称其实是取STepanov与Lee而来），Lee先前研究的是编译器的制作，对C++的模版很熟，第一版的STL中许多程式都是Lee的杰作。

1993年，Andy Koenig到斯坦福演讲，Stepanov便向他介绍STL，Koenig听后，随即邀请Stepanov参加1993年11月的ANSI/ISO C++标准化会议，并发表演讲。

Bell实验室的Andrew Koenig于1993年知道STL研究计划后，邀请Alex于是年11月的ANSI/ISO C++标准委员会会议上展示其观念。并获得与会者热烈的回应。

1994年1月6日，Koenig寄封电子邮件给Stepanov，表示如果Stepanov愿意将STL的说明文件撰写齐全，在1月25日前提出，便可能成为标准C++的一部份。Stepanov回信道："Andy, are you crazy?" 。 Koenig便说："Well, yes I am crazy,but why not try it?"。

Alex于是在次年夏天在Waterloo举行的会议前完成其正式的提案，并以百分之八十压倒性多数，一举让这个巨大的计划成为C++ Standard的一部份。

STL于1994年2月年正式成为ANSI/ISO C++的一部份，它的出现，促使C++程序员的思维方式更朝向泛型编程(generic program)发展.

内容

容器

STL 包含了序列容器（sequence containers）与关联容器（associative containers）。序列容器包含了 vector, deque 和 list。至于关联容器则有 set, multiset, map 和 multimap。

资料容器	描述
有序 / Lists - 有序集
vector	C++提供了内建阵列的替代型态vector，vector 可以如同阵列一样的存取方式，例如使用下标（Subscript）运算子，并记得自己的长度资讯（size），您也可以使用物件的方式来存取vector（push、pop）。使用vector可以轻易地定义二维可调整型阵列。要使用vector，必须含入vector表头档。
list	list容器是一个有序（Ordered）的数据结构（循序容器），其特性主要是实作串行数据结构。具有双向链结作用。
deque (双端队列)
Associative containers - 无序集
set
multiset	跟set具有相同功能，但允许重复的元素。
map
multimap	跟map具有相同功能，但允许重复的键值。
hash_set hash_multiset hash_map hash_multimap	similar as a set, multiset, map, or multimap, respectively, but implemented using a hash table; keys are not sorted, but a hash function must exist for key type. These containers are not part of the C++ Standard Library, but are included in SGI's STL extensions, and are included in common libraries such as the GNU C++ Library in the `__gnu_cxx` namespace. They may be included in future extensions of the C++ standard.
其他类型的容器
bitset
valarray

参见

C++标准程式库

外部链接

C/C++ reference includes a section on the STL
STL programmer's guide official guide from SGI
Bjarne Stroustrup on The emergence of the STL (Page 5, Section 3.1)
Apache stdcxx portable Open Source implementation based on Rogue Wave STL
STLport multiplatform STL implementation
Dinkumware commercial STL implementation (ships with Visual C++ and several other compilers)
Rogue Wave STL Class Reference
MPTL shared-memory parallel extension of the STL using the Native POSIX Thread Library.
STXXL: an STL implementation for external memory.
STLSoft libraries: open-source, 100% header-only, C/C++ libraries of technology-specific facades and STL extensions.

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History

标准模板库

目录

历史

内容

容器

参见

外部链接