侯捷stl源码剖析注释之8 sgi-memory

57、什么是内存池，如何实现内存池（Memory Pool）是⼀种内存分配⽅式。

通常我们习惯直接使⽤new、malloc 等申请内存，这样做的缺点在于：由于所申请内存块的⼤⼩不定，当频繁使⽤时会造成⼤量的内存碎⽚并进⽽降低性能。

内存池则是在真正使⽤内存之前，先申请分配⼀定数量的、⼤⼩相等(⼀般情况下)的内存块留作备⽤。

当有新的内存需求时，就从内存池中分出⼀部分内存块，若内存块不够再继续申请新的内存。

这样做的⼀个显著优点是尽量避免了内存碎⽚，使得内存分配效率得到提升。

这⾥简单描述⼀下《STL源码剖析》中的内存池实现机制：allocate包装malloc,deallocate包装free⼀般是⼀次20*2个的申请，先⽤⼀半，留着⼀半，为什么也没个说法，侯捷在STL那边书⾥说好像是 C++委员会成员认为20是个⽐较好的数字，既不⼤也不⼩1. ⾸先客户端会调⽤malloc()配置⼀定数量的区块（固定⼤⼩的内存块，通常为8的倍数），假设40 个32bytes的区块，其中20个区块（⼀半）给程序实际使⽤，1个区块交出，另外19个处于维护状态。

剩余20个（⼀半）留给内存池，此时⼀共有（20*32byte）2. 客户端之后有有内存需求，想申请（20*64bytes）的空间，这时内存池只有（20*32bytes），就先将（10*64bytes)个区块返回，1个区块交出，另外9个处于维护状态，此时内存池空空如也3. 接下来如果客户端还有内存需求，就必须再调⽤malloc()配置空间，此时新申请的区块数量会增加⼀个随着配置次数越来越⼤的附加量，同样⼀半提供程序使⽤，另⼀半留给内存池。

申请内存的时候⽤永远是先看内存池有⽆剩余，有的话就⽤上，然后挂在0-15号某⼀条链表上，要不然就重新申请。

4. 如果整个堆的空间都不够了，就会在原先已经分配区块中寻找能满⾜当前需求的区块数量，能满⾜就返回，不能满⾜就向客户端报bad_alloc异常allocator就是⽤来分配内存的，最重要的两个函数是allocate和deallocate，就是⽤来申请内存和回收内存的，外部（⼀般指容器）调⽤的时候只需要知道这些就够了。

c++向量的用法C++中的向量（Vector）是一种动态数组，它能够自动调整大小以适应不同的元素数量。

向量属于标准模板库（Standard Template Library，STL）的一部分，它提供了许多方便的函数和操作符，用于方便地处理和操作元素。

下面将介绍向量的用法及相关参考内容。

1. 定义和初始化向量向量的定义需要包含<vector>头文件，并使用std命名空间。

我们可以使用以下方式来定义和初始化向量：```cpp#include <vector>#include <iostream>int main() {// 定义一个整数类型的向量std::vector<int> v1;// 定义一个浮点类型的向量，初始容量为10std::vector<float> v2(10);// 定义一个字符串类型的向量，并初始化为{"Hello", "World"}std::vector<std::string> v3{"Hello", "World"};// 定义一个空向量，并指定初始容量为5std::vector<char> v4(5, 'a');// 输出向量中的元素for (int i : v1) {std::cout << i << " ";}std::cout << std::endl;for (float f : v2) {std::cout << f << " ";}std::cout << std::endl;for (std::string str : v3) {std::cout << str << " ";}std::cout << std::endl;for (char c : v4) {std::cout << c << " ";}std::cout << std::endl;return 0;}```参考内容：- 《C++ Primer Plus》- 《C++标准库-深度剖析》，侯捷- 《C++标准库速查表》2. 向向量中添加元素向量提供了几个函数来添加元素：- push_back(value)：在向量的末尾添加一个元素；- insert(iterator, value)：在指定位置插入一个元素；- emplace(iterator, args...)：在指定位置使用参数构造一个元素；- insert(iterator, n, value)：在指定位置插入n个元素；- insert(iterator, first, last)：在指定位置插入另一个区间内的元素。

STL源码侯捷注释《STL源码侯捷注释》是一本经典的程序员必备书籍，它为广大程序员提供了深入了解STL源码的机会。

