标准模板库（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 一样，也就是说它们应该 是 explicit instantiatedBjarne没有听进我的话，他设计了一个 template function 机制，其中的 template 是以一个多载化机制 （overloading mechanism 来进行implicitly instantiated这项特殊的技术对我的工作具有关键性的影响，因为我发现它使我得以完成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 (双端队列) | a vector with insertion/erase at the beginning or end in amortized constant time, however lacking some guarantees on iterator validity after altering the deque. | |
| Associative containers - 无序集 | ||
| set | a sorted set; inserting/erasing elements in a set does not invalidate iterators pointing in the set. Provides set operations union, intersection, difference, symmetric difference and test of inclusion. Type of data must implement comparison operator < or custom comparator function must be specified. Implemented using a self-balancing binary search tree. |
|
| multiset | 跟set具有相同功能，但允许重复的元素。 | |
| map | a sorted associative array; allows mapping from one data item (a key) to another (a value). Type of key must implement comparison operator < or custom comparator function must be specified. Implemented using a self-balancing binary search tree. |
|
| multimap | 跟map具有相同功能，但允许重复的键值。 | |
| hash_set hash_multiset |
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 | stores series of bits similar to a fixed-sized vector of bools. Also optimizes for space | |
| valarray | another C-like array like vector, but is designed for high speed numerics at the expense of some programming ease and general purpose use. It has many features that make it ideally suited for use with vector processors in traditional vector supercomputers and SIMD units in consumer-level scalar processors, and also ease vector mathematics programming even in scalar computers. | |
Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History