STL 源代码分析笔记 (1)

分析笔记

C++ 是本人主要学习的编程语言,为了自己更深刻地了解 C++ 的底层机制,遂开此笔记,以记录学习、分析 STL 源代码的各个知识要点与关键技术原理。本笔记除了对书中、网络上各种文献的阅读理解与归纳概括之外,还包含了我本人的见解。对待技术道路上的难题与瓶颈,我的能力还远远不足以应对大多数情形,需要时刻保持空杯状态,并且花费更多时间在阅读、思考与不断的练习过程中,从而使得自己收获成长。同时,我会练习自己的写作技术,我的写作目标是使得整篇笔记成为可供同样还在学习 STL 核心技术的读者参阅的文档。要做到这一点,语言必须通俗易懂、令人拨云睹日,最好能配合图例,以图文并茂的形式展现出来。我会在书写分析笔记的时候尽可能周详地考虑以上要点。

参考资料与技术文献

本人在学习过程中,除了会参考互联网上已有的第三方文献之外,主要参考了 (参考的部分是书籍列表的子集) 以下书籍:

《STL 源代码剖析》 - 侯捷
《C++ 标准库 (第2版)》 - 尼古拉·约祖蒂斯 (Nicolai M.Josuttis), 侯捷(译)

以及以下来自互联网的在线文献:

SGI Standard Template Library Programmer's Guide

源代码的采用

STL 发展至今,有诸多版本的实现,为了能够简明扼要地了解 STL 的核心技术,避开细枝末节,本篇笔记采用 SGI-STL 3.3 版本的源代码,这份源代码貌似在互联网上作为学习的经典案例广为流传。然而,至少当我开始写笔记之时,SGI (Silicon Graphics Computer System, Inc) 公司官网已无法下载这份源代码包,其原有链接将发生页面重定向,貌似官方已经放弃维护此页面。因此,这里笔者是在一个镜像的归档网站获取到的一份拷贝,可以在下述链接所在的页面获取:

http://labmaster.mi.infn.it/Laboratorio2/serale/www.sgi.com/tech/stl/download.html

源代码头文件的前部包含了版权声明文字,HP 公司的版权声明之后还有 SGI 公司的版权声明,可见 SGI STL 是从 HP STL 发展而来。

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * 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.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996,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.
 */

在这份声明的后半部分,说明了此源代码的权限,允许用户免费使用、拷贝、修改、分发以及贩卖此源代码及文档。正因为这种伟大的开源精神,我们便能够学习、分析以及使用 SGI STL 的源代码。

C++ 编译器兼容性

从镜像网站的官方原文可以看出,SGI STL 库至少可以在 Visual C++ 5.0 编译器与 GNU C++ 2.8.1 编译器上成功通过编译,并且能够正常工作。

The STL was developed on SGI MIPSproTM C++ 7.0, 7.1, 7.2, and 7.2.1. If you are using the 7.0 compiler, you must compile using either the -n32 or the -64 flag; if you are using 7.1 or later, you may use -o32, -n32, or -64. The STL has also been tested on Microsoft Visual C++ 5.0, on g++ 2.8.1, and on recent egcs snapshots. All of the STL except for the , , and headers has also been tested on Borland 5.02.

引用自 http://labmaster.mi.infn.it/Laboratorio2/serale/www.sgi.com/tech/stl/download.html

不过,通过查阅相关资料可以得知,虽然 GNU C++ 编译器曾经将 SGI STL 库一并纳入自己的 C++ 标准库当中。但是,随着代码版本的更新迭代,其核心内容可能发生一些变化。这里笔者举出一个典型的例子,比如关于 allocator 的变化,这里有一篇博文详细地论述了相关内容,原文的引用链接如下:

SGI STL 核心代码文件

真正的 SGI STL 代码实现都包含在文件名以 stl_ 前缀开头的头文件当中,然后通过标准库或者与 HP STL 兼容 (标准化之前) 的接口封装起来。所以在全篇分析笔记中一般是分析来自上述头文件中的源代码。

stl_algo.h
stl_algobase.h
stl_alloc.h
stl_bvector.h
stl_config.h
stl_construct.h
stl_ctraits_fns.h
stl_deque.h
stl_exception.h
stl_function.h
stl_hashtable.h
stl_hash_fun.h
stl_hash_map.h
stl_hash_set.h
stl_heap.h
stl_iterator.h
stl_iterator_base.h
stl_list.h
stl_map.h
stl_multimap.h
stl_multiset.h
stl_numeric.h
stl_pair.h
stl_queue.h
stl_range_errors.h
stl_raw_storage_iter.h
stl_relops.h
stl_rope.h
stl_set.h
stl_slist.h
stl_stack.h
stl_string_fwd.h
stl_tempbuf.h
stl_threads.h
stl_tree.h
stl_uninitialized.h
stl_vector.h

STL 的六大组件

  • 容器 (containers): 各种数据结构,例如 vector,list,deque,set,map 之类。
  • 算法 (algorithms): 各种常用算法,例如 sort,search,copy,erase 之类,是以函数模板的形式存在的。
  • 迭代器 (iterators): 容器算法之间的胶合剂,包括泛型指针与原生指针在内。
  • 仿函数 (functors): 以类或者类模板的形式出现,并且重载 operator() 操作符,作为算法的某种策略 (policy),狭义上同时也包括函数指针在内。
  • (容器)适配器 (adapters): 用于修饰容器仿函数迭代器的接口,例如 queue 和 stack,其底层完全借助 deque 实现。
  • 配置器 (allocators): 用于内存空间的配置与管理。

adapter(s) 又译作配接器,allocator(s) 又译作分配器

六大组件的大致逻辑关系如图所示
QQ截图20201207165218.png

📅 更新时间:2021/10/17 Sunday 16:06

🖊️ 本文由 Alone Café 创作,如果您觉得本文让您有所收获,请随意赞赏 🥺
⚖️ 本文以 CC BY-NC-SA 4.0,即《署名-非商业性使用-相同方式共享 4.0 国际许可协议》进行许可
👨‍⚖️ 本站所发表的文章除注明转载或出处外,均为本站作者原创或翻译,转载前请务必署名并遵守上述协议
🔗 原文链接:https://alone.cafe/2020/12/stl源代码分析笔记1
📅 最后更新:2021年10月17日 Sunday 16:06

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×