本文将从以下几个方面进行分析和评价。

一、作者介绍侯捷是一位著名的程序员和作家，他曾获得多项国际和国内大奖，包括ACM国际程序设计竞赛金牌、IBM杰出软件奖、国家自然科学二等奖等。

他还是多本计算机书籍的作者，如《STL源码剖析》、《C++程序设计》等。

二、书籍概述《STL源码侯捷注释》是一本详细介绍STL源码的书籍，它对STL的各个组成部分进行了详细的解析和注释。

本书的主要特点包括：1.详细的注释：本书对STL源码的每个细节都进行了详细的解释和注释，使读者能够深入了解STL的实现原理。

2.清晰的结构：本书按照STL源码的结构进行组织，并提供了详细的目录和索引，方便读者查找和理解。

3.丰富的例子：本书提供了大量的例子，帮助读者更好地理解STL的使用方法和实现原理。

4.全面的覆盖：本书覆盖了STL的所有组成部分，包括容器、迭代器、算法、仿函数等。

三、书籍优点1.深入浅出：本书的注释和解释非常详细，但又不失深入浅出的风格，使读者能够轻松理解STL的实现原理。

2.丰富的例子：本书提供了大量的例子，使读者能够更好地理解STL的使用方法和实现原理。

3.清晰的结构：本书按照STL源码的结构进行组织，并提供了详细的目录和索引，方便读者查找和理解。

4.全面的覆盖：本书覆盖了STL的所有组成部分，包括容器、迭代器、算法、仿函数等。

四、书籍不足之处1.过于复杂：本书注释和解释的内容非常详细，但有时候可能会让读者感到过于复杂和深入，不太适合初学者。

2.缺少实战案例：本书提供了大量的例子，但是缺少实战案例，读者可能需要自己去实践。

五、适合读者群体《STL源码侯捷注释》适合以下读者群体：1.对STL源码有兴趣的程序员。

2.希望深入了解STL实现原理的程序员。

3.希望提高自己的STL编程能力的程序员。

4.想要更好地掌握C++语言和STL的程序员。

侯捷老师——STL源码剖析侯捷老师是国内知名的C++专家，他在C++领域有着很高的知名度和影响力。

他的《STL源码剖析》是一本非常经典的C++书籍，深入剖析了C++标准模板库（Standard Template Library，STL）的源代码，并详细解释了其设计思想和实现细节。

下面是对这本书的1200字以上的介绍。

《STL源码剖析》是一本写给C++程序员的经典著作，它由侯捷老师亲自编写，内容非常详尽和深入。

这本书主要介绍了C++标准模板库（STL）的源代码，并解析了其中的设计思想和实现细节。

通过阅读这本书，读者可以更好地理解STL的底层原理，提高自己的C++编程能力。

这本书共分为13个章节，每个章节都涉及了STL的不同组件和特性。

书中的内容既包括理论知识，也包括具体的代码实现。

侯捷老师用通俗易懂的语言和形象生动的例子，对STL的各个组件进行了详细介绍。

他从容器、迭代器、算法和函数对象等方面入手，逐步展开对STL的剖析。

每一章的结尾都有相关的练习题，读者可以通过做题来巩固所学知识。

在《STL源码剖析》中，侯捷老师对STL的源代码进行了深入分析，解释了其中的设计思想和实现原理。

他通过对容器的底层结构和操作进行剖析，揭示了STL的高效性和灵活性。

在对算法和函数对象的讲解中，他详细介绍了STL中的各种常用算法，并解释了它们的内部实现原理。

通过这种深入的分析，读者可以更好地理解STL的运作机制，并能够灵活运用STL进行程序设计。

除了对STL源代码的剖析，侯捷老师还对STL的使用和扩展进行了说明。

他介绍了STL的使用注意事项和常见问题，并给出了一些实用的编程技巧和优化建议。

此外，他还展示了如何扩展STL，给出了一些自定义容器和算法的示例。

这些内容对于想要深入学习和应用STL的读者来说是非常有价值的。

总的来说，侯捷老师的《STL源码剖析》是一本非常权威和深入的C++书籍，对于想要深入学习STL的C++程序员来说是一本必读之作。

