下载文档原格式
C++顺序容器基础知识总结0.前⾔本⽂简单地总结了STL的顺序容器的知识点。
⽂中并不涉及具体的实现技巧，对于细节的东西也没有提及。
⼀来不同的标准库有着不同的实现，⼆来关于具体实现《STL源码剖析》已经展⽰得全⾯细致。
所以本⽂仅仅是对容器基础知识的归纳。
⾄于容器提供的接⼝与使⽤实例，建议查取官⽅⽂档。
⽂章难免有错漏，希望指出。
1.容器概论容器，置物之所也。
像桶可装⽔，碗可盛汤，C++的容器，可以存储对象。
容器有多种，⽤来处理不同的元素操作诉求。
按照元素存储到容器中以及访问⽅式的差异，容器分为顺序容器与关联容器。
顺序容器也称为序列式容器。
序列式容器按元素插⼊的顺序存储元素，这些元素可以进⾏排序，但未必是有序的。
C++本⾝内置了⼀个序列式容器array（数组），STL另外提供了vector,list,forward_list,deque,stack,queue,priority-queue，string等等序列式容器。
所有的容器都是基于模板实现的，因为容器必须保证能装得下各种各样的类型。
其中，stack，queue都是基于deque来实现的，priority-queue基于heap来实现，从技术上来说它们属于容器适配器（adapter）。
其中array与forward_list是C++11添加的新容器类型。
2.std::array2.1.底层数据结构array的底层数据结构是固定数组。
与C-style的数组类似，它的⼤⼩在定义后就不能被改变。
由于array具有固定的⼤⼩，它不⽀持添加和删除元素或改变容器⼤⼩等其他容器拥有的操作。
在定义⼀个array容器的时候必须指定⼤⼩：Defined in header <array>template<class T,std::size_t N> struct array;2.2.内存分配策略在内存分配策略上，array也与C-style数组类似。
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++程序员来说是一本必读之作。
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:。
stl原理
STL原理是指标准模板库（Standard Template Library）的原理，它是一组C++模板类和函数的集合。
STL的目标是提供一套
通用的数据结构和算法，使得程序员能够更加高效地进行软件开发。
STL的核心思想是将数据结构和算法的实现与具体的数据类型无关，通过模板机制实现了数据结构和算法的高度通用性。
STL包括容器（containers）、算法（algorithms）和迭代器（iterators）三个主要组成部分。
容器是STL中最基本的概念，它相当于数据结构，提供了存
放数据的基本框架，包括vector、list、deque、set、map等等。
容器将数据的存储和访问进行了封装，提供了丰富的成员函数用于操作数据。
算法是STL中的核心，它提供了大量的基本算法，如排序、
查找、合并等等。
这些算法都是通过迭代器来操作容器中的元素，实现了算法和数据的解耦。
程序员可以直接使用这些算法，而无需关心具体的实现细节。
迭代器是STL中的另一个重要概念，它相当于指针，用于遍
历容器中的元素。
迭代器提供了类似指针的操作，如解引用、自增等，使得程序员可以通过迭代器来访问容器中的数据。
STL的原理可以总结为：通过使用模板机制，将数据结构和算法进行抽象和分离，使得程序员可以通过容器、算法和迭代器
来实现高效的数据处理。
STL的设计思想和实现方式为C++编程提供了很大的便利，使得开发人员可以更加专注于业务逻辑的实现。
stl标准库STL（Standard Template Library）标准库是C++语言中非常重要的一部分，它提供了一系列的通用模板类和函数，用于实现常见的数据结构和算法，为程序员提供了丰富的工具库，极大地提高了程序的开发效率和代码的重用性。
在本文中，我们将深入探讨STL标准库的相关内容，包括其基本组成、常用容器和算法等方面的内容。
STL标准库主要由三个组成部分构成，分别是容器（Containers）、算法（Algorithms）和迭代器（Iterators）。
容器是用来存放数据的数据结构，包括向量（vector）、链表（list）、队列（queue）、栈（stack）等；算法是对容器中的数据进行操作和处理的函数，包括排序、查找、遍历等；而迭代器则是用来遍历容器中的元素的工具，可以看作是指针的一种扩展。
在STL标准库中，最常用的容器包括向量（vector）、链表（list）、集合（set）、映射（map）等。
向量是一种动态数组，可以动态地增加和减少元素，非常适合于需要频繁插入和删除操作的场景；链表则是一种由节点组成的数据结构，可以快速地插入和删除元素，但查找元素的效率较低；集合是一种不允许重复元素的容器，适合于去重操作；映射是一种键值对的容器，可以快速地根据键查找对应的值。
除了常用的容器之外，STL标准库还提供了丰富的算法，包括排序算法（如快速排序、归并排序）、查找算法（如二分查找、线性查找）、遍历算法（如for_each、transform）等。
这些算法可以直接用于各种容器，极大地提高了程序的开发效率和代码的重用性。
在使用STL标准库时，我们通常会使用迭代器来遍历容器中的元素。
迭代器可以看作是一种指针，它指向容器中的某个元素，并可以通过自增、自减等操作来遍历容器中的所有元素。
通过迭代器，我们可以方便地对容器中的元素进行操作和处理。
总的来说，STL标准库是C++语言中非常重要的一部分，它提供了丰富的工具库，包括容器、算法和迭代器等，极大地提高了程序的开发效率和代码的重用性。
STL源码剖析（⼀）SLT简介STL（Standard Template Library），即标准模板库，是⼀个⾼效的C++程序库。
包含了诸多在计算机科学领域⾥常⽤的基本数据结构和基本算法。
为⼴⼤C++程序员们提供了⼀个可扩展的应⽤框架，⾼度体现了软件的可复⽤性。
其核⼼思想就是泛化编程（generic programming），在这种思想⾥，⼤部分基本算法被抽象，被泛化，独⽴于与之对应的数据结构，⽤于以相同或相近的⽅式处理各种不同情形。
STL组件STL中包含了6⼤组件容器（Containers）：包含各种基础的数据结构，如vector, list, deque, set, map等。
分配器（Allocators）：负责空间配置与管理。
算法（Algorithms）：各种常⽤的算法，如sort, search, copy, erase等等。
迭代器（Iterators）：负责连接Containers与Algorithms。
适配器（Adapters）：可以⽤来修饰Containers，Iterators和Functors接⼝的组件。
函数式（Functors）：类似于函数，可以作为Algorithms的⼀种策略。
六⼤组件的关系Containers 通过 Allocators 取得数据存储空间，Algorithms 通过 Iterators 存取 Containers 内容，Functors 可以协助 Algorithms 完成不同的策略变，Adapters 可以修饰或套接Containers，Iterators和Functors。
容器结构与分类容器总体上分为三⼤类：Sequence Containers(序列容器): Arrary（⼤⼩固定，⽆法⾃动扩充）, Vector（只可向后扩充, 两倍的扩展）, Deque（可向前或向后扩充, 分段连续, stack和queue都是基于此）, List（双向链表）, Forwaed-List（单向链表）Associative Containers(关联容器)：Set/Multiset, Map/Multimap（基本都⽤红⿊树来实现）Unordered Containers(⽆序容器): Unordered Set/Multiset, Unordered Map/Multimap（基本都是 HashTable Separate Chaining 实现）Array是⼀种固定⼤⼩的容器类型，在定义的时候就要声明⼤⼩和类型。
stl标准库STL（Standard Template Library）标准库是C++语言中的一个非常重要的组成部分，它为程序员提供了丰富的数据结构和算法，极大地提高了程序的开发效率和质量。
STL标准库包括了许多容器、迭代器、算法等组件，它们可以帮助程序员轻松地实现各种功能，从而简化了程序的开发过程。
本文将对STL标准库进行详细介绍，包括其组成部分、常用容器和算法等内容。
STL标准库的组成部分主要包括容器、迭代器、算法和函数对象。
容器是STL中最基本的组件，它用来存储数据，并提供了对数据的访问和操作接口。
常用的容器包括vector、list、deque、stack、queue、set、map等，它们分别对应了动态数组、链表、双端队列、栈、队列、集合和映射等数据结构。
迭代器是STL中用来遍历容器中元素的工具，它提供了统一的访问接口，使得程序员可以以统一的方式来访问不同类型的容器。
算法是STL中的另一个重要组件，它包括了大量的常用算法，如查找、排序、合并、删除等，可以直接应用于各种容器中的数据。
函数对象是STL中的一个重要概念，它是一种可调用对象，可以像函数一样被调用，通常用来作为算法的参数，用于指定算法的操作方式。
在STL标准库中，容器是其中最重要的部分之一。
vector是STL中最常用的容器之一，它是一个动态数组，可以根据需要动态扩展和收缩，非常适合于需要频繁插入和删除操作的场景。
list是另一个常用的容器，它是一个双向链表，可以快速地进行插入和删除操作，但在随机访问时性能较差。
deque是双端队列，可以在两端进行快速插入和删除操作，比vector和list都要高效。
除了这些基本容器外，STL标准库还提供了stack、queue、set、map等容器，它们分别对应了栈、队列、集合和映射等数据结构，可以满足不同场景下的需求。
除了容器外，STL标准库中的算法也是其核心部分之一。
STL中提供了大量的常用算法，如查找、排序、合并、删除等，它们可以直接应用于各种容器中的数据，极大地提高了程序员的开发效率。
<stl_slist.h> 完整列表 The Annotated STL Sources 1G++ 2.91.57，cygnus\cygwin-b20\include\g++\stl_slist.h 完整列表/** 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. **//* NOTE: This is an internal header file, included by other STL headers. * You should not attempt to use it directly.*/#ifndef __SGI_STL_INTERNAL_SLIST_H#define __SGI_STL_INTERNAL_SLIST_H__STL_BEGIN_NAMESPACE#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma set woff 1174#endif// 單向串列的節點基本結構struct __slist_node_base{__slist_node_base* next ;};// 全域函式：已知某一節點，安插新節點於其後。
inline __slist_node_base* __slist_make_link (__slist_node_base* prev_node, __slist_node_base* new_node){// 令 new 節點的下一節點為prev 節點的下一節點new_node->next = prev_node->next;prev_node->next = new_node; // 令 prev 節點的下一節點指向new 節點return new_node;}// 全域函式：找出某一節點的前一個節點。
inline __slist_node_base* __slist_previous (__slist_node_base* head,const __slist_node_base* node){<stl_slist.h> 完整列表The Annotated STL Sources 2 while (head && head->next != node) // 在單向串列中，只能採用循序搜尋法head = head->next;return head;}// 全域函式：找出某一節點的前一個節點。
const 版。
inline const __slist_node_base* __slist_previous (const __slist_node_base* head, const __slist_node_base* node) {while (head && head->next != node) // 在單向串列中，只能採用循序搜尋法head = head->next;return head;}// 全域函式：inline void __slist_splice_after (__slist_node_base* pos,__slist_node_base* before_first,__slist_node_base* before_last){if (pos != before_first && pos != before_last) {__slist_node_base* first = before_first->next;__slist_node_base* after = pos->next;before_first->next = before_last->next;pos->next = first;before_last->next = after;}}// 全域函式：inline __slist_node_base* __slist_reverse (__slist_node_base* node){__slist_node_base* result = node;node = node->next;result->next = 0;while(node) {__slist_node_base* next = node->next;node->next = result;result = node;node = next;}return result;}// 單向串列的節點結構template <class T>struct __slist_node : public __slist_node_base{T data;};<stl_slist.h> 完整列表 The Annotated STL Sources 3// 單向串列的迭代器基本結構struct __slist_iterator_base{typedef size_t size_type ;typedef ptrdiff_t difference_type ;typedef forward_iterator_tag iterator_category ; // 注意，是單向__slist_node_base* node ; // 指向節點基本結構__slist_iterator_base (__slist_node_base* x) : node (x) {}void incr () { node = node->next ; } // 前進一個節點bool operator==(const __slist_iterator_base& x) const {return node == x.node ;}bool operator!=(const __slist_iterator_base& x) const {return node != x.node ;}};// 單向串列的迭代器結構template <class T, class Ref, class Ptr>struct __slist_iterator : public __slist_iterator_base{typedef __slist_iterator<T, T&, T*> iterator ;typedef __slist_iterator<T, const T&, const T*> const_iterator ;typedef __slist_iterator<T, Ref, Ptr> self ;typedef T value_type ;typedef Ptr pointer ;typedef Ref reference ;typedef __slist_node<T> list_node ;__slist_iterator (list_node* x ) : __slist_iterator_base(x ) {}// 呼叫 slist<T>::end() 時會造成 __slist_iterator(0)，於是喚起上述函式。
__slist_iterator () : __slist_iterator_base(0) {}__slist_iterator (const iterator& x ) : __slist_iterator_base(x.node ) {}reference operator*() const { return ((list_node*) node)->data ; }#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }#endif /* __SGI_STL_NO_ARROW_OPERATOR */self& operator++(){incr (); // 前進一個節點return *this;<stl_slist.h> 完整列表The Annotated STL Sources 4 }self operator++(int){self tmp = *this;incr(); // 前進一個節點return tmp;}// 注意，沒有實作 operator--，因為這是一個 forward iterator// 注意，沒有實作 operator==。
於是將使用 __slist_iterator_base::operator==。
// 換句話說兩個 __slist_iterator 的比較，其實就是其底層的兩個 __slist_iterator_base // 的比較，而也就是比較其內的 __slist_node_base 指標是否相等。
};#if n def __STL_CLASS_PARTIAL_SPECIALIZATIONinline ptrdiff_t*distance_type(const __slist_iterator_base&){return 0;}inline forward_iterator_tagiterator_category(const __slist_iterator_base&){return forward_iterator_tag();}template <class T, class Ref, class Ptr>inline T*value_type(const __slist_iterator<T, Ref, Ptr>&) {return 0;}#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */// 全域函式：單向串列的大小（元素個數）inline size_t __slist_size (__slist_node_base* node){size_t result = 0;for ( ; node != 0; node = node->next)++result; // 累計return result;}// 單向串列template <class T, class Alloc = alloc >class slist{<stl_slist.h> 完整列表 The Annotated STL Sources 5public:typedef T value_type ;typedef value_type* pointer ;typedef const value_type* const_pointer ;typedef value_type& reference ;typedef const value_type& const_reference ;typedef size_t size_type ;typedef ptrdiff_t difference_type ;typedef __slist_iterator<T, T&, T*> iterator ;typedef __slist_iterator<T, const T&, const T*> const_iterator ;private:typedef __slist_node<T> list_node ;typedef __slist_node_base list_node_base ;typedef __slist_iterator_base iterator_base ;typedef simple_alloc <list_node , Alloc> list_node_allocator ;static list_node* create_node (const value_type& x) {list_node* node = list_node_allocator::allocate (); // 配置空間__STL_TRY {construct (&node->data, x); // 建構元素node->next = 0;}__STL_UNWIND(list_node_allocator::deallocate(node));return node;}static void destroy_node (list_node* node) {destroy (&node->data); // 將元素解構list_node_allocator::deallocate (node); // 釋還空間}void fill_initialize (size_type n, const value_type& x) {head.next = 0;__STL_TRY {_insert_after_fill(&head, n, x);}__STL_UNWIND(clear());}#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>void range_initialize (InputIterator first, InputIterator last) {head.next = 0;__STL_TRY {_insert_after_range(&head, first, last);}__STL_UNWIND(clear());<stl_slist.h> 完整列表The Annotated STL Sources 6 }#else /* __STL_MEMBER_TEMPLATES */void range_initialize (const value_type* first, const value_type* last) { head.next = 0;__STL_TRY {_insert_after_range(&head, first, last);}__STL_UNWIND(clear());}void range_initialize (const_iterator first, const_iterator last) {head.next = 0;__STL_TRY {_insert_after_range(&head, first, last);}__STL_UNWIND(clear());}#endif /* __STL_MEMBER_TEMPLATES */private:list_node_base head ; // 頭部。
