798热心会员
798热心会员
微信二维码一、基本概念1.1 泛型程序设计C++ 语言的核心优势之一就是便于软件的重用，重用在两个方面有体现：面向对象的思想：继承和多态，标准类库 泛型程序设计(generic programming) 的思想： 模板机制，以及标准模板库 STL简单地说就是使用模板的程序设计法。将一些常用的数据结构(比如链表，数组，二叉树)和算法(比如排序，查找)写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合。有了STL，不必再写大多的标准数据结构和算法，并且可获得非常高的性能。1.2 STL中基本的概念容器： 可容纳各种数据类型的通用数据结构,是类模板迭代器： 可用于依次存取容器中元素，类似于指针算法： 用来操作容器中的元素的函数模板二、容器概述容器指可以用于存放各种类型的数据( 基本类型的变量，对象等)的数据结构，都是类模版,分为三种：顺序容器vector, deque,list 关联容器set, multiset, map, multimap 容器适配器stack, queue, priority_queue对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，有的容器本身就是排序的，所以，放入容器的对象所属的类，往往还应该重载 == 和 & 运算符。2.1 顺序容器顺序容器并非指容器内的元素是排序的，元素的插入位置同元素的值无关。有vector，deque，list 三种。vector 指动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成，在尾端增删元素具有较佳的性能(大部分情况下是常数时间)。头文件是& vector&&&deque指双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间)。&&list指双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。 不支持随机存取。&&2.2 关联容器关联容器有以下几个特点：元素是排序的 插入任何元素，都按相应的排序规则来确定其位置 在查找时具有非常好的性能 通常以平衡二叉树方式实现， 插入和检索的时间都是 O(log(N))有两类：set/multiset(头文件 & set&)set 即集合。 set中不允许相同元素， multiset中允许存在相同的元素。map/multimap(头文件 & map&)map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first,另一个名为second, map根据first值对元素进行从小到大排序，并可快速地根据first来检索元素。map同multimap的不同在于是否允许相同first值的元素2.3 容器适配器容器适配器有3类：stack、queue、priority_queue。stack指栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项(栈顶的项)。 后进先出。头文件是& stack&&&queue指队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。 先进先出。头文件是& queue&。&&priority_queue指优先级队列。最高优先级元素总是第一个出列。头文件是& queue&。2.4 成员函数顺序容器和关联容器中都有的成员函数：begin 返回指向容器中第一个元素的迭代器end 返回指向容器中最后一个元素后面的位置的迭代器rbegin 返回指向容器中最后一个元素的迭代器rend 返回指向容器中第一个元素前面的位置的迭代器erase 从容器中删除一个或几个元素clear 从容器中删除所有元素front :返回容器中第一个元素的引用back : 返回容器中最后一个元素的引用push_back : 在容器末尾增加新元素pop_back : 删除容器末尾的元素erase :删除迭代器指向的元素(可能会使该迭代器失效)，或删除一个区间，返回被删除元素后面的那个元素的迭代器三、迭代器3.1 基本概念迭代器用于指向顺序容器和关联容器中的元素，用法和指针类似，有const 和非 const两种。通过迭代器可以读取它指向的元素，通过非const迭代器还能修改其指向的元素。定义一个容器类的迭代器的方法可以是：容器类名::iterator 变量名;容器类名::const_iterator 变量名;访问一个迭代器指向的元素：* 迭代器变量名迭代器上可以执行 ++ 操作, 以使其指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，此时再使用它，就会出错，类似于使用NULL或未初始化的指针一样。3.2 迭代器示例#include#includint main() { //一个存放int元素的数组，一开始里面没有元素v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4);vector::const_ //常量迭代器for( i = v.begin();i != v.end();++i )cout && * i && &,&;cout &&vector::reverse_ //反向迭代器for( r = v.rbegin();r != v.rend();r++ )cout && * r && &,&;cout &&vector:: //非常量迭代器for( j = v.begin();j != v.end();j ++ )* j = 100;for( i = v.begin();i != v.end();i++ )cout && * i && &,&;}输出：1,2,3,4,4,3,2,1,100,100,100,100,3.3 迭代器类别3.3.1 双向迭代器若p和p1都是双向迭代器，则可对p、 p1可进行以下操作：++p, p++ 使p指向容器中下一个元素--p, p-- 使p指向容器中上一个元素* p 取p指向的元素p = p1 赋值p == p1 , p!= p1 判断是否相等、不等3.3.2 随机访问迭代器若p和p1都是随机访问迭代器，则可对p、 p1可进行以下操作：双向迭代器的所有操作p += i 将p向后移动i个元素p -= i 将p向向前移动i个元素p + i 值为: 指向 p 后面的第i个元素的迭代器p - i 值为: 指向 p 前面的第i个元素的迭代器p[i] 值为: p后面的第i个元素的引用p & p1, p &= p1, p & p1, p&= p13.3.3 容器和迭代器容器容器对应的迭代器vector随机访问deque随机访问list双向set/multiset双向map/multimap双向stack不支持迭代器queue不支持迭代器priotiry_queue不支持迭代器四、算法简介4.1 基本概念算法就是一个个函数模板, 大多数在& algorithm& 中定义。STL中提供能在各种容器中通用的算法，比如查找，排序等算法通过迭代器来操纵容器中的元素。许多算法可以对容器中的一个局部区间进行操作，因此需要两个参数，一个是起始元素的迭代器，一个是终止元素的后面一个元素的迭代器。比如，排序和查找。有的算法返回一个迭代器。比如 find() 算法，在容器中查找一个元素，并返回一个指向该元素的迭代器。算法可以处理容器，也可以处理普通数组。4.2 算法示例templateInIt find(InIt first, InIt last, const T& val);first 和 last 这两个参数都是容器的迭代器，它们给出了容器中的查找区间起点和终点[first,last)。区间的起点是位于查找范围之中的，而终点不是。 find在[first,last)查找等于val的元素用 == 运算符判断相等。函数返回值是一个迭代器。如果找到，则该迭代器指向被找到的元素。如果找不到，则该迭代器等于last。五、STL中&大&、&小&、&相等&的概念5.1 基本概念关联容器内部的元素是从小到大排序的有些算法要求其操作的区间是从小到大排序的，称为& 有序区间算法&例： binary_search 有些算法会对区间进行从小到大排序，称为&排序算法&例： sort 还有一些其他算法会用到&大&，&小&的概念使用STL时，在缺省的情况下，以下三个说法等价：x比y小 表达式& x & y&为真 y比x大关于&相等&：有时，& x和y相等&等价于& x==y为真&例：在未排序的区间上进行的算法，如顺序查找find&& 有时& x和y相等&等价于& x小于y和y小于x同时为假&例：有序区间算法，如binary_search关联容器自身的成员函数find&&5.2 程序示例#include#includclass A{public:A(int v):v(v) { }bool operator&(const A &a) const{cout&输出：3&9?2&9?1&9?9&1?1折半查找，最后找到1没有更多的可以找了。比较9是否小于1，结果为假;比较1是否小于9，结果为假;这时候认为9==1，输出1。六、小结STL 三个基本概念：容器、迭代器、算法 容器分为顺序容器、关联容器、容器适配器 顺序容器分为vector(动态数组)、deque(双向队列)、list(双向链表) 关联容器分为set/multiset、map/multimap 容器适配器stack、queue、priority_queue 迭代器分为双向迭代器、随机访问迭代器，不同的容器可以使用的迭代器类别不同 算法就是一个个函数模板, 大多数在& algorithm& 中定义 STL 中的&大&、&小&、&相等&等概念可以自己定义，可能和常规意义上的概念不同。就爱阅读网友整理上传,为您提供最全的知识大全,期待您的分享，转载请注明出处。
欢迎转载：
推荐： 　　　今天看啥 热点：
stl分析之allocator，stlallocatorallocator封装了stl标准程序库的内存管理系统，标准库的string，容器，算法和部分iostream都是通过allocator分配和释放内存的。标准库的组件有一个参数指定使用的allocator类，比如vector的原型是：
template&typename _Tp, typename _Alloc = std::allocator&_Tp& &
class vector : protected _Vector_base&_Tp, _Alloc&
第二个参数_Alloc指定使用的allocator，默认是std::allocator。我们也可以自己指定allocator
vector&int, __gnu_cxx::malloc_allocator&int& & malloc_
将使用malloc_allocator分配释放内存。GNU gcc实现了多种allocator，下面简单介绍几种allocator的作用，我的g++版本是4.8。1. new_allocator这是g++4.8默认使用的allocator，即 std::allocator使用的allocator，在头文件/usr/include/c++/4.8/bits/allocator.h中定义了 std::allocator：
template&typename _Tp&
class allocator: public __allocator_base&_Tp&
std::allocator使用的接口是由__allocator_base定义的，而后者在/usr/include/i386-linux-gnu/c++/4.8/bits/c++allocator.h定义为new_allocator：
# define __allocator_base
__gnu_cxx::new_allocator
new_allocator只是简单地包装::operator new和operator delete，实现在/usr/include/c++/4.8/ext/new_allocator.h
pointer allocate(size_type __n, const void* = 0)
if (__n & this-&max_size())
std::__throw_bad_alloc();
return static_cast&_Tp*&(::operator new(__n * sizeof(_Tp)));
deallocate(pointer __p, size_type)
{ ::operator delete(__p); }
并没有memory pool，所以现在如果还有程序因为使用了stl而出现内存没有回收的问题，那么一定是libc的cache没有释放，并不是stl的原因。
2. malloc_allocator malloc_allocator直接包装malloc和free，定义在/usr/include/c++/4.8/ext/malloc_allocator.h头文件中，
allocate(size_type __n, const void* = 0)
if (__n & this-&max_size())
std::__throw_bad_alloc();
pointer __ret = static_cast&_Tp*&(std::malloc(__n * sizeof(_Tp)));
if (!__ret)
std::__throw_bad_alloc();
deallocate(pointer __p, size_type)
{ std::free(static_cast&void*&(__p)); }
3. array_allocator array_allocator并不调用new或者malloc从操作系统申请分配内存，而是直接使用已分配的内存。通过使用该allocator可以重用内存，效率很高。
array_allocator(array_type* __array = 0) _GLIBCXX_USE_NOEXCEPT
: _M_array(__array), _M_used(size_type()) { }
Pointer allocate(size_type __n, const void* = 0)
if (_M_array == 0 || _M_used + __n & _M_array-&size())
std::__throw_bad_alloc();
pointer __ret = _M_array-&begin() + _M_
_M_used += __n;
return __ret，_M_used
_M_array指向已分配的内存块地址，_M_used指向空闲的地址位移，初始值为0，每分配一段内存后就将_M_used后移.当需要的内存量超出空闲内存大小时会抛出bad_alloc异常。
4. debug_allocator 可以包装任意其它的allocator，包括G++自带的或者用户自定义的，分配内存时多分配了一块内存保存申请的内存大小，释放时检查释放的内存大小是否和保存的值一样，不一样则抛出异常。具体的申请释放动作由被包装的allocator执行。
pointer allocate(size_type __n)
pointer __res = _M_allocator.allocate(__n + _M_extra);
size_type* __ps = reinterpret_cast&size_type*&(__res);
*__ps = __n;
return __res + _M_
void deallocate(pointer __p, size_type __n)
pointer __real_p = __p - _M_
if (*reinterpret_cast&size_type*&(__real_p) != __n)
throw std::runtime_error("debug_allocator::deallocate wrong size");
_M_allocator.deallocate(__real_p, __n + _M_extra);
throw std::runtime_error("debug_allocator::deallocate null pointer");
__ps中存储了当前申请分配的内存长度， deallocate时会检测释放的内存大小是否等于该值。debug_allocator可以检测内存是否存在泄露，代价是需要多分配用于debug的空间。
5. __pool_alloc 唯一一个带内存池的allocator，也是G++早期默认使用的allocator,侯捷的《stl源码剖析》第二章详细分析了其代码实现.原理就是为了减少内存碎片，当分配大于128byte的内存时直接调用operator new，而小于128byte的内存则从一个free list里面取，free list中的内存是可以重用的，程序运行期间不会归还给操作系统。过程比较复杂，有兴趣的同学可以参考《stl源码剖析》。
reference：https://gcc.gnu.org/onlinedocs/gcc-4.9.1/libstdc++/manual/manual/memory.html#std.util.memory.allocato
实例化的时候不需要自己定义allocator。如果你要自己编写allocator的话 1：没有必要 2.对于新手来说很复杂。 所以你直接用默认的就可以了。默认的allocator是一个模板，会自动的帮你替换成allocator&string&的，所以你不需要管。 想用字符串的向量直接：std::vector&std::string&就可以了。条款10：注意分配器的协定和约束分配器是怪异的。它们最初是为抽象内存模型而开发的，允许库开发者忽略在某些16位操作系统上near和far指针的区别（即，DOS和它的有害产物），但努力失败了。分配器也被设计成促进全功能内存管理器的发展，但事实表明那种方法在STL的一些部分会导致效率损失。为了避免效率冲击，C++标准委员会向标准中添加了词语，把分配器弱化为对象，同时也表达了他们不会让操作损失能力的希望。还有更多。正如operator new和operator new[]，STL分配器负责分配（和回收）原始内存，但分配器的客户接口与operator new、operator new[]甚至malloc几乎没有相似之处。最后（而且可能非常惊人），大多数标准容器从未向它们相关的分配器索要内存。从没有。结果分配器是，嗯，分配器是怪异的。当然，那不是它们的错，而且无论如何，这不意味着它们没用。但是，在我解释分配器好在哪里之前（那是条款11的主题），我需要解释它们哪里不好。有许多事情分配器好像能做，但不能，而且在你试图开始使用之前，知道领域的边界很重要。如果不，你将肯定会受伤。此外，关于分配器的事实如此独特，总结它的行为既有启发性又有趣。至少我希望是。分配器的约束的列表从用于指针和引用的残留typedef开始。正如我提到的，分配器最初被设想为抽象内存模型，在那种情况下，分配器在它们定义的内存模型中提供指针和引用的typedef才有意义。在C++标准里，类型T的对象的默认分配器（巧妙地称为allocator&T&）提供typedef allocator&T&::pointer和allocator&T&::reference，而且也希望用户定义的分配器也提供这些typedef。C++老手立即发现这有问题，因为在C++里没有办法捏造引用。这样做要求有能力重载operator.（“点操作符”），而那是不允许的。另外，建立行为像引用的对象是使用代理对象的例子，而代理对象会导致很多问题。（一个这样的问题产生了条款18。对代理对象的综合讨论，转向《More Effective C++》的条款30，你能知道什么时候它们工作什么时候不。)就STL里的分配器而言，没有任何代理对象的技术缺点会导致指针和引用typedef失效，实际上标准明确地允许库实现假设每个分配器的pointer typedef是T*的同义词，每个分配器的reference typedef与T&相同。对，库实现可以忽视typedef并直接使用原始指针和引用！所以即使你可以设法写出成功地提供新指针和引用类型的分配器的方法，也好不到哪里去，因为你使用的STL实现将自由地忽视你的typedef。很优雅，不是吗？当你钦佩标准化的怪癖时，我将再介绍一个。分配器是对象，那表明它们可能有成员功能，内嵌的类型和typedef（例如pointer和reference）等等，但标准允许STL实现认为所有相同类型的分配器对象都是等价的而且比较起来总是相等。很唐突，听起来并不可怕，而且对它当然有好的动机......余下全文>>
C++模板的声明你看到这个应该是STL中容器(vector, list)的代码这个模板包含两个模板参数，T 和 Allocator。其中 Allocator 有 缺省值，缺省为 allocator&T&allocator 也是一个模板，需要一个参数，你可以具体看它的定义，allocator&T& 为 模板allocator的实例。要想看懂STL，需要一定的模板功底，推荐阅读 《C++ Template》。
暂无相关文章
相关搜索：
相关阅读：
相关频道：
&&&&&&&&&&&&&&&&
C++教程最近更新