面向对象的理论与C++实践清华课程设计一、课程介绍面向对象的理论与C++实践是清华大学计算机科学与技术系本科生专业选修课程，涵盖面向对象编程理论和C++编程实践两个方面，旨在帮助学生深入理解面向对象思想并用C++语言进行实现。

二、课程内容面向对象编程理论1.面向对象思想概述2.类与对象3.继承、多态与虚函数4.抽象类与纯虚函数5.STL库简介C++编程实践1.C++程序设计基础2.类与对象的实现3.继承、多态与虚函数的实现4.STL库的使用三、课程教材《C++ Primer》（第五版）（中文版），作者：Lippman, Lajoie, Moo，译者：侯捷。

四、课程参考资料1.《Effective C++》（中文版），作者：Scott Meyers，译者：侯杰。

2.《STL源码剖析》（中文版），作者：侯捷。

3.《深入浅出设计模式》（中文版），作者：程杰。

五、课程设计要求1.选题要求：要求选好一个项目，体现应用面向对象编程的思想。

2.设计方案包括：给出所设计类的类体及成员函数原型，试画出相应的类图，写出内部数据结构方案的描述，描述各类或各函数功能作用的注释。

3.程序要求：为了反映面向对象编程语言的特征，要使用C++语言进行编程，采用面向对象思想，必须使用类和对象来体现程序设计思想，要充分利用C++语言的特性和STL库进行程序开发。

六、课程设计流程第一阶段：选题第一次课程上老师将介绍课程设计大概内容，学生需要结合个人实际情况，选定一个初步的设计主题，初步选题可与老师讨论资讯。

相当于开题选题环节。

第二阶段：设计方案在确定题目后，需要自己独立完成课程设计方案。

设计方案要求如上述第五部分所说明。

相当于中期论文。

第三阶段：实现程序在建立好方案后，开始进行程序实现。

实现过程中出现问题，需及时向老师或助教请教解决，最终提交实现代码。

相当于结题报告。

七、课程评分标准1.选题：选题是否合理，是否具有一定难度性；2.设计方案：方案是否完善，方案中的类设计是否具有标准性；3.程序代码：代码是否规范，是否达到良好的代码质量，代码是否具有可扩充性、可移植性等软件工程方面的优良特征；4.报告：书面报告是否符合规范，语言表达、图表使用是否得当；5.程序演示：演示时是否条理清晰，是否表现出更高的带了解问题以及解决问题的能力。

stl的使用介绍的书籍STL（Standard Template Library，标准模板库）是C++编程语言的一个重要组成部分，它为C++程序员提供了一套丰富的数据结构和算法，极大地提升了开发效率和代码的可重用性。

本文将介绍几本关于STL使用的优秀书籍，帮助读者更好地掌握STL的应用。

1.《Effective STL》《Effective STL》是Scott Meyers写的一本经典著作，旨在向读者展示如何高效地使用STL。

书中通过丰富的示例和详细的讲解，介绍了STL中各个容器、算法和迭代器的使用方法和注意事项。

同时，书中还提供了许多实用的技巧和技巧，帮助读者写出高质量的STL代码。

2.《STL源码剖析》《STL源码剖析》是侯捷教授编著的一本经典教材，深入剖析了STL 的实现原理和内部机制。

这本书不仅讲解了STL中各个容器和算法的实现细节，还介绍了STL的设计思想和优化技巧。

通过阅读本书，读者可以更好地理解STL的底层实现，提升自己的编程能力。

3.《C++标准库》《C++标准库》是Nicolai M. Josuttis撰写的一本权威性书籍，全面介绍了C++标准库，包括STL在内的各个组件。

书中详细讲解了STL中容器、算法、迭代器、函数对象等的使用方法，并给出了大量的示例代码。

此外，书中还介绍了C++11、C++14和C++17中新添加的特性，使读者了解最新的C++标准库开发技术。

4.《STL教程与案例精解》《STL教程与案例精解》是郝斌编著的一本教材，通过大量的案例和实例，系统地讲解了STL的使用方法和应用技巧。

书中从容器、迭代器、算法等方面入手，深入浅出地介绍了STL的各个组成部分，并提供了丰富的练习题和案例分析，帮助读者巩固所学知识。

5.《STL源码剖析与应用》《STL源码剖析与应用》是李师贺编著的一本专门讲解STL源码和应用的书籍。

书中详细解析了STL的设计思想、实现原理和内部机制，帮助读者深入理解STL的底层实现。

<std\> 完整列表 The Annotated STL Sources 1G++ 2.91.57，cygnus\cygwin-b20\include\g++\std\ 完整列表// Member templates for the -*- C++ -*- string classes.// Copyright (C) 1994 Free Software Foundation// This file is part of the GNU ANSI C++ Library. This library is free// software; you can redistribute it and/or modify it under the// terms of the GNU General Public License as published by the// Free Software Foundation ; either version 2, or (at your option)// any later version.// This library is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the// GNU General Public License for more details.// You should have received a copy of the GNU General Public License// along with this library; see the file COPYING. If not, write to the Free// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.// As a special exception, if you link this library with files// compiled with a GNU compiler to produce an executable, this does not cause // the resulting executable to be covered by the GNU General Public License. // This exception does not however invalidate any other reasons why// the executable file might be covered by the GNU General Public License.// Written by Jason Merrill based upon the specification by Takanori Adachi // in ANSI X3J16/94-0013R2.extern "C++" {template <class charT, class traits, class Allocator>inline void * basic_string <charT, traits, Allocator>::Rep::operator new (size_t s, size_t extra){return Allocator::allocate(s + extra * sizeof (charT));}template <class charT, class traits, class Allocator>inline void basic_string <charT, traits, Allocator>::Rep::operator delete (void * ptr){Allocator::deallocate(ptr, sizeof(Rep) +reinterpret_cast<Rep *>(ptr)->res *sizeof (charT));}template <class charT, class traits, class Allocator>inline size_t basic_string <charT, traits, Allocator>::Rep::frob_size (size_t s){<std\> 完整列表 The Annotated STL Sources 2 size_t i = 16;while (i < s) i *= 2;return i;}template <class charT, class traits, class Allocator>inline basic_string <charT, traits, Allocator>::Rep *basic_string <charT, traits, Allocator>::Rep::create (size_t extra){extra = frob_size (extra + 1);Rep *p = new (extra) Rep;p->res = extra;p->ref = 1;p->selfish = false;return p;}template <class charT, class traits, class Allocator>charT * basic_string <charT, traits, Allocator>::Rep::clone (){Rep *p = Rep::create (len);p->copy (0, data (), len);p->len = len;return p->data ();}template <class charT, class traits, class Allocator>inline bool basic_string <charT, traits, Allocator>::Rep::excess_slop (size_t s, size_t r){return 2 * (s <= 16 ? 16 : s) < r;}template <class charT, class traits, class Allocator>inline bool basic_string <charT, traits, Allocator>::check_realloc (basic_string::size_type s) const{s += sizeof (charT);rep ()->selfish = false;return (rep ()->ref > 1|| s > capacity ()|| Rep::excess_slop (s, capacity ()));}template <class charT, class traits, class Allocator>void basic_string <charT, traits, Allocator>::alloc (basic_string::size_type size, bool save)<std\> 完整列表 The Annotated STL Sources 3{if (! check_realloc (size))return;Rep *p = Rep::create (size);if (save){p->copy (0, data (), length ());p->len = length ();}elsep->len = 0;repup (p);}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>&basic_string <charT, traits, Allocator>::replace (size_type pos1, size_type n1,const basic_string& str, size_type pos2, size_type n2){const size_t len2 = str.length ();if (pos1 == 0 && n1 >= length () && pos2 == 0 && n2 >= len2)return operator= (str);OUTOFRANGE (pos2 > len2);if (n2 > len2 - pos2)n2 = len2 - pos2;return replace (pos1, n1, str.data () + pos2, n2);}template <class charT, class traits, class Allocator>inline void basic_string <charT, traits, Allocator>::Rep::copy (size_t pos, const charT *s, size_t n){if (n)traits::copy (data () + pos, s, n);}template <class charT, class traits, class Allocator>inline void basic_string <charT, traits, Allocator>::Rep::move (size_t pos, const charT *s, size_t n){if (n)<std\> 完整列表 The Annotated STL Sources 4 traits::move (data () + pos, s, n);}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>&basic_string <charT, traits, Allocator>::replace (size_type pos, size_type n1, const charT* s, size_type n2){const size_type len = length ();OUTOFRANGE (pos > len);if (n1 > len - pos)n1 = len - pos;LENGTHERROR (len - n1 > max_size () - n2);size_t newlen = len - n1 + n2;if (check_realloc (newlen)){Rep *p = Rep::create (newlen);p->copy (0, data (), pos);p->copy (pos + n2, data () + pos + n1, len - (pos + n1));p->copy (pos, s, n2);repup (p);}else{rep ()->move (pos + n2, data () + pos + n1, len - (pos + n1));rep ()->copy (pos, s, n2);}rep ()->len = newlen;return *this;}template <class charT, class traits, class Allocator>inline void basic_string <charT, traits, Allocator>::Rep::set (size_t pos, const charT c, size_t n){traits::set (data () + pos, c, n);}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>& basic_string <charT, traits, Allocator>:: replace (size_type pos, size_type n1, size_type n2, charT c){const size_t len = length ();OUTOFRANGE (pos > len);if (n1 > len - pos)n1 = len - pos;LENGTHERROR (len - n1 > max_size () - n2);<std\> 完整列表 The Annotated STL Sources 5size_t newlen = len - n1 + n2;if (check_realloc (newlen)){Rep *p = Rep::create (newlen);p->copy (0, data (), pos);p->copy (pos + n2, data () + pos + n1, len - (pos + n1));p->set (pos, c, n2);repup (p);}else{rep ()->move (pos + n2, data () + pos + n1, len - (pos + n1));rep ()->set (pos, c, n2);}rep ()->len = newlen;return *this;}template <class charT, class traits, class Allocator>void basic_string <charT, traits, Allocator>::resize (size_type n, charT c){LENGTHERROR (n > max_size ());if (n > length ())append (n - length (), c);elseerase (n);}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::copy (charT* s, size_type n, size_type pos) const{OUTOFRANGE (pos > length ());if (n > length () - pos)n = length () - pos;traits::copy (s, data () + pos, n);return n;}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::<std\> 完整列表 The Annotated STL Sources 6 find (const charT* s, size_type pos, size_type n) const{size_t xpos = pos;for (; xpos + n <= length (); ++xpos)if (traits::eq (data () [xpos], *s)&& traits::compare (data () + xpos, s, n) == 0)return xpos;return npos;}template <class charT, class traits, class Allocator>inline basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::_find (const charT* ptr, charT c, size_type xpos, size_type len){for (; xpos < len; ++xpos)if (traits::eq (ptr [xpos], c))return xpos;return npos;}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::find (charT c, size_type pos) const{return _find (data (), c, pos, length ());}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::rfind (const charT* s, size_type pos, size_type n) const{if (n > length ())return npos;size_t xpos = length () - n;if (xpos > pos)xpos = pos;for (++xpos; xpos-- > 0; )if (traits::eq (data () [xpos], *s)&& traits::compare (data () + xpos, s, n) == 0)return xpos;return npos;}template <class charT, class traits, class Allocator><std\> 完整列表 The Annotated STL Sources 7basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::rfind (charT c, size_type pos) const{if (1 > length ())return npos;size_t xpos = length () - 1;if (xpos > pos)xpos = pos;for (++xpos; xpos-- > 0; )if (traits::eq (data () [xpos], c))return xpos;return npos;}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::find_first_of (const charT* s, size_type pos, size_type n) const{size_t xpos = pos;for (; xpos < length (); ++xpos)if (_find (s, data () [xpos], 0, n) != npos)return xpos;return npos;}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::find_last_of (const charT* s, size_type pos, size_type n) const{if (length() == 0)return npos;size_t xpos = length () - 1;if (xpos > pos)xpos = pos;for (++xpos; xpos-- > 0;)if (_find (s, data () [xpos], 0, n) != npos)return xpos;return npos;}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::find_first_not_of (const charT* s, size_type pos, size_type n) const<std\> 完整列表 The Annotated STL Sources 8 {size_t xpos = pos;for (; xpos < length (); ++xpos)if (_find (s, data () [xpos], 0, n) == npos)return xpos;return npos;}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::find_first_not_of (charT c, size_type pos) const{size_t xpos = pos;for (; xpos < length (); ++xpos)if (traits::ne (data () [xpos], c))return xpos;return npos;}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::find_last_not_of (const charT* s, size_type pos, size_type n) const{if (length() == 0)return npos;size_t xpos = length () - 1;if (xpos > pos)xpos = pos;for (++xpos; xpos-- > 0;)if (_find (s, data () [xpos], 0, n) == npos)return xpos;return npos;}template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::find_last_not_of (charT c, size_type pos) const{if (length() == 0)return npos;size_t xpos = length () - 1;if (xpos > pos)xpos = pos;for (++xpos; xpos-- > 0;)if (traits::ne (data () [xpos], c))return xpos;<std\> 完整列表 The Annotated STL Sources 9return npos;}template <class charT, class traits, class Allocator>int basic_string <charT, traits, Allocator>::compare (const basic_string& str, size_type pos, size_type n) const{OUTOFRANGE (pos > length ());size_t rlen = length () - pos;if (rlen > n)rlen = n;if (rlen > str.length ())rlen = str.length ();int r = traits::compare (data () + pos, str.data (), rlen);if (r != 0)return r;if (rlen == n)return 0;return (length () - pos) - str.length ();}template <class charT, class traits, class Allocator>int basic_string <charT, traits, Allocator>::compare (const charT* s, size_type pos, size_type n) const{OUTOFRANGE (pos > length ());size_t rlen = length () - pos;if (rlen > n)rlen = n;int r = traits::compare (data () + pos, s, rlen);if (r != 0)return r;return (length () - pos) - n;}#include <iostream.h>template <class charT, class traits, class Allocator>istream &operator>> (istream &is, basic_string <charT, traits, Allocator> &s){int w = is.width (0);if (is.ipfx0 ()){register streambuf *sb = is.rdbuf ();s.resize (0);while (1)<std\> 完整列表 The Annotated STL Sources 10 {int ch = sb->sbumpc ();if (ch == EOF){is.setstate (ios::eofbit);break;}else if (traits::is_del (ch)){sb->sungetc ();break;}s += ch;if (--w == 1)break;}}is.isfx ();if (s.length () == 0)is.setstate (ios::failbit);return is;}template <class charT, class traits, class Allocator>ostream &operator<< (ostream &o, const basic_string <charT, traits, Allocator>& s) {return o.write (s.data (), s.length ());}template <class charT, class traits, class Allocator>istream&getline (istream &is, basic_string <charT, traits, Allocator>& s, charT delim) {if (is.ipfx1 ()){_IO_size_t count = 0;streambuf *sb = is.rdbuf ();s.resize (0);while (1){int ch = sb->sbumpc ();if (ch == EOF){is.setstate (count == 0? (ios::failbit|ios::eofbit)<std\> 完整列表 The Annotated STL Sources 11 : ios::eofbit);break;}++count;if (ch == delim)break;s += ch;if (s.length () == s.npos - 1){is.setstate (ios::failbit);break;}}}// We need to be friends with istream to do this.// is._gcount = count;is.isfx ();return is;}// static data member of class basic_string<>template <class charT, class traits, class Allocator>basic_string <charT, traits, Allocator>::Repbasic_string<charT, traits, Allocator>::nilRep = { 0, 0, 1, false };template <class charT, class traits, class Allocator>const basic_string <charT, traits, Allocator>::size_typebasic_string <charT, traits, Allocator>::npos ;} // extern "C++"。

STL source 1 G++ 2.91.57，cygnus\cygwin-b20\include\g++\memory 完整列表/** Copyright (c) 1997* Silicon Graphics Computer Systems, Inc.** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation. Silicon Graphics makes no* representations about the suitability of this software for any* purpose. It is provided "as is" without express or implied warranty.**/#ifndef __SGI_STL_MEMORY#define __SGI_STL_MEMORY#include <stl_algobase.h>#include <stl_alloc.h>#include <stl_construct.h>#include <stl_tempbuf.h>#include <stl_uninitialized.h>#include <stl_raw_storage_iter.h>// Note: auto_ptr is commented out in this release because the details// of the interface are still being discussed by the C++ standardization// committee. It will be included once the iterface is finalized.#if 0#if defined(_MUTABLE_IS_KEYWORD) && defined(_EXPLICIT_IS_KEYWORD) && \defined(__STL_MEMBER_TEMPLATES)__STL_BEGIN_NAMESPACEtemplate <class X> class auto_ptr {private:X* ptr;mutable bool owns;public:typedef X element_type;explicit auto_ptr(X* p = 0) __STL_NOTHROW : ptr(p), owns(p) {}auto_ptr(const auto_ptr& a) __STL_NOTHROW : ptr(a.ptr), owns(a.owns) {a.owns = 0;}template <class T> auto_ptr(const auto_ptr<T>& a) __STL_NOTHROW: ptr(a.ptr), owns(a.owns) {a.owns = 0;2STL source }auto_ptr& operator=(const auto_ptr& a) __STL_NOTHROW {if (&a != this) {if (owns)delete ptr;owns = a.owns;ptr = a.ptr;a.owns = 0;}}template <class T> auto_ptr& operator=(const auto_ptr<T>& a) __STL_NOTHROW {if (&a != this) {if (owns)delete ptr;owns = a.owns;ptr = a.ptr;a.owns = 0;}}~auto_ptr() {if (owns)delete ptr;}X& operator*() const __STL_NOTHROW { return *ptr; }X* operator->() const __STL_NOTHROW { return ptr; }X* get() const __STL_NOTHROW { return ptr; }X* release const __STL_NOTHROW { owns = false; return ptr }};__STL_END_NAMESPACE#endif /* mutable && explicit && member templates */#endif /* 0 */#endif /* __SGI_STL_MEMORY */// Local Variables:// mode:C++// End:。

SGISTL源码stl_vector.h分析前⾔vector 是最常⽤的 C++ 容器，其动态扩容的特性是普通数组不具备的，这⼤⼤增加了编程的灵活性。

虽然平时⽤ vector 很多，也能基本理解其原理，但⽆法从深层次理解。

直到研读了 vector 的源码，才能⽐较⾃信的说⾃⼰真正理解了 vector 的基本原理，正应了侯捷说的那句话：源码⾯前，了⽆密码。

我会写两篇⽂章分别分析泛化 vector 和针对 bool 类型的特化 vector（即是 bit_vector，位向量容器）。

本⽂将分析泛化的 vector 的源码。

vector概述vector 是动态扩容的连续数组。

普通数组是静态空间，⼀旦配置就⽆法改变，⽽ vector 是动态空间，其内部机制会⾃动扩充空间以容纳更多的元素。

其动态扩容的具体过程：当容器没有备⽤空间时，会开辟⼀块⼤⼩是原空间两倍的新空间，将数据从原空间复制到新空间并释放原空间。

因此，vector 提⾼了内存的合理利⽤和运⽤的灵活性，⽤户再也不⽤考虑数组的容量不⾜的问题。

vector部分源码本⽂分析的 vector 源码来⾃侯捷⽼师《STL源码剖析》⽤的 SGI-STL-v2.91 的版本。

其泛化版本的 vector 具体实现在 stl_vector.h ⽂件中，部分源码如下：// alloc 是 SGI STL 的空间配置器template<class T, class Alloc = alloc>class vector {public:typedef T value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type* iterator;typedef const value_type* const_iterator;typedef value_type& reference;typedef const value_type& const_reference;typedef size_t size_type;typedef ptrdiff_t difference_type;#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION //这⾥是反转迭代器，可先忽略typedef reverse_iterator<const_iterator> const_reverse_iterator;typedef reverse_iterator<iterator> reverse_iterator;#endifprotected:// simple_alloc 是 SGI STL 的空间配置器，是源码所有容器都使⽤这个接⼝typedef simple_alloc<value_type, Alloc> data_allocator;iterator start; //表⽰⽬前使⽤空间的头iterator finish; //表⽰⽬前使⽤空间的尾iterator end_of_storage; //表⽰⽬前可⽤空间的尾void insert_aux(iterator position, const T& x);void deallocate() {if(start)data_allocator::deallocate(start, end_of_storage - start);}void fill_initialize(size_type n, const T& value) {start = allocate_and_fill(n, value);finish = start + n;end_of_storage = finish;}public:iterator begin() { return start; }const_iterator begin() const { return start; }iterator end() { return finish; }const_iterator end() const { return finish; }reverse_iterator rbegin() { return reverse_iterator(end()); }const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}reverse_iterator rend() { return reverse_iterator(begin()); }const_reverse_iterator rend() const {return const_reverse_iterator(begin());}size_type size() const {return size_type(end() - begin());}size_type max_size() const {return size_type(-1) / sizeof(T);}size_type capacity() const {return size_type(end_of_storage - begin());}bool empty() const { return begin() == end(); }reference operator[](size_type n) {return *(begin() + n);}const_reference operator[](size_type n) const {return *(begin() + n);}vector() : start(0), finish(0), end_of_storage(0) {}vector(size_type n, const T& value) {fill_initialize(n, value);}vector(int n, const T& value) {fill_initialize(n, value);}vector(long n, const T& value) {fill_initialize(n, value);}explicit vector(size_type n) {fill_initialize(n, T());}vector(const vector<T, Alloc>& x) {start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end()); finish = start + (x.end() - x.begin());end_of_storage = finish;}template <class InputIterator>vector(InputIterator first, InputIterator last) :start(0), finish(0), end_of_storage(0){range_initialize(first, last, iterator_category(first));}~vector() {destroy(start, finish); //全局变量deallocate();}vector<T, Alloc>& operator=(const vector<T, Alloc>& x);void reverve(size_type n) {if (capacity() < n) {const size_type old_size = size();iterator tmp = allocate_and_copy(n, start, finish);destroy(start, finish);deallocate();start = tmp;finish = start + old_size;end_of_storage = start + n;}}reference front() { return *begin(); }const_reference front() const { return *begin(); }reference back() { return *(end() - 1); }const_reference back() const { return *(end() - 1); }void push_back(const T& x) {if (finish != end_of_storage) { //还有备⽤空间construct(finish, x); //全局函数++finish;} else//⽆备⽤空间insert_aux(end(), x); //成员函数，后续会分析}void swap(vector<T, Alloc>& x) {__STD::swap(start, x.start);__STD::swap(finish, x.finish);__STD::swap(end_of_storage, x.end_of_storage);}//和push_back差别不⼤，只是插⼊位置不⼀样，复杂⼀点iterator insert(iterator position, const T& x) {size_type n = position - begin();if (finish != end_of_storage && position == end()) {construct(finish, x);} elseinsert_aux(position, x);return begin() + n;}iterator insert(iterator position) {insert(position, T());}#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>void insert(iterator position, InputIterator first, InputIterator last){range_insert(position, first, last, iterator_category(first));}#endifvoid insert(iterator pos, size_type n, const T& x);void insert(iterator pos, int n, const T& x) {insert(pos, (size_type) n, x);}void insert(iterator pos, long n, const T& x) {insert(pos, (size_type) n, x);}void pop_back() {--finish;destroy(finish); //finish->~T 这⾥仅仅是调⽤指针finish所指对象的析构函数，不能释放内存 }iterator erase(iterator position) {//如果移除的不是最后⼀个元素if (position + 1 != end())copy(position + 1, finish, position); //全局函数--finish;destroy(finish);return position;}//移除半开半闭区间[first, last)之间的所有元素，last指向的元素不被移除iterator erase(iterator first, iterator last) {iterator i = copy(last, finish, first);//如果区间内元素的析构函数是trivial的，则什么也不做//如果区间内元素的析构函数是non-trivial的，则依序调⽤其析构函数destroy(i, finish);finish = finish - (last - first); //重新调整finishreturn first;}void resize(size_type new_size, const T& x) {if (new_size < size())erase(begin() + new_size, end());elseinsert(end(), new_size - size(), x);}void resize(size_type new_size) { resize(new_size, T()); }void clear() { erase(begin(), end()); }protected://配置空间并填满内容iterator allocate_and_fill(size_type n, const T& x) {iterator result = data_allocator::allocate(n);__STL_TRY{uninitialized_fill_n(result, n, x);return result;}__STL_UNWIND(data_allocator::deallocate(result, n));}template <class ForwardIterator>iterator allocate_and_copy(size_type n,ForwardIterator first, ForwardIterator last) {iterator result = data_allocator::allocate(n);__STL_TRY {uninitialized_copy(first, last, result);return result;}__STL_UNWIND(data_allocator::deallocate(result, n));}/***********************后⾯还有********************************/vector 迭代器vector 维护的是⼀个连续空间所以⽆论其元素的型别为何，普通指针就可以作为 vector 的迭代器⽽满⾜所有必要条件，因为 vector 迭代器所需要的操作⾏为，如 operator*，operator++，operator--，operator+，operator-，operator+=，operator-=，普通指针就具备，从上⾯的源码就可以看出，vector ⽤的迭代器就是普通指针。