标签：总结容器 const 迭代 iterator stl c++ vector type

前言

本篇是c++总结系列的stl篇，重点讲解容器，及effective stl的总结

stl原理

stl提供六大部件，这六大部件可以彼此搭配工作，这六大部件是：

容器。各种数据结构
迭代器。扮演容器和算法间的胶合剂，算法需要通过迭代器来对容器进行操作
算法
仿函数。行为类似函数，作为算法的某种策略
配接器。用于修饰容器、仿函数、迭代器接口.如stack，虽然看似容器，但却是一种容器配接器，它们的底部完全借助deque,操作都由deque供应
空间配置器。负责空间配置与管理.从实现的角度看，配置器是个实现了动态空间配置、空间管理、空间释放的class模板

六大部件的关系：

容器通过空间配置器取得数据存储空间
算法通过迭代器存取容器内容
仿函数可以协助算法完成不同的策略变化
配接器可以修饰或套接仿函数

空间配置器

空间配置器(allocator)为一个class, 用于管理 Type 类型的对象数组的存储分配和释放.所有 C++ 标准库容器均有默认为 allocator 的模板参数

为什么空间配置器是内存配置器的意思吗？并不是，因为空间不一定是内存，空间也可以是磁盘或其他辅助存储介质。也就是说，你甚至可以写个allocator向硬盘取空间

标准STL的allocator：

typedef
1. pointer。指向由allocator管理的对象类型的指针的类型
```
typedef value_type *pointer;
```
2. const_pointer。指向由allocator管理的对象类型的常量指针的类型
```
typedef const value_type *const_pointer;
```
3. reference。对allocator管理的对象类型的引用的类型
```
typedef value_type& reference;
```
4. const_reference。对allocator管理的对象类型的常量引用的类型
```
typedef const value_type& const_reference;
```
5. size_type。无符号整型类型，表示class allocator的对象分配的序列的最大长度
```
typedef size_t size_type;
```
6. value_type。由allocator管理的类型
```
typedef Type value_type;	//Type为模板参数类型
```
7. difference_type。有符号的整型，表示两个迭代器之间的距离,也就是同一个内存分配器分配出来的buffer首地址的偏移
```
typedef ptrdiff_t difference_type;
```
成员函数
1. 构造函数。用于创建allocator对象,构造函数并不执行其他任何操作
```
allocator();
allocator(const allocator<Type>& right);
template <class Other>
    allocator(const allocator<Other>& right);
```
2. 拷贝构造运算符。将一个分配器对象分配到另一个分配器对象
```
template <class Other>
    allocator<Type>& operator=(const allocator<Other>& right);
```
3. construct。在使用指定值初始化的指定地址处构造特定类型的对象
```
//ptr.指向要构造对象的位置的指针
//val.要进行初始化的要构造的对象的值
void construct(pointer ptr, const Type& val);	//等价于new ((void *) ptr) Type(val)
void construct(pointer ptr, Type&& val);
template <class _Other>
    void construct(pointer ptr, _Other&&... val);
```
4. destory。调用对象析构函数ptr->Type::~Type销毁由 ptr 指定的对象,而不释放存储对象的内存
```
void destroy(pointer ptr);
```
5. allocate。分配足以存储count个对象的空间.未分配内存，则指向分配的对象的指针或为 null
```
//_Hint 定位分配前的对象的地址,一般忽略它
pointer allocate( size_type _Count );	//实际上是调用_Allocate,再调用new,new调用malloc
pointer allocate(size_type count, const void* _Hint);
```
6. deallocate。从指定位置归还配置的空间。调用 operator delete(ptr)
```
void deallocate(pointer ptr, size_type count);
```
7. address.查找指定值的对象的地址
```
pointer address(reference val) const;
const_pointer address(const_reference val) const;
```
8. max_size。在可用内存用完之前，返回可以由allocator的对象分配的类型 Type 的元素数。也就是返回还未用的空间可以分配类型为Type的元素个数
```
size_type max_size() const;
```
9. rebind.使一种类型的对象allocator可以为另一种类型的对象分配空间
```
struct rebind { typedef allocator<_Other> other; };
```
  我们知道list的分配器为allocator<T>，但是list构造的对象是一个node，单使用allocator<T>，无法构造node；现在，rebind就发挥作用了，allocator<T>::rebind<node<T>>::other，在这里这个other就是allocator<node<T>>。也就是说，在一个容器内，allocator可以获取适合当前容器的分配器类型，只是分配的对象类型不同，但是策略是一样的。
  
  而且，allocator并不在意类型，只关系类型大小
其他函数
1. _Allocate()。allocate( size_type _Count )的调用实现，最终是调用malloc
```
inline T* _allocate(ptrdiff_t size, T*)
	{
		std::set_new_handler(0);
		T* tmp = static_cast<T*>(::operator new(sizeof(T) * size);
		if (tmp == 0)
		{
			std::cerr << " Failed to malloc ";
			exit(1);
		}
		return tmp;
	}
```
2. std::set_new_handler()。在throw异常的new版本中，若分配内存失败时会调用set_new_handler()。所属std namespace,如果 new 分配内存失败，则将控制权交给错误处理机制.也就是，设置new_p指向的函数为new操作或new[]操作失败时调用的处理函数
  1. 参数:
    1. new_p，所指的处理函数应为空参数列表且返回值类型为void;参数为空或0或nullptr则调用默认的处理函数，内存分配失败则抛出bad_alloc异常
  2. 返回值:
    1. 返回指向由 _set_new_handler 注册的上一个异常处理函数的指针，以便能还原上一个函数,类型为void*。如果之前没有设置函数，将返回空指针
  3. 值得注意的:
    1. 设置的处理函数可以尝试使更多空间变为可分配状态，这样新一次的new操作就可能成功。当且仅当该函数成功获得更多可用空间它才会返回；否则它将抛出bad_alloc异常（或者继承该异常的子类）或者终止程序（例如调用abort或exit）
    2. 若处理函数已经返回（如，该函数成功获得了更多的可用空间）,它可能将被反复调用，直到内存分配成功，或者它不再返回，或者被其它函数所替代
    3. 如果new_p是没有实现适当功能的函数指针（见上面的参数说明），或者如果new_p是无效的指针，它会导致未定义的行为
```
Typedef void  (*new_handler)();
new_handler  set_new_handler(new_handler  new_p) throw();//C++98
new_handler  set_new_handler (new_handler  new_p) noexcept;//C++11
```

SGI STL

不过在后面所用的都是SGI STL，它的内存空间的配置、释放和对象的构造、析构时分开的，且都为全局函数

SGI STL的空间配置器不再包装new/delete,而是直接调用malloc/free,分为两级配置器。考虑如下几点：

向system heap索要空间
考虑多线程
考虑内存不足时的应变措施
考虑过多"碎片化"问题

总体逻辑如下：

第二季配置器由一种free-lists实现，每次配置一大块内存,并维护对应的free-lists，若有对应大小的内存需求，则从free-lists索取；若返回内存块，这些内存块也有free-lists管理，且为了方便管理会进行边缘对齐上调至8的倍数

举个例子：客户端要求30bytes,则自动调整为32bytes,并维护16个free_lists，各自管理大小为8,16,24,32,40,48,56,64,72,80,,88,96,104,112,120,128 bytes的小区块

free-lists节点定义如下:

union obj
{
    union obj* free_list_link;
    char client_data[1];
}

当free-lists中没有可用区块，会调用refill()，从内存池取用( chunk-alloc()完成 )新的空间来填充free-lists

五种内存处理工具

uninitialized_copy()。将内存的配置和对象的构造分离，若输出范围[ result, result + ( last - first ) )的每个迭代器都指向未初始化区域，则uninitialized_copy()调用copy constructor，为范围内的每个位置构造一个复制对象。且此函数满足要么构造出所有必要元素，要么有一个构造失败则不构造任何对象

template< class InputIterator, class ForwardIterator >
inline ForwardIterator uninitialized_copy( InputIterator first, InputIterator last, ForwardIterator result )
{
    //用value_type()得出first的value_type
    return __uninitialized_copy( first, last, result, value_type(result) );
}

template< class InputIterator, class ForwardIterator, class T >
inline ForwardIterator __uninitialized_copy( InputIterator first, InputIterator last, ForwardIterator result, T* )
{
    //判断是否为标量类型或c风格struct，POD类型必然有无用的ctor/dtor/copy/assignment函数，需要对POD类型采用合适的最有效的初值填写方法;对non-POD类型采取最安全的做法
    using is_POD = typename __type_traits<T>::is_POD_type;	
    return __uninitialized_copy_aux( first, last, result, is_POD() );
}

//POD
template< class InputIterator, class ForwardIterator >
inline ForwardIterator __uninitialized_copy_aux( InputIterator first, InputIterator last,
                                                ForwardIterator result, __true_type )
{
    return copy( first, last, result );	//STL算法
}

//non-POD
template< class InputIterator, class ForwardIterator >
ForwardIterator __uninitialized_copy_aux( InputIterator first, InputIterator last,
                                               ForwardIterator result, __false_type )
{
    ForwardIterator cur = result;
    for( ; first != last; ++first, ++cur )
        constructor( &*cur, *first );	//一个一个构造
    return cur;
}

uninitialized_fill().将内存的配置和对象的构造分离,若输出范围[ first, last )的每个迭代器都指向未初始化区域，uninitialized_fill()会调用constrcutor( &*i, x )为范围内的每个位置构造一个复制对象.且此函数满足要么构造出所有必要元素，要么有一个构造失败则不构造任何对象

template< class ForwardIterator, class T >
inline void unitialized_fill( ForwardIterator first, ForwardIterator last, const T& x )
{
    //value_type()求得first的类型
    __unitialized_fill( first, last x, value_type(first) );
}

template< class ForwardIterator, class T, class T1 >
inline void __unitialized_fill(ForwardIterator first, ForwardIterator last, const T& x, T1* )
{
    using is_POD = typename __type_traits<T1>::is_POD_type;	
    __unitialized_fill_aux( first, last, x, is_POD() );
}

template<class ForwardIterator, class T>
inline void __unitialized_fill_aux( ForwardIterator first, ForwardIterator last, const T& x, __true_type )
{
    fill( first, last, x );	//STL算法
}

template<class ForwardIterator, class T>
void __unitialized_fill_aux( ForwardIterator first, ForwardIterator last, const T& x, __false_type )
{
    ForwardIterator cur = first;
    for( ; cur != last; ++cur )
        construct( &*cur, x );
}

uninitialized_fill_n().将内存的配置和对象的构造分离,若范围[ first, first + n )内的每个迭代器都指向未初始化区域，则此函数调用copy constructor( &*i, x )，为范围内的每个位置构造一个复制对象.且此函数满足要么构造出所有必要元素，要么有一个构造失败则不构造任何对象

template<class ForwardIterator, class Size, class T >
inline ForwardIterator uninitialized_fill_n( ForwardIterator first, Size n, const T& x )
{
    //用value_type()取出first的value_type
    return __uninitialized_fill_n( first, n, x, value_type( first ) );
}

//__uninitialized_fill_n定义如下
inline ForwardIterator __uninitialized_fill_n( ForwardIterator first, Size n, const T& x, T1* )
{
    using is_POD = typename __type_traits<T1>::is_POD_type;		
    return __uninitialized_fill_n_aux( first, n, x, is_POD() );
}

//is POD
template<class ForwardIterator, class Size, class T>
inline ForwardIterator __uninitialized_fill_n_aux( ForwardIterator first, Size n, const T& x, __true__type )
{
    return fill_n( first, n, x );	//STL算法
}

//non-POD
template<class ForwardIterator, class Size, class T>
ForwardIterator __uninitialized_fill_n_aux( ForwardIterator first, Size n, const T& x, __false__type )
{
    ForwardIterator cur = first;
    for( ; n > 0; --n, ++cur )
        constructor( &*cur, x );
    return cur;
}

之前提到的construct()
之前提到的destory()

总体逻辑如下：

迭代器

迭代器(iterator)行为类似智能指针，不需要我们手动进行delete，离开作用域会自行释放内存

每一种容器都有专属的迭代器，否则会暴露实现细节

算法运用迭代器时，需要用到相应参数的类型，这时我们可以通过模板推导对应类型；但对于返回值却无法推导，因此需要声明类型成员;看起来没问题了，但对于普通指针不是class，则此法不行，针对这个我们需要设计偏特化版本

template<class T>
struct MyIter
{
    using value_type = T;
    T*ptr;
    //...
}

template<class T>
typename T::value_type func( T ite )	//typename告诉编译器这是一个类型，因为编译器对T一无所知
{
    return *ite;
}

//针对普通指针
template<class T>
class C{ ... };

template<class T>
class C<T*>{ ... };		//针对普通指针的偏特化版本

萃取机(traits)可以提取迭代器特性

template<class T>
struct iterator_traits
{
    using value_type = typename T::value_type;	//如果T有value_type,萃取T的value_type
};
//偏特化版本.针对普通指针
template<class T>
struct iterator_traits<T*>
{
    using value_type = T;
}

//改写上个例子
template<class T>
typename iterator_traits<T>::value_type func( T ite )
{
    return *ite;
}

迭代器分类：

input iterator.迭代器所指对象为只读
output iterator.迭代器所指对象为只写
forward iterator.迭代器所指对象允许读写
bidirectional iterator.可双向移动
random access iterator.涵盖指针只有算数能力

这五类关系如下：

最常用的迭代器的类型有五类:

template<class Category, class T, class Distance = ptrdiffer_t, class Pointer = T*, class Reference = T&>
struct iterator
{
    using iterator_category = Category;
    using value_type = T;
    using difference_type = Distance;
    using pointer = Pointer;
    using reference = Reference;
}
template<class Iterator>
struct iterator_traits
{
    using iterator_category = typename Iterator::iterator_category;
    using value_type = typename Iterator::value_type;
    using difference_type = typename Iterator::difference_type;
    using pointer = typename Iterator::pointer;
    using reference = typename Iterator::reference;
}

value type.迭代器所指对象的类型

difference_type.两个迭代器之间的距离

template<class T>
struct iterator_traits
{
    using difference_type = typename T::difference_type;
};

template<class T>
struct iterator_traits<T*>
{
    using difference_type = ptrdiff_t;
};

template<class T>
struct iterator_traits<const T*>
{
    using difference_type = ptrdiff_t;
}

reference type 和 pointer type

template<class T>
struct iterator_traits
{
    using reference = typename T::reference;
    using pointer = typename T::pointer;
};

template<class T>
struct iterator_traits<T*>
{
    using pointer = T*;
    using reference = T&;
};

template<class T>
struct iterator_traits<const T*>
{
    using pointer = const T*;
    using pointer = const T&;
}

iterator category.根据移动特性于实行操作的迭代器种类

input iterator.迭代器所指对象为只读
output iterator.迭代器所指对象为只写
forward iterator.迭代器所指对象允许读写
bidirectional iterator.可双向移动
random access iterator.涵盖指针所有算数能力

//以advance()算法为例，迭代器p前进n距离
//有三个定义:input iterator、bidirectional iterator、random access iterator
//选择迭代器种类时，在可行的基础上重点考虑效率。可以看出选input版本的时间复杂度为O(n);而random虽然复杂度为O(1),但没有只读属性。因此需要按需选择
//一般而言有如下设计
template<class InuputIterator, class Distance>
void advance( InputIterator& i, Distance n )
{
    if( is_random_access_iterator(i) )
        advance_RAI(i, n);	//假设设计了一份Random版本
    else if( is_bidirectional_iterator(i) )
        advance_BI(i, n);	//假设设计了一份bid版本
    else
        advance_II(i, n);	//假设设计了一份input版本
}
//这个方案虽然可行，但在执行期决定对应版本会影响效率。按理说设计三个重载版本，应该可行；但是这是模板啊，类型是不确定的

//可行的方案：函数再加上一个迭代器种类的tag
//以下tag只用作标记，因此不需要任何成员
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag{};
struct bidirectional_iterator_tag{};
struct random_access_iterator_tag{};

template<class InputIterator, class Distance>
inline void __advance( InputIterator& i, Distance n, input_iterator_tag )
{
    while(n--) ++i;
}

template<class ForwardIterator, class Distance>
inline void __advance( ForwardIterator& i, Distance n, forward_iterator_tag )
{
    _advance(i, n, input_iterator_tag() );
}

template<class BidiectionalIterator, class Distance>
inline void __advance( BidiectionalIterator& i, Distance n, bidirectional_iterator_tag )
{
    if( n >= 0 ) 
        while(n--) ++i;
    else
        while(n++) --i;
}

template<class RandomAccessIterator, class Distance>
inline void __advance( RandomAccessIterator& i, Distance n, random_access_iterator_tag )
{
    i += n;
}

//定义一个上层函数调用对应的重载版本，因此上层函数需要借助traits推导出对应迭代器类型
template<class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n)
{
    __advance( i, n, iterator_traits<InputIterator>::iterator_category() );
}

为支持以上行为，traits需再加一个相应的类型:

template<class T>
struct iterator_traits
{
    using iterator_category = typename T::iterator_category;
}

template<class T>
struct iterator_tratis<T*>
{
    using iterator_category = random_access_iterator_tag;
}

template<class T>
struct iterator_traits<const T*>
{
    using iterator_category = random_access_iterator_tag;
}

容器

总览图：

顺序容器

顺序容器意为可序，未必有序。其中c++提供array，stl提vector、list、deque、stack、queue、priority-queue等；其中stack和queue称为配接器以deque为底层实现而来

顺序容器操作

除array外，所有stl容器都提供灵活的内存管理，可动态地添加或删除对象来改变容器大小

顺序容器操作原理和名称基本一样

添加元素

添加元素会改变容器大小，不适用于array

forward_list有自己独有的insert、emplace版本,且不支持push_back,emplace_back

vector和string不支持push_front、emplace_front

emplace_back和push_back的区别在于：push_back需要先构造一个对象，然后再复制放入容器内；而emplace_back只需要构造然后移动进容器，减少了复制拷贝的操作，效率更高，也就是所谓的移动拷贝函数。其他操作同理。也就是说c++11的元素操作函数基本都有两个版本

//尾部插入一个值为t的元素或对象
void push_back( t );
void emplace_back( t );	

//头部插入一个值为t的元素或对象
void push_front( value_type&& t );
void emplace_front( t );

//在迭代器p指向的位置之前插入一个值为t创建的元素或对象
//返回指向新添加元素的迭代器
iterator insert( iterator p, t );
iterator emplace( p, t );

//在迭代器p指向的位置之前插入一个值为t创建的元素或对象
//返回指向新添加元素的迭代器
//若n为0，返回p
iterator insert( iterator p, size_type n, value_type& t );

//将迭代器b和e指定范围内的元素插入到迭代器p指向的元素之前
//返回指向新添加元素的迭代器
//b和e不能指向 p指向的容器。若范围为空，则返回p
iterator insert( iterator p, iterator b, iterator e );

//il为{}，将il里的给定值插入到迭代器p指向的元素之前
//返回指向新添加的第一个元素的迭代器
//若il为空，则返回p
iterator insert( iterator p, initializer_list il );

访问元素

若容器没有元素，访问操作的结果是未定义

顺序容器都支持front()，array亦是如此；forward_list不支持back()

at()和operator[]只适用于string、vector、deque、array

//返回尾元素的引用
//容器为空，则行为未定义
reference back();

//返回首元素的引用
//容器为空，则行为未定义
reference front();

//返回容器中下标为n的元素或对象的引用
//若 n >= size() ，则行为未定义
reference operator[]( size_type n );

//返回下标为n的元素或对象的引用
//若下标越界，则抛出异常
reference at( size_type n );

删除元素

删除元素会改变容器大小，不适用array

forward_list有特殊版本的erase,不支持pop_back

vector、string不支持pop_front

//删除末尾元素
//若容器为空，则行为未定义
void pop_back();

//删除首元素
//若容器为空，则行为未定义
void pop_front();

//删除迭代器p所指定元素或对象
//返回指向被删除元素后一位元素的迭代器
//若p指向尾部元素，则返回尾后迭代器；若p为尾后迭代器，则未定义
iterator erase( iterator p );

//删除迭代器b和e范围内的元素或对象
//返回指向最后一个被删除元素之后的元素的迭代器
//若e为尾后迭代器，则也返回尾后迭代器
iterator erase( iterator b, iterator e );

//删除容器中所有元素或对象
void clear();

vector

vector与array有相似之处在于数据安排与操作方式；不同之处在于空间运用的灵活性，array是静态空间，一旦配置后便无法变大或变小，想要完成这个目的需要重新配置一块新空间，再把旧空间的元素一个一个复制过来。而vector是动态空间，随着元素的加入，它会自行扩充空间以容纳新元素

vector重点实现

templeta<class T,class Alloc=alloc> 
class vector { 
public:
    //嵌套类型或关联类型
	typedef T value_type; 
    typedef value_type *pointer; 
    typedef value_type &reference; 
    typedef value_type *iterator; 	
    typedef size_t size_type; 
    typedef ptrdiff_t difference_type;
    
protected:
    //空间配置器
	typedef simple_alloc <value_type, Alloc> data_alloctor 

    iterator start; 
    iterator finish; 
    iterator end_of_storage;
    
    //vector的自动扩容函数
	void insert_aux(iterator position, const T &x);
	
    //析构实现
	void data_allocator::deallocate(start, end_of_storage)；
        
   	//构造实现
	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; };
	iterator end() { return finish; };
    //已用空间
	size_type size() const { return size_type(end() - begin()); };
    //vector容量，可使用空间
	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); };
	vector() : start(0), end(0), end_of_storage(0) {};
	vector(size_type n, const T &value)(fill_initialize(n, value););
	vector(long n, const T &value)(fill_initialize(n, value););
	vector(int n, const T &value)(fill_initialize(n, value););
	explicit vector(size_type n) { fill_initialize(n, T()); };
    ~vector() 
    {
		destory(start, finish);	//全局函数
		deallocate();	//成员函数
	}
    
	//重要函数
    reference front() { return *begin(); };
	reference back() { return *(end() - 1); };
	void push_back(const T &x) 
    {
		if (finsih != end_of_storage) 
        {
			construct(finish, x);
			++finish;
		} 
        else insert_aux(end(), x);
	}
    
	void pop_back() 
    {
		--finish;
		destory(finish);
	}
    
	iterator erase(iterator position) 
    {
		if (position + 1 != end())
		copy(position + 1, finish, position);
		--finish;
		destory(finish);
		return position;
	}
    
	void resize(size_type new_size, const T &x) 
    {
		if (new_size() < size())
		erase(begin() + new_size, end());
		else
		insert(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); 
        uninitialized_fill_n(result, n, x);//全局函数
        return result;
	}
}

底层实现

vector在堆中分配连续的内存空间存放对象
迭代器类别
1. start.指向vector目前使用空间的起始位置
2. finish.指向vector目前使用空间的末尾位置
3. end_of_storage:指向vector目前可用空间(最大容量)的末尾位置
普通指针亦可充当迭代器
数据结构

vector采用的是线性连续空间.为降低配置空间的速度成本，vector实际配置的大小比需求更大，此之谓容量
扩容

若vector的容量已满，新增对象之前，首先需要分配一块更大的内存(不是在原空间后接续新空间),再将原来空间上的对象复制过来，释放原来的空间，最后再插入新增对象

一旦引起空间配置，指向旧vector的所有迭代器都要失效

当size() = capacity()相等时，vector就需要扩容，capacity翻倍

两种自动扩容方式:
1. 固定扩容
  1. 实现方式：每次扩容时，在capacity基础上加上固定容量
  2. 优点：空间利用率高
  3. 缺点：时间复杂度高。有些情况比较极端，若每次扩容固定增加容量为1，会导致每添加一次元素就需要扩容一次，而扩容消耗时间的代价很高
2. 加倍扩容
  1. 实现方式：每次扩容时，原capacity翻倍
  2. 优点：时间复杂度低。减少扩容次数
  3. 缺点：空间利用率低
vector采用加倍扩容

手动扩容:

resize(len):改变当前容器含有对象的个数
1. 若len > capacity()，则size和capacity设为len
若len <= capacity()，则size设为len,capacity不变

reserve(len):改变当前容器的可用空间
1. 若len > capacity(),则重新分配可存len个对象的空间，再把之前空间上的对象复制过来，回收之前的空间
2. 若len <= capacity(),则size不变和capacity不变

构造与内存管理

当使用push_back()在尾端插入元素时，函数首先检查是否还有备用空间，有则构造对象并调整迭代器finish;没有则扩充空间

实现如下：

void push_back( const T& x )
{
    if( finish != end_of_storage )	//有备用空间
    {
        construct( finish, x );		//SGI STL全局函数
        ++finsh;
    }
    else	//无备用空间
    {
        //若原大小为0，则配置1一个元素；不为0，则配置两倍元素
        const size_type old_size = size();
        const size_type len = old_size != 0 ? 2 * old_size : 1;
        
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {
			//将旧vector的内容拷贝到新vector
            new_finish = uninitialized_copy(start, position, new_start); 
            construct(new_finish, x); 
            ++new_finish; 
            //拷⻉安插点之后的元素 
            new_finish = uninitialized_copy(position, finish, new_finish); 
        }
        catch(...)
        {
            destroy(new_start, new_finish); 
            data_allocator::deallocate(new_start, len); 
            throw;
        }
        
        //析构并释放原vector
        destory(begin(), end());
        deallocate();
        
        //调整迭代器，指向新vector
        start = new_start; 
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}

整个过程分为三个部分，配置新空间，移动数据，释放原空间。因此一旦引起空间配置，指向旧vector的所有迭代器都要失效

重要的元素操作

pop_back()

void pop_back()
{
    --finish;
    destory(finish);
}

erase()

//清除[first,last]中的所有对象
iterator erase( iterator first, iterator last )
{
    iterator i = copy( last, finish, first );	//STL算法，全局函数
    destory( i, finish );
    finish = finish - (last - first);
    return first;
}

//清除某位置的对象
iterator erase( iterator position )
{
    if( position + 1 != end )
        copy( position + 1, finish, position);	//全局函数
    --finish;
    destory( finish );	//全局函数
    return position;
}

clear()

void clear()
{
    erase( begin(), end() );
}

实现如下：

insert().插入后，新对象位于指定位置之前

template< class T, class Alloc >
void vector<T, Alloc>::insert( iterator position, size_type n, const T& x );
{
    if( n != 0 )
    {
        //备用空间>=新增对象个数
        if( size_type( end_of_storage - finish ) >= n )	
        {
            T x_copy = x;
            const size_type elems_after = finish - position;
            iterator old_finish = finsih;
            //插入点后的对象数量>新增对象个数
            if( elems_after > n )
            {
                uninitialized_copy( finish - n, finish, finish );
                finish += n;	//尾部迭代器后移
                copy_backward( position, old_finish - n, old_finish );
                fill( position, position + n, x_copy );		//插入点开始填入新值
            }
        }
        //插入点后的对象数量<=新增元素个数
        else
        {
            uninitialized_copy( finish, n - elems_after, x_copy );
            finish += n - elems_after;
            uninitialized_copy( position, old_finish, finish );
            finish += elem_after;
            fill( position, old_finish, x_copy );
        }
    }
    //备用空间小于新增元素个数，需扩充
    //先决定新长度：旧长度两倍或旧长度+新增元素个数
    else
    {
        const size_type old_size = size();
        const size_type len = old_size + max( old_size, n);
        
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        
        __STL_TRY
        {
            //先将旧vector的插入点之前的元素复制到新空间
            new_finish = uninitialized_copy( start, position, new_start );
            //再将新增元素填入新空间
            new_finish = uninitialized_fill_n( new_finish, n, x );
            //最后再将旧vector的插入点后的元素复制到新空间
            new_finish = uninitialized_copy( position, finish, new_finish );
        }
	#ifdef __STL_USE_EXCEPTIONS
        catch(...)
        {
            destory( new_start, new_finish );
            data_allocator::deallocate( new_start, len );
            throw;
        }
    #endif 
        //析构并归还旧的vector
        destory( start, finish );
        deallocate();
        //调整迭代器指向新的vector
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}

list

list并非像vector一样是连续内存空间，而是非连续的。每个对象放于一块内存中，通过指针进行访问

添加删除元素性能很高，不需要像vector那样移动内存。因此，常用做随机插入、删除操作容器

list为双向链表且SGI STL的list是环状的双向链表,list自身与节点是分开设计的。满足左闭右开原则

list部分数据结构定义如下：

//节点定义
template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data;
};
struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};

//链表定义
template<class T>
class __list_node : protected _List_base<_Tp, _Alloc>
{
protected:
    typedef void* _Void_pointer;
    
public:
    typedef List_node<T> _Node;
    typedef T value_type;
    typedef value_type* pointer;
    typedef value_type& reference;
}

迭代器

list将不再能够像vector那样可以以普通指针作为迭代器，因为其节点不保证空间是连续的

由于list为双向链表，迭代器必须具备前移、后移的能力，所以list提供的迭代器种类是bidirectional iterators

list的迭代器不会因为插入或接合而失效

list与vector的区别:

vector为数组；list为双向链表
vector为顺序内存，可随机访问，且速度快,但插入删除慢；list访问速度慢，但插入删除快
vector中间进行插入删除会导致内存拷贝，list并不会
vector一次性分配内存，不够时翻倍扩容；list每次插入都会进行内存请求

deque

deque是一种双向开口的连续线性空间,且内部为分段的连续空间，随时可以新增一段空间并链接

deque与vector的差异在于：

deque允许时间复杂度为O(1)的头部插入或移除操作
deque没有capacity概念。因为deque随时可以新增一段空间并链接，没必要保留空间
deque虽然支持快速随机访问，但因为deque需要处理内部跳转，所以速度不如vector

deque提供ramdon access iterator，但不支持普通指针，迭代器比vector更复杂。这影响了各个运算层面，因此除非必要尽可能使用vector

中控器

deque由一段段的定量连续空间构成，一旦有必要在deque的头部或尾部新增空间,便配置一段定量连续空间，串接在整个deque的头部或尾部

优势:对这些分段的定量连续空间，维护整体连续的假象，并提供随机存取接口

缺点：迭代器变得十分复杂

设计思路：deque采用一块所谓的map(不是map容器)作为主控，这个map是一小块连续空间，其中每个元素都是指针，指向另一段较大的连续线性空间(缓冲区),这个缓冲区才是真正用来存放数据的

deque的部分数据结构和迭代器

template< class T, class Alloc = alloc, size_t Bufsize = 0 >
class deque
{
public:
    using value_type = T;
    using pointer* = value_type;
    using size_type = size_t;
    using iterator __deque_iterator<T, T&, T*, BufSiz >;
    
    

protected:
    using map_pointer = pointer*;
    map_pointer map;
    size_type map_size;	
    iterator start;
    iterator finish;
}

template< class T, class Ref, class Ptr, size_t BufSiz >
struct __deque_iterator
{
    using iterator __deque_iterator<T, T&, T*, BufSiz >;
    using iterator_category = random_access_iterator_tag;
    using map_pointer = T**;
    T* cur;
    T* first;
    T* last;
    map_pointer node;
    
}

//迭代器重要操作

//一旦遇到缓冲区边缘，可能需要跳一个缓冲区
void  set_node( map_pointer new_node )
{
    node = new_node;
    first = *new_node;
    last = first + difference_type(buffer_size());
}

deque的构造与内存管理

//deque定义两个专属的空间配置器
using data_allocator = simple_alloc< value_type, Alloc >;
using map_allocator = simple_alloc< pointer, Alloc>;

//一个构造函数调用fill_initialize()用于构造deque并赋初值
deque( int n, const value_type& value )
    : start(), finish(), map(0), map_size(0)
{
	fill_initialize(n, value);        
}

template<class T, class Alloc, size_t BufSize) 
void deque<T, Alloc, BufSize>::fill_initialize(size_type n, const value_type &value) 
{ 
    creat_map_and_node(n);//安排结构 
    map_pointer cur; 
    _STL_TRY 
    { 
        //为每个缓存区赋值 
        for (cur=start.node;cur<finish.node;++cur) 
            uninitalized_ fill(*cur, *cur+buffer_size(), value); 
        //设置最后⼀个节点方式不同 
        uninitalized_fill(finish.first, finish.cur, value);
	}
	catch(...) 
    {
    	// ...
	}
}

template<class T, class Alloc, size_t Bufsize> 
void deque<T, alloc, Bufsize>::creat_map_and_node(size_type num_elements) 
{ //需要节点数=元素个数/每个缓存区的可容纳元素个数+1 
    size_type num_nodes = num_elements / Buf_size() + 1; 
    map_size = max(initial_map_size(), num_nodes + 2);	//前后预留2个供扩充
    
	//创建⼀个⼤⼩为map_size的map 
    map = map_allocator::allocate(map_size);
	//创建两个指针指向map所拥有的全部节点的最中间区段 
    map_pointer nstart = map + (map_size() - num_nodes) / 2; 
    map_poniter nfinish = nstart + num_nodes - 1; 
    map_pointer cur;
    
    _STL_TRY 
    { 
        //为每个节点配置缓存区 
        for (cur=nstart;cur<nfinish;++cur) 
            +cur=allocate_node();
	}
    catch(...)
    {
        //...
    }
    //最后为deque内的start和finish设定内容 
    start.set_node(nstart); 
    finish.set_node(nfinish); 
    start.cur = start.first; 
    finish.cur = finish.first + num_elements % buffer_szie();
}

元素操作

push_back()

void push_back( const value_type& t )
{
    //缓冲区有两个及以上的剩余空间
    if( finish.cur != finish.last - 1 )
    {
        construct( finish.cur, t );
        ++finish.cur;
    }
    else	//缓冲区只有一个剩余空间
    {
        //配置一个新的缓冲区，再设置新元素，最后更改迭代器finish状态
        push_back_aux( t );
    }
}

tempalate<class T, class Alloc, size_t BufSize> 
void deque<T, alloc, BufSize>::push_back_aux(const value_type &t) 
{ 
    value_type t_copy = t; 
    reserve_map_at_back(); 
    *(finish.node + 1) = allocate_node(); 
    __STL_TRY 
    {
		construct(finish.cur, t_copy); 
        finish.set_node(finish.node+1); 
        finish.cur=finish.first;
	} 
    __STL_UNWIND {deallocate_node(*(finish.node + 1)); }
}

stack 和 queue

栈和队列都是以deque为底部实现，一切操作都由deque完成，被称为deque的配接器

直接来看实现

template< class T, class Sequence=deque <T> >
class stack
{
public:
    using value_type = typename Squence:value_type;
    using size_type = typename Squence::size_type;
    using reference = typename Squence::reference;
    
protected:
    Squence c;	//底层容器
    
public:
    bool empty() const { return c.empty(); } 
    size_type size() const { return c.size(); } 
    reference top() { return c.back(); }
	void push(const value_type &x) { c.push_back(x); } 
    void pop_back() { c.pop_back(); }
}

heap 和 priority_queue

heap

heap(不是内存heap)是完全二叉树(除了最底层叶子节点，都是填满的，而叶子节点从左至右不得有缝隙)，扮演priority_queue的助手，priority_queue允许用户以任何次序将元素推入容器，但取出时一定是从优先权最高的元素开始取

heap默认为max-heap，大顶堆是一个以vector表现的完全二叉树。也就是说heap可为小顶堆和大顶堆,大顶堆每个节点的key值大于等于子节点key值,最大值位于vector/array的开头处;小顶堆每个节点的key值小于等于子节点key值,最小值位于vector/array的开头处

heap所有元素遵循完全二叉树规则，因此不提供遍历功能，也就不提供迭代器

元素操作

push_heap()

新加入的元素放在最底层作为叶子节点，并填补由左至右的第一个空格，也就是插入vector的end()处

新节点key值大于父节点大，则父子对换位置，重复此操作直至无需对换
pop_heap()

取走根节点，为满足完全二叉树的性质，必须取走并去掉(放于vector末尾)最底层最右边的叶子节点，并将其值重新安插.重现安插时，需要下溯，也就是将目标节点与较大子节点对调，并持续下方至叶子节点为止

pop_heap()后，最大元素只是放于底部容器的尾部。若想要移除则调用pop_back()
sort_heap()

因为每次pop_heap()都是去除最大值，并把这个最大值放于vector末尾,所以sort_heap()也是用pop_heap()实现
meak_heap()

将已有数据转化为一个heap

priority_queue

priority_queue是一个有权值观念的queue,自动按照元素的权值排列,默认是由一个max-heap完成

priority_queue只允许在底部加入元素，在顶端取出元素

priority_queue没有迭代器，因为所有元素进出都有规则

关联容器

重点在于三种set/map的实现不同：

集合	底层实现	是否有序	数值是否可以重复	能否修改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(logn)	O(logn)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

映射	底层实现	是否有序	数值是否可以重复	能否修改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(logn)	O(logn)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

pair模板

pair保存两个数据成员，类似容器，是一个用于生成特定类型的模板。当创建pair时，必须提供两个类型，类型可以不同

主要用途是用作遍历关联容器

实现：

template<typename _U1, typename _U2> class __pair_base
{

    template<typename _T1, typename _T2> friend struct pair;
    __pair_base() = default;
    ~__pair_base() = default;
    __pair_base(const __pair_base&) = default;
    __pair_base& operator=(const __pair_base&) = delete;

};

template<typename _T1, typename _T2>
struct pair : private __pair_base<_T1, _T2>
{
    typedef _T1 first_type;    /// @c first_type is the first bound type
    typedef _T2 second_type;   /// @c second_type is the second bound type

    _T1 first;                 /// @c first is a copy of the first object
    _T2 second;  
}

pair操作

//对T1和T2成员进行值初始化
pair<T1, T2> p;

//frist和second分别用T1和T2进行初始化
pair<T1, T2> p( v1, v2 );
pair<T1, T2> p{ v1, v2 };

//返回一个以v1和v2初始化的pair
make_pair(v1, v2);

//当first和second分别相等时，两个pair才相等
p1 == p2;
p1 != p2;

map 和 set

相同点：

map和set底层都是由红黑树(平衡二叉搜索树)实现
所有元素都会根据元素的key值自动排序，也就是说它们是有序的
key值不可重复.因为基于红黑树的insert_unique()
不可以修改key值
查询和增删效率一样,都为O(logn)，且这个效率十分稳定，最差的情况都十分高效

不同点：

set的key值和value值都为key类型，set的key值就是value值，value值就是key值；map的元素为pair类型，pair的第一元素为key值，第二元素为value值
map可以修改value值

缺点：

插入新值时，都需要调整红黑树，效率不是特别高。因为需要保持有序

迭代器：

对set/map进行增删时，操作前的所有迭代器除开被删除的元素的迭代器，操作后依然有效

set迭代器为const类型，因为set的元素排列是有序的，不允许进行写入，否则会破坏内部结构，导致大量排序操作

map迭代器不为const，因为它的value值修改对内部结构没有影响

set部分重要实现：

template<class Key, class Compare = less<key>, class Alloc = alloc >
class set
{
public:
    using key_type = Key;
    using value_type = Key;	//于map不同之处
    //map只有一个排序
    using key_compare = Compare;
    using value_compare = Compare;
    
    //iterator都为const
    using iterator = typename rep_type::const_iterator;
    using const_iterator = typename rep_type::const_iterator;
    using reverse_iterator = typename rep_type::const_reverse_iterator;
    using const_reverse_iterator = typename rep_type::const_reverse_iterator;
    
    key_compare key_comp() const { return t.key_comp(); }
    value_compare value_comp() const { return t.key_comp(); }
   
}

map部分重要实现

template< class Key, class T, class Compare = less<key>, class Alloc = alloc >
class map
{
public:
    using key_type = Key;
    using data_type =  T;	//与set不同之处
    using value_type = pair<const Key, T>;
    //set有两个排序
    using key_compare = Compare;
    
    using iterator = typename rep_type::iterator;
    using const_iterator = typename rep_type::const_iterator;
    using reverse_iterator = typename rep_type::reverse_iterator;
    using const_reverse_iterator = typename rep_type::const_reverse_iterator;
    
    key_compare key_comp() const { return t.key_comp(); }
    value_compare value_comp() const { return value_compare( t.key_comp() ); }
}

multiset 和 multimap

multiset/multiset与set/map的特性及用法完全相同，唯一的差别在于它允许key值重复，因为它基于红黑树的insert_equal()

实现方面只是构造函数和insert函数不同

unordered_set 和 unordered_map

unordered_set / unordered_map基于哈希表(又称散列表)实现

unordered_set / unordered_map 和 set/map的不同：

哈希表是数组;红黑树是树
哈希表不是有序的；红黑树是有序的
unordered_set / unordered_map 查询和增删时间复杂度为O(1)，但不是特别稳定，发生碰撞的最差的情况为O(n);set/map为O(logn)
unordered_set / unordered_map以空间换时间,扩容复杂度为O(logn)。因为其内部虽然基于哈希表，但以(key,value)形式存储
哈希表不可以范围查找；红黑树可以
unordered_set / unordered_map扩容导致迭代器失效；set/map只有在删除时，会导致指向删除元素的迭代器失效

哈希表的大致实现过程：

用哈希函数对数据进行映射，如此即可将这些数据(特定编码方式)直接映射为哈希表上的索引，随后通过索引来进行查询
若得到的数值大于哈希表的大小，会对数值进行取模
若得到的数值有相同的情况，会发生哈希碰撞。哈希碰撞有两个解决方法：
1. 拉链法：将哈希碰撞的位置上的数据都存储在一个链表中
2. 线性探测法：此方法需要保证哈希表的大小大于数据大小。在发生哈希碰撞的位置，将其中一个数据存储于此，随后向后寻找空位来存放其他数据

迭代器

迭代器没有后退操作，即没有reverse iterator

仿函数

什么是仿函数

仿函数又叫函数对象，是一个能表现函数功能的class/struct

调用仿函数的语法与普通的函数调用一样，不过包含仿函数的class/struct 必须重载operator()。因为调用仿函数，实质是通过class/struct对象调用重载后的operator()

仿函数的类别主要用于表现函数参数的类别和传回值的类别
仿函数的由来

函数的实参可以是普通变量或函数指针，但函数指针在大多数情况下十分复杂，可读性很差。针对这一情况，仿函数孕育而生，它完全可以代替函数指针

具体方式是定义一个class/strcut,其中定义某个operator()，将该class/struct对象作为函数的实参，函数即可调用此operator()；当然，定义某方法也能行得通

仿函数的特点有两个:
1. 可以使用inline函数,如果使用inline函数的指针，编译器只是将他当作普通函数对待
2. 函数对象由class/struct封装，设计灵活。可以使用聚合和class/struct，利于资源管理
STL的仿函数

STL的仿函数定义了两个classes，分别为一元仿函数和二元仿函数(不支持三元仿函数),其中没有任何数据成员或成员函数，唯有类型定义
1. unary_function
  
  此仿函数用于呈现一元函数的参数类型和返回值类型
  
  一旦某仿函数继承自unary_function，用户便可取得该仿函数的参数类型和返回值类型，且方式是相同的(如下)
  
  定义如下：
```
template < class Arg, class Result >
struct unary_function
{
    using argument_type = Arg;
    using result_type = Result;
};

//取得仿函数的参数类型或返回值类型
//negate继承unary_function
template <class T>
struct negate : public unary_function<T, T>
{
    T operator()( const T& x ) const { return -x; }
};

template < class Predicate >
class unary_negate
{
public:
    bool operator() ( const typename Predicate::argument_type& x ) const;
}
```
2. binary_function
  
  此函数用于呈现二元函数的第一参数类型、第二参数类型，及返回值类型
  
  一旦某仿函数继承自binary_function，用户便可取得该仿函数的参数类型和返回值类型,方式同上
  
  定义如下：
```
template < class Arg1, class Arg2, class Result >
struct binary_function
{
    using first_argument_type = Arg1;
    using second_argument_type = Arg2;
    using result_type = Result;
};
```

effective stl

容器

慎重选择容器类型

需要在容器任意位置插入元素，则选择序列容器
不关心关联容器中元素是否需要排序，则选择哈希容器
非标准STL的序列容器：slist、rope(重型string)、hash容器
随机访问迭代器：vector、deque、string;双向迭代器：不使用slist和hash容器
当发生元素的插入/删除时，若避免移动容器中原来的元素很重要，则需避免连续内存的容器
若容器中数据的布局需要和c兼容，则只能选择vector
若元素的查找速度为关键因素，应选择哈希hash、排好序的vector 及标准关联容器
若介意容器内部使用引用计数，则避免使用string、rope(实现基于引用计数)
在插入/删除失败时，若需要能编写异常安全(事务语义)，需要使用基于节点的容器；且若是针对多个元素，需使用list(只有list支持)。使用连续内存的容器也可以获得事务语义，但需付出性能上的代价
基于节点的容器的插入/删除操作 不会使迭代器、指针和引用变为无效，除非它们指向一个打算删除的元素
若序列容器的迭代器是随机访问类型，只要没有发生删除操作，且插入操作只发生在容器末尾，则指向数据的指针和引用就不会失效，deque正是这样的容器。但当插入操作发生在容器末尾时，deque是唯一的会让迭代器失效而指针和引用不会失效的标准容器

不要试图编写独立于容器类型的代码

STL以泛化原则为基准：

数组被泛化为”以其包含的对象的类型为参数“的容器
函数被泛化为”以其使用的迭代器的类型为参数“的算法
指针被泛化为”以其指向的对象的类型为参数“的迭代器
容器被泛化为”序列式和关联式“容器

考虑到有时不可避免地需要从一种容量类型转为另一种，请不要使用如下写法：

class Widget{...};
vector<Widget> vw;
Widget bestWidget;
vector<Widget>::iterator i = find( vw.begin(), vw.end(), bestWidget );

而是使用如下写法，这样改变容器类型会十分容易，尤其是仅仅增加一个自定义的容器：

class Widget{ ... };
using WidgetContainer = vector<Widget>;
using WCIterator = WidgetContainer:iterator;
WidgetContainer cw;
Widget bestWidget;
WCIterator i = find( cw.begin(), cw.end(), bestWidget );

使用class把自定义的容器封装，可以更容易地改变容器类型，同时达到安全修改的目的

class CustomizedContainer
{
    private:
   
    typedef vector<Widget> InternalContainer;
    typedef InternalContainer::Iterator ICIterator;   
    InternalContainer container;
   
public:
	//...
};

确保容器中的对象拷贝正确且高效

STL容器中，插入和读取操作都是，导致的结果都是对象的拷贝

在存放base对象的容器中存放derived对象，当容器内的对象发生拷贝时，会发生截断。解决之道是让容器包含指针而非对象,智能指针更优

vector和array的效率比较：

array创建时，就会调用index + 1次构造函数
```
array A[n];		//调用n次构造函数
```

vector效率更高,你让他创建对象，实则是通过拷贝对象；只有让它使用构造函数才会使用

vector<A> va;	//创建vector，但不会构造任何一个对象
va.reverse(5);	//不调用任何函数
vector<A> va(3);  //1次构造 3次拷贝构造
va.reverse(3);	//需要移动位置，调用3次拷贝构造

调用empty而不是检查size()是否0

empty()对所有标准容器时间复杂度为O(1);而size()对list时间复杂度为O(n)

区间成员函数应优于对应的单元素成员函数

区间成员函数：像STL算法一般，利用两个迭代器来确定函数操作的区间

区间成员函数的优点：

避免频繁的元素移动
避免不必要的函数调用
避免多次进行内存分配
区间函数写起来更容易
更清楚地表达意图

若vector需要insert n个元素，单元素成员函数需要调用n次，每次还需移动一次内存位置。甚至如果是class，还需要构造，析构；而区间成员函数一步到位

区间函数的一些模板:

区间创建

container::container(InputIterator begin, InputIterator end);

区间插入

void container::insert(Iterator position, InputIterator begin, InputIterator end);
void associatedContainer::insert(InputIterator begin, InputIterator end);

区间删除

Iterator container::erase(Iterator begin, Interator end);
void associatedContainer:erase(Iterator begin, Iterator end);

区间赋值

void container::assign(InputIterator begin, InputIterator end);

C++会尽可能的将一条语句解释为函数声明

下面三种形式的语句声明效果相同.都是返回值是int类型的函数f，其参数是double类型：

int f(double d);
int f(double(d));
int f(double);

以下三种形式的语句声明效果也相同。都是返回值是int类型的函数g，其参数是返回值为double类型且无参的函数指针

int g(double(*pf)());
int g(double pf());
int g(double ()); //与"int f(double(d));"的区别在于：围绕参数名的括号会被忽略；而独立的括号表示参数列表的存在，也就是存在一个函数指针参数

现在来看一个令人吃惊的例子。对于以下函数，编译器会将其看作函数声明：

//第二个参数类型是指向不带参数的函数的指针，该函数返回一个istream_iterator<int>
list<int> data(istream_iterator<int>(dataFile),istream_iterator<int>());

另一个例子也比较常见：

class A{ ... }
A a();	//这并不会声明一个名为a的A，而是声明一个名为a的函数

对于这种情况的解决之道：

给函数参数加上括号.给形参声明用括号括起来是非法的，但给函数参数加上括号是合法的
```
list<int> data( ( istream_iterator<int>(dataFile) ), istream_iterator<int>() );
```
有一半的编译器都不支持这种行为

避免使用匿名的istream_iterator迭代器对象，而是给这些迭代器一个名称,也就是命名迭代器

ifstream datafile("ints.dat");
istream_iterator<int> dateBegin(datafile); 
istream_iterator<int> dataEnd; 
list<int>data(dataBegin,dateEnd);

如果容器中包含了通过new操作创建的指针，切记在容器对象析构前将指针delete掉

STL容器在析构前，会将其所包含的对象进行析构,但对象若是动态分配的指针，没有进行delete会造成内存泄漏

针对这一现象的解决之道：使用带有引用计数的智能指针

切勿创建包含auto_ptr对象的容器

对于一个auto_ptr，无论是被拷贝还是被复制，源对象都会失去对当前资源的所有权，·自身被置为NULL；而STL容器中的插入和读取，都是对象的拷贝，并且基于STL容器的算法也通常需要进行对象的copy

慎重选择删除元素的方法

需要删除容器中特定值的所有对象
1. 若容器是vector、string、deque,则使用erase-remove
```
container.erase( remove( container.begin(), container.end(), value ), container.end() );
```
2. 若容器是list,则使用list::remove
```
list.remove(value);
```
3. 若容器是关联容器，则使用其对应的erase成员函数
```
associatedContainer.erase(value);
```

需要删除容器中满足特定条件(判别式)的所有对象

若容器是vector、string、deque,则使用erase-remove_if

container.erase(remove_if(container.begin(),container.end(),condition),container.end());

若容器是list,则使用list::remove_if
```
list.remove_if(condition);
```

若容器是标准关联容器，则使用remove_copy_if和swap,或写一个循环来遍历容器中的元素，每次把迭代器传给erase时，要对其进行后缀递增

//remove_copy_if和swap
associatedContainer.remove_copy_if(associatedContainer.begin(), associatedContainer.end(),
                                    insert(tempAssocContainer , tempAssocContainer.end()), condition);

//后缀递增
for(assocIt = associatedContainer.begin(); assocIt != associatedContainer.end())
{
    
    if(condition(*assoIt))
    {
       dosth();
       associatedContainer.erase(assoIt++); 
    }
    else
    {
        assocIt++;
    }
    
}

除了删除对象，还需要在循环体内部做某些操作
1. 若容器是标准的序列容器，用一个循环来遍历容器中的元素，每次调用erase时，要用它的返回值更新迭代器
```
for(containerIt = container.begin(); containerIt != container.end())
{
    
    if(condition(*containerIt))
    {
       doSth();
       containerIt = container.erase(containerIt++);
	}
    else
    {
       containerIt++;
    }
    
}
```
2. 若容器是标准的关联容器，用一个循环来遍历容器中的元素，每次把迭代器传给erase时，要对迭代器做后缀递增
  
  模板在上一条c中

分配子

分配子(空间配置器,allocator)最初是内存模型的抽象，后来作为为了利于开发者作为对象而存在的内存管理器。但在STL的这部分会导致效率降低，为避免影响效率，c++降低了分配子作为对象的要求。在STL内存分配子负责分配和释放内存

自定义分配子，需要注意以下几点：

分配子是一个模板，模板参数T代表你为其分配内存的对象的类型
分配子可以为它所定义的内存模型中的指针和引用提供类型定义,始终让pointer为T*而reference为T&
库实现者可以忽略类型定义而直接使用指针和引用
STL实现者可以假定所有属于同一类型的分配子都是等价的
大多数标准容器从来没有单独使用过对应的分配子

如，list添加一个节点时，并不需要T的内存大小，而是T的listNode的内存大小.也就是说，list不需要分配子进行内存分配，它并不能提供list所需要的;而list是利用分配子提供的模板——Allocator::rebind::other，以T来决定listNode的分配子类型
不要让分配子拥有随对象而不同的状态，通常，分配子不应该有非静态数据成员
传递给allocator的是要创建元素的个数而不是申请的字节数;同时,该函数返回T*，即使还没有T对象构造出来
必须提供rebind模板，因为标准容器依赖于该模板

分配子用法:

将STL容器里的内容放在共享内存的堆

void* mallocShared(size_t bytesNeeded);
void* freeShared(void* ptr);

template<typename T>
class sharedMemoryAllocator
{
    pointer allocate(size_type numObj, const void* localHint = 0) 
    {
        return static_cast<pointer>(mallocShared(numObj * sizeof(T)));
    }
    
    void deallocate(pointer ptrToMemory, size_type numObj) 
    {
  		freeShared(ptrToMemory);
    }
}

//调用sharedMemoryAllocator
void* ptrVecMemory = mallocShared(sizeof(SharedDoubleVec));
SharedDoubleVec* pv = new(ptrVecMemory) SharedDoubleVec;
//...
pv->~SharedDoubleVec();
freeShared(sharedVec);

将STL容器里的内容放在不同的堆

切勿对STL容器的线程安全性有不切实际的依赖

对于一个STL实现，最多期望：

多线程读是安全的
多线程对不同的容器写入是安全的

也就是说STL对多线程的支持有限，需要修改STL或调用STL算法时，需要手动实现加锁

一个库实现完全的容器线程安全性时可能采取的方式：

对容器成员函数的每次调用，都锁住容器直到调用结束
在容器所返回的每个迭代器的生存期结束前，都锁住容器

为了实现异常安全，最好不要手动加锁解锁，尽量使用RAII

vector和string

vector和string优先于动态分配的数组

若使用动态的分配数组，可能需要做更多的工作，为减轻负担，请使用 vector 和 string

vector、string自动管理其所包含对象的构造与析构，且有一系列的STL算法支持，同时vector也能够保证和老代码的兼容

使用了引用计数的string可以避免不必要的内存分配和字符串拷贝(COW, copy on write);但在多线程下，string进行线程同步的开销远大于COW的开销。此时，可以考虑的方案是使用vector<char> / 动态数组

使用reserve来避免不必要的内存分配

对于STL容器而言，当他们的容量(capacity)不足以放下一个新元素时，会自动扩容来容纳新的元素.只要不超过max_size

vector和string的增长过程:

分配一块大小为当前容量的某倍数的新内存
将容器的所有元素从旧内存拷贝至新内存
析构旧内存的对象
释放旧内存

reverse()可以将上速重新分配内存的次数减到最小，从而避免重新分配及指针、迭代器、引用失效带来的开销.因此，应尽早的使用reverse()，最好是在容器刚刚构造出来时

标准容器中，只有vector和string提供以下四个函数：

size()：容器中含有多少个元素
capacity()：容器利用已经分配的内存可以容纳多少个元素,这是容器所能容纳的元素总数
resize( Container::size_type )：强迫容器改变至包含n个元素的状态。调用后size返回n
1. 若size < n，则容器尾部元素被析构
2. 若size > n,则调用默认构造函数创建新元素，再将这些新元素添加到容器末尾;且若n > capacity,添加元素前，需要重新分配内存
reserve( Container::size_type n)：强迫容器将capacity变为至少是n，前提是n不小于当前capacity,因为capacity的增加通常会导致重新分配
1. 若n < capacity,则vector无事发生；而string可能把自己的capacity减为size()和n的最大值,string大小保持不变

两种方式使用reverse避免不必要的内存分配

预测大致所需内存，并在构造容器之后就调用reserve预留内存
先用reserve分配足够大的内存，将所有元素都加入到容器后再去除多余内存(参照swap)

例子：

//创建包含1到1000的值的vector<int>
//如下做法会导致频繁的扩容,迭代器失效
vector<int> v;
for( int i = 1; i <= 1000; ++i ) v.push_back( i );

//高效的做法
vector<int>v;
v.reverse(1000);
for( int i = 1; i <= 1000; ++i ) v.push_back( i );

string实现的多样性

大部分string实现都包含：size、capacity、value;还可能包含allocator的一份拷贝;建立在引用计数上的可能包含对值的引用计数

string的四种实现形式：

包含默认Allocator的string是一个指针大小的4倍。若使用自定义allocator，则string会更大一些
在使用默认的Allocator的情况下，string对象的大小与指针的大小相等。当使用自定义的Allocator时，string对象将加上对应的自定义Allocator的对象。Other部分用来在多线程条件下进行同步控制，其大小通常为指针大小的6倍
string对象的大小与指针大小相同，没有对单个对象的Allocator的支持。X包含与值的可共享性相关的数据
对于使用默认Allocator的string，其大小等于指针大小的7倍。不使用引用计数，string内部包含一块内存可容纳15个字符的字符串

string的多种实现总结如下：

string的值可能会被引用计数
string对象大小可能是char*大小的1~7倍
创建一个新的字符串可能会发生0~2次动态分配
string可能共享其容量、大小信息
string可能支持针对单个对象的allocator
不同的实现对字符内存的最小分配单位有不同的策略

将vector和string的数据传给传统的API

将vector传递给接受数组指针的函数，要注意数组大小为空的情况

void func( const int* p, size_t numInts );
vector<int>v;

//数组大小为空，以下方式可以预防数组为空时，指针也指向空
if( !v.empty() )
    //&v[0]，改为迭代器时，将不正确，因为对于c的数组来说迭代器不等于指针
    //当然如果必须要使用迭代器，可以使用这样的形式：&*v.begin()
    func( &v[0], v.size() );

以上获得容器指针的方式对vector适用，但对string不可靠。原因如下：

string中的数据不一定存储在连续内存中
string内部不一定以空字符结尾

对于string而言，返回字符串值得指针通过调用c_str()得到。即使字符串长度为0，也是可行得，c_str()会返回一个指向空字符得指针;值得注意的是这种情况下，会把string内部得第一个空字符当作结尾的空字符

void func( const char* pString );
func( s.c_str() );

对于vector而言，用C API改变vector的元素值通常来说没有问题，因为有些情况vector对它的数据有额外限制；但这种调用方式不可以改变vector的元素个数，这会导致size()无法产生正确结果

用C API中的元素初始化vector或string:

利用vector和数组的内存布局兼容性，向API传入该矢量中元素的存储区域

//给定数组开始地址和要填充的个数，来填充数组
size_t fillArray(int* ptr, size_t size);
vector<int> v(maxSize);
//fillArray来填充vector，再把size改为fillArray填充的个数
v.resize(fillArray(&v[0],v.size()));

C API把数据放在vector<char>，再把数据从该vector拷贝至相应string

这种方式也适用于其他STL容器

size_t fillString( char* pArray, size_t arraySize );
vector<char> v( nums );
size_t charsWritten = fillString( &v[0], v.size(0) );
string s( v.begin(), v.begin() + charsWritten );

使⽤“swap技巧”删去多余的容量

当你想要清除vector/string多余内存时，可以考虑"shrink to fit"(压缩至适当大小)。实现方法是先创建一个vector的临时对象，再调用swap()。因为临时对象会调用vector的拷贝构造函数，这个函数只为所拷贝的元素分配所需要的内存，没有多余容量
做法如下：

vector<int>(v).swap(v);

但需要注意的是，上述做法不能保证一定能去除多余容量，但能尽量压缩到目前实现情况的最小

swap也可以用于清空容器，并使其容量变为该实现下的最小值。实现方法是先调用默认构造函数创建的临时对象，再调用swap()

vector<int>v;
string s;

//进行清空操作
vector<int>().swap(v);
string().swap(s);

值得注意的是，swap后，不仅容器的内容进行交换，且迭代器、指针、引用也进行交换(string除外)。也就是说，原先的迭代器依然有效，并指向同一元素，只是存在另一个容器

避免使用vector<bool>

vector<bool>并不是一个STL容器，也并不存储bool

为什么说它不是一个STL容器呢？

因为c++标准说过，如果c是包含对象T的容器，且c支持operator[]，以下代码必须能被编译
```
T* p = &c[0];	//得到一个指向该T类型对象的指针

//但vector<bool>无法通过
vector<bool> v;
bool* pb = &v[0];	//右边是&*类型
```
为什么它并不存储bool呢？

书接上回，vector<bool>无法编译通过是因为它并不真的存储bool,相反为节省空间，它存储的是bool的紧凑显示,实质上它使用了同"位域"一样的思想，来表示vector存储的bool。也就是说，这里的bool其实是一个bit,,一个八位字节可以容纳八个bool，它只是假装存储了这些bool

位域和bool看似相似，只能表示两个值，但它们之间有个重要的区别：可以创建指向bool的指针，而指向单个bit的指针/引用是不允许的。因此，上述返回bool的指针行为编译无法通过。

为了克服这一困难，vector<bool>::operator[]返回的是一个对象，这个对象表现得像是一个指向单个bit的引用，也就是代理对象
既然vector<bool>不满足STL的要求，那为什么vector<bool>是c++标准中的?

源自一个失败的实验，正是这个实验把vector<bool>留在STL容器中

这个实验大致是，c++标准委员会的人很清楚代理对象在c++软件开发中十分有用，因此它们决定开发vector<bool>，来演示STL如何支持"通过代理来存取器元素的容器"，但最终它们发现要创建一个基于代理对象的容器，同时又要满足STL容器的所有要求是不可能的
如果需要vector<bool>，有以下两种选择：
1. deque<bool>
  
  除了reserve和capacity，deque提供vector所提供的一切。但deque<bool>它属于一个标准的STL容器，且它确实存储bool
  
  不过，它元素的内存并非连续，不可以把deque<bool>的数据传递给期望bool数组的C API
2. bitset,并非STL容器,但属于c++标准库
  
  bitset的元素个数在编译时就确定了，因此它不支持插入和删除，没有迭代器

关联容器

相等和等价的区别

什么是相等？

相等的概念基于"operator=="。一旦x==y为true，则x与y相等

什么是等价？

等价关系基于"在已排序的区间中对象值的相对顺序"

标准的关联容器总是保持内部元素的一定的排列顺序，因此标准容器的实现是基于等价的，每个容器必须有一个比较函数(默认为less)来决定保持怎样的顺序.如果关联容器使用相等来决定两个对象是否有相同的值，那么还需要另一个比较函数来决定两个值是否相等(默认应该为equal_to);但equal_to没被用作STL的默认比较函数,当在STL 中需要判断相等时，一般是调用 operator ==

为包含指针的关联容器指定比较类型

以下实现并不往你期望的方向发展：

set<string*> s;
s.insert(new string("AB"));
s.insert(new string("BC"));
s.insert(new string("CD"));
for(set<string*>::iterator i = s.begin(); i != s.end(); i++)
{
    cout << *i;  //输出结果是指针
}

因为set里存储的不是string，而是指针

把 "cout << *i" 改为 "cout << **i"，也许得到想要的结果，但很大概率得不到,因为set会按指针的值进行排序，而不是string的值

为了解决以上问题，我们不能使用默认的比较函数子类，必须编写自定义的比较函数子类，最好是模板

struct _Compare
{
    template<typename ptrType>
    bool operator()( ptrType pT1, ptrType pT2 ) const
    {
        return pT1 > pT2;
    }
}

永远让比较函数对相等的值返回false

比较函数的返回值表面的是按照该函数定义的排序顺序，一个值是否在另一个之前，相等的值从不会有前后顺序关系，除非比较函数对相等的值总是返回flase,否则会破坏所有的标准关联容器，不管它们是否允许存储重复值

不含重复值的容器：

set< int, less_equal<int> > s;
s.insert(10);
s.insert(10);
//set检查以下表达式是否为true
!( 10 <= 10 ) && !( 10 <= 10 )
//简化
!(true) && (!true)
false && false

这会导致set有两份10，破坏了这个容器

对于可以含有重复值的容器:

multiset< int, less_equal<int> > s;
s.insert(10);
s.insert(10);

对multiset进行equal_range，我们并不会得到迭代器来定义一个包含相等值的区间，因为它实际指定的是包含等价值的区间。以上例子中，两个10并不等价

切勿直接修改set/multiset中的key

set、multiset、map、multimap都会按照一定的顺序存储元素，但若修改key值，将会破坏容器的有序性

对于map/multimap而言，其存储元素的类型为pair<const key, value>，修改map中的key值将不能通过编译,最好是永远不要修改map/multimap的key值(const亦是如此);对于set/multiset而言，其存储的key值不是const，需注意不要修改key值

尽管set/multiset的元素不是const，STL实现也让它们不被修改。如，set<T>::iterator的operator*返回const T&，这样的结果是指向该set中元素的const&。值得一提的是，c++标准并没有统一这个实现，不同的实现者有不同的实现，因此由于标准的模棱两可，会产生不同的理解，这样的代码是不可移植的

强制类型转换意味着临时关掉系统的安全保护，STL亦是如此，但大多数强制类型转换都可避免,例如以可行且安全的方式修改set/multiset/map/multimap的元素，可以用以下五步来进行：

找到想修改的容器的元素
拷贝一份将要被修改的元素.但对于map/multimap，不要把该拷贝的key声明为const
用你期望的值来修改该拷贝
把该元素从容器中删除，通常是erase
将拷贝的值插入到该容器

考虑用排序的vector代替关联容器

如果查询速度十分重要，标准的set/multiset/map/multimap并不是最合适的，而非标准的hash容器几乎总是值得的，也许hash函数选择得不合适或表太小，会导致hash表得查找性能可能会显著降低，但这一情况在实践中并不常见

二叉搜索树对插入、删除、查找得混合操作做了优化，也就是说，对于要混合使用插入、删除和查找的行为且无法预测下一个操作，二叉搜索树其实是首选

但许多程序使用数据结构的方式并不会这么混乱，总的来说分为三个阶段：

设置

创建新的数据结构，插入大量元素

几乎都是插入、删除，几乎没有查找
查找

查询数据结构特定的信息

几乎是查找，基本没有插入、删除
重组

改变数据结构的内容，或删除所有的当前数据,再插入

对于以上这种方式来说，排序的vector在空间和时间方面比关联容器提供更好的性能,因为只有对排序的容器才能正确使用查找算法

为什么排序的vector优于二叉搜索树?原因如下：

相对于vector，关联容器需要更大的存储空间
在排序的vector中存储数据比在关联容器中存储数据会消耗更少的内存(关联容器会多存储三个指针)，考虑到页面错误(当软件试图读取或写入标记为“不存在”的虚拟内存位置时发生的中断)的因素，通过二分搜索进行查找，排序的vector效率更高一些

关于页面错误如下：假设数据结构足够大，它们被分割后将跨越多个内存页，但vector将比关联容器需要更少的页面,若操作系统使用虚拟内存，这会导致页面错误，系统会变慢

值得注意的是，若使用vector来模仿map<const k, v>时，存储在vector中的是pair<k,v>。此时需要自定义三个比较函数，排序的比较函数和查找的比较函数
实现如下：

using Data = pair<string, int>;
class compare
{
public:
    //排序的比较函数
    bool operator()( const T& lhs, const T& rhs ) const
        return keyless( lhs.first, rhs.first );
    
    //查找的比较函数
    bool operator()( const T& lhs, const T::first_type& k ) const
        return keyless( lhs.first, k );
    //查找的比较函数
    bool operator()( const T::first_type& k, const T& rhs ) const
        return keyless( k, rhs.first );
    
private:
    bool keyless( const T::first_type& k1, const T::first_type& k2 ) const
        return k1 < k2;
}

当效率很关键时尽量用map::insert代替map::operator

对于添加操作，用insert替换operator[]

map的operator[]与vector、deque、string、数组内置的operator[]都无关，这个函数设计的目的是提供"添加和更新"的功能，但添加会降低性能

map<K,V>m;
m[k] = v;

对于"m[k] = v"其实是在检查key k是否在map中，若没有，k就被加入并以v作为value；但k已经存在，则与之关联的value更新为v

实现方式如下：operator[]返回&,指向与k相关联的value对象，v被赋值给该引用所指对象

//进行添加
map<int, A>m;
m[1] = 2;	//map中没有key1，operator[]会默认构造一个A，作为1相关联的value,再返回一个指向该A的&
//等价于
using IntAMap = map<int,A>;
pair<IntAMap::iterator, bool> result = m.insert( IntAMap::value_type(1, A() ) );
result.first->second = 2;

对于添加，我们完全可以使用"insert"来替换"operator[]"

m.insert( IntAMap::value_type( 1, 2 ) );

这种方式通常会节省三个函数调用：默认构造函数，析构函数，拷贝赋值

对于更新来说，用operator[]代替insert

一般来说，insert操作需要一个value_type(pair)，因此必须调用构造和析构一个pair，若pair中包含class，又会对class对象进行构造、析构；而operator不使用pair对象

定义一个对更新和添加效率都不错的通用函数:

template<typename MapType,
         typename KeyType,
         typename ValueType>
typename MapType::iterator InsertOrUpdate(MapType& map,const KeyType& k, const ValueType& v) 
{
    typename MapType::iterator i = map.lower_bound(k); // 如果i！=map.end()，则i->first不小于k

    if(i!=map.end() && !map.key_comp()(k,i->first)) // k不小于i->first 等价！
    {
        i->second = v;
        return i;
    }
    else
    {
        return map.insert(i,pair<const KeyType, ValueType>(k,v));
    }
};

map<int,Widget> m;
Widget w(1); 
map<int,Widget>::iterator i  = InsertOrUpdate<map<int,Widget>,int,Widget>(m,0,w);

迭代器

尽量使用iterator代替const_iterator，reverse_iterator和const_reverse_iterator

对于容器类container<T>而言:

iterator类型的功效相当于T*
const_iterator相当于const T*
reverse_iterator与const_reverse_iterator与前两者类似，只是进行反向遍历

不同类型的迭代器之间的转换关系：

从图中可得知，无法从const迭代器转换到非const迭代器,也就是说const迭代器往往没啥用。const_reverse_iterator可以通过base()成员函数被转换为const_iterator(reverse_iterator亦是),但转换后的结果并不指向同一元素(有一个offset)

算法并不关心迭代器是何种类型，只关心它是何种类别(category)；容器中很多成员函数也可以接受const的迭代器

const_iterators转化为iterators

对于大多数的容器而言，const_cast不能把const_iterator转换为iterator,因为iterator和const_iterator是完全不同的class。在某些编译器上可以将vector和string的const_iterator转换为iterator，但reverse_iterator和const_reverse_iterator不行，因为这些容器中iterator最终被解释为指针，也就是从const T*到T*，而reverse迭代器的仍然是class，但存在移植性的问题

将const_iterator转换为iterator的可行方案：

创建一个新的iterator，再将他指向与const_iterator指向的同一位置

vector<Widget> v;
typedef vector<Widget>::const_iterator ConstIter;
typedef vector<Widget>::iterator Iter;

ConstIter ci; 
//使ci指向v中的元素
Iter i = v.begin();
//distance可以取得两个迭代器之间的距离，但前提是指向同一个容器,需要注意distance的两个参数需要是同一类型定义
//advance用于将一个迭代器移动指定的距离
advance(i,distance<ConstIter>(i,ci));	//移动i

由reverse_iterator的base()成员函数所产生的iterator的用法

前面提到过调用reverse_iterator的base()成员函数所产生的iterator和原来的reverse_iterator间有一个offset
先来看个例子：

vector<int> v;
v.reserve( 5 );

for( int i = 1; i <= 5; ++i )
    v.push_back(i);

vector<int>::reverse_iterator ri = find( v.rbegin(), v.rend(), 3 );
vector<int>::iterator i( ri.base() );

相应迭代器状态如下：

可以看到调用base()后产生的iterator与原来的iterator确实存在偏移。那么如何正确使用调用base()后的iterator呢？

若要在reverse_iterator 指定的位置插入新元素，只需再base()位置处插入元素即可

若要在reverse_iterator指定的位置删除一个元素，只需再ri.base()前的位置进行删除操作

//对于vector和string以下可以编译成功,但对于它们的实现基本无法编译通过
//因为iterator和const_iterator以内置指针的方式实现
//c/c++都规定函数返回的指针不应被修改
v.erase( --ri.base() );
//改为
v.erase( (++ri).base() );

需要逐字符输入时用istreambuf_iterator

istream_iterator使用operator>>函数来完成实际的读操作，默认情况下该函数会跳过空白字符。想要保留空白字符，只需要清除输入流的skipws标志即可

ifstream inputFile("data.txt");
inputFile.unsetf( ios::skipws );
string fileData( ( istream_iterator<char>(inputFile)), istream_iterator<char>() );

但速度并不尽人意，因为每次调用operator>>都要执行许多操作(格式化)

一个内部sentry对象的构造和析构(设置和清理行为的对象)
检查可能影响行为的流标志(比如skipws)
检查可能发生的读取错误；若出现错误还会检查流的异常屏蔽标志以决定是否抛出异常

更有效的方法是"istreambuf_iterator"，调用方法和istream_iterator大致相同，但istream_iterator对象使用operator>>从输入流中读取单个字符；而istreambuf_iterator直接从流的缓冲区中读取下一个字符,且不会跳过任何字符,也没有任何格式化

ifstream inputFile("data.txt");
string fileData( istreambuf_iterator<char>(inputFile)), istreambuf_iterator<char>() );

对于非格式化的逐字符输出，考虑使用ostreambuf_iterator代替ostream_iterator,它避免因ostream_iterator带来的额外负担（损失了格式化输出的灵活性）

算法

确保目的范围足够大

每当插入新对象时，STL容器会自动扩充空间来容纳新增对象，但这并不意味着STL容器总是可以正确管理它的存储空间

比如以下这个例子：

int func( int x );
vector<int>values;
//...向values存入值
vector<int>results;

transform( values.begin(), value.end(), result.end(), func );

transform会把value设定的区间内的元素从result.end()开始赋值到result，可是问题是result.end()为空啊，因此这种调用是错误的

针对以上这类状况，我们需要调用back_inserter()(插入器，接受一个容器并生成一个迭代器,可以实现向指定容器添加元素)生成一个迭代器来指定目标区间的起始位置。改动如下：

transform( values.begin(), values.end(), back_inserter( results ), func );

现在，back_inserter()返回的迭代器将使得push_back被调用

back_inserter()适用于所有提供push_back()的容器;front_inserter()适用于提供push_front()的容器

无论何时，若使用的算法需指定一个目标区间，必须确保此目标区间足够大，或确保它会随着算法的允许而增大

各种与排序有关的选择

对排序算法的选择应更多地基于所需要完成的功能，而不是性能

关于排序的选择：

对vector/string/deque/数组而言，只需要找到n个质量最好的对象，但不需要对这n个元素进行排序，应选择nth_element

nth_element用于排序一个区间，使得位置n上的元素正好是全排序(sort)下的第n个元素

nth_element属于不稳定排序
对vector/string/deque/数组而言，若需要选择n个质量最好的对象，且还需要对前n个对象依据质量进行排序，应选择parital_sort

parital_sort属于不稳定排序
若需要对vector/string/deque/数组中的元素进行一次完全排序，应选择使用sort/stable_sort

stable_sort属于稳定排序——也就是两个相同的对象，排序后的相对位置不会发生变化

sort属于不稳定排序
若需要把所有满足某个特定条件的元素放在区间开头，应选择partition/stable_partition

partition属于不稳定排序

stable_partition属于稳定排序
若排序容器是list,partition/stable_partition仍然适用;但需要用list::sort替代sort/stable_sort;而parital_sort/nth_element则需要一些间接途径，可行的途径:
1. 将list中的元素拷贝至一个提供随机访问迭代器的容器，再对该容器执行你期望的算法
2. 先创建一个list::iterator的容器，再对该容器执行你期望的算我，最后通过其中的迭代器访问list元素
3. 利用一个包含迭代器的有序容器中的信息，通过反复调用splice成员函数，将list中的元素调整到期望的目标位置

如果确实需要删除元素,在remove这类算法后调用erase

template<class ForwardIterator, class T>
ForwardIterator remove( ForwardIterator first, ForwardIterator last, const T& value );

可以看到，remove其实并不知道value放在哪个容器，单从迭代器类型也无法推断容器类型，因此remove不可能从容器中删除元素,调用了remove容器中的元素个数也不会减少;相反，想要删除容器中的元素，唯一的方法是调用容器中的成员函数,几乎是用erase函数(list除外，因为它的成员函数并不叫erase)

那么remove的工作原理是什么？

remove移动区间中的元素，将不被删除的元素移至区间前面并保持相对顺序,再用需要保留的元素的值覆盖(赋值)要被删除的元素的值，返回一个迭代器指向最后一个"不被删除"的元素之后的元素

调用前

调用后,newEnd为remove的返回值

实际调用过程(双指针覆盖)

针对这一状况，若想删除元素，那就必须在remove后使用erase.其实，list的remove成员函数就是合并了remove和erase且效率更高

vector<int>v;
//...
v.erase( remove( v,begin(), v.end(), 99) );

remove_if和unique(删除相邻的、重复的值)也是和erase搭配使用;unique与list的结合和list::remove相似且效率更高

当心在包含普通指针的容器使用remove这类的算法

原因：因为remove会用不被删除的指针覆盖那些要被删除的指针，所以没有指针指向那些被覆盖的指针，这会造成资源泄漏

改进方法：

使用智能指针
使用remove-erase前手动删除指针并将其置空

需要排序的区间作为参数的算法

并非所有算法都可以应用于任何区间

remove算法要求单向迭代器且要求可以通过这些迭代器向容器中的对象赋值,因此它不可用于输入迭代器指定的区间，也不适用于map/multimap、某些set/multiset

有些排序算法要求随机访问迭代器，list无法调用这些算法

要求排序区间的算法：binary_search,lower_bound,upper_bound,equal_range,set_union,set_intersection,set_difference,set_symmetric_difference,merge,inplace_merge,includes

不一定要求排序的区间，但通常与排序区间一起使用：unique,unique_copy

通过mismatch或lexicographical_compare实现忽略大小写字符串比较

虽然strcmp可以实现这个目的，但它不可以处理多种语言.一般而言，运用类似strcmp的函数(返回正、负、0)和operator<(返回true,false)

int func( char c1, char c2 )
{
    //转换为小写
    int lc1 = tolower( static_cast<unsigned char>(c1) );
    int lc2 = tolower( static_cast<unsigned char>(c2) );
    
    if( lc1 < lc2 ) return -1;
    if( lc1 > lc2 ) return 1;
    return 0;
}

lexicographical_compare是strcmp的泛化版本，不过strcmp只能和字符数组工作，lexicographical_compare可以和任何类型的值的区间工作且它可以接受一个判别式，由该判别式来决定两个值是否满足一个用户自定义的准则

bool ciCharLess( char c1, char c2 )
{
    return tolower( static_cast<unsigned char>(c1) )
         < tolower( static_cast<unsigned char>(c2) );
}

bool ciStringCompare( const string& s1, const string& s2 )
{
    return lexicographical_compare( s1.begin(), s1.end()
                                    s2.begin(), s2.end(),
                                    ciCharLess
                                  );
}

strcmp通常是被优化过的，它在字符串的处理上一般要比mismatch和lexicographical_compare快得多

copy_if算法

STL没有copy_if算法实现,因为copy_if价值不大

正确的copy_if实现如下：

template<typename InputIterator, typename OutputIterator,
		 typename Predicate>
OutputIterator copy_if( InputIterator begin, InputIterator end,
                        OutputIterator destBegin, Predicate p)
         {
             while( begin != end)
             {
                 if( p(*begin)) * destBegin++ = *begin;
                 ++begin;
             }
             return destBegin;
         }

accumulate或for_each统计序列

有时我们需要以自定义方式对区间进行统计处理，accumulate可以胜任这个工作，它不位于<algorithm>，而位于<numeric>

accumulate有两种形式：

(begin, end,初始值)，返回初始值加上迭代器标识的区间中的值的总和
(初始值，统计函数)

for_each形式：(区间，函数对象)，返回一个函数对象，我们还需从这个函数对象提取我们所要的统计结果

仿函数，仿函数类，函数等

遵循按值传递的原则来设计函数子类

c/c++都不允许将一个函数作为参数传递给另一个函数，相反，你必须传递一个函数指针。C和C++的标准库函数都遵循这一规则：函数指针是按值传递的。

确保判别式是纯函数

判别式：一个返回值为bool(隐式转换)的函数

纯函数：返回值仅依赖于其参数的函数.能访问的数据仅限于参数及常量

判别式类:一个函数子类，它的operator()是一个判别式

STL能接受判别式的地方，既可接受一个判别式，亦可接受一个判别式类对象

STL算法可能会先创建仿函数的拷贝，再存放起来等以后再使用这些拷贝。正是因为这一特性，要求判别式函数必须是纯函数

一个反例：

class A : public unary_function<B, bool>
{
public:
    A() : count(0) {}
    bool operator()( const B& )
    {
        return ++count == 3;
    }
    
private:
    size_t count;
}

vector<B>vb;
...插入一些B
//不仅删除第三个元素，而且还删除了第六个
vb.erase( remove_if( vb.begin(), vb,end(), A() ) );

template<typename FwdIteraroe, typename Prediate>
FwdIterator remove_if( FwdIterator begin, FwdIterator end, Predicate p )
{
    begin = find_if( begin, end, p );	//这里的p是拷贝，因为是按值传递，count初始值为0, count+=3
    if( begin == end ) return begin;
    else
    {
        FwdIterator next = begin;
        return remove_copy_if( ++next, end, begin, p );		//这里的p同样是拷贝,count不受find_if影响，开始值为0
    }
}

理解ptr-fun,mem-fun和mem-fun-ref的来由

理解它们的由来：

//非成员函数
f(x);

//成员函数，由对象或对象的引用调用
x.f();

//成员函数，由指向对象的指针调用
p->f();

一般而言，STL都接受第一种形式的调用，对于下面两种形式，我们可以使用mem-fun/mem-fun-ref，，但必须无参

c++11中，mem-fun/mem-fun-ref不香了，而是使用fun-fn(std::mem_fn - cppreference.com)

当然更香的是std::bind

确保less<T>和operator<具有相同的含义

operator不但是less的默认实现，而且是程序员期望的，应尽量避免不让less调用operator<

应尽量避免修改less的行为，因为这样做可能误导他人，若你使用less，无论显式或隐式，都需确保它与operator<有相同含义

若希望以特殊方式排序对象，最好创建一个特殊的函数子类

程序中的STL

算法的调用优先于手写循环

算法的调用优先于手写循环的原因：

效率：算法通常比程序员自己实现的效率更高
正确性：自己实现的算法更易出错
可维护性：算法代码一般比自己实现的更简洁明了

容器的成员函数优于同名算法

为什么容器的成员函数优于同名算法？

成员函数的行为与关联容器的其他成员函数可以保持更优的一致性
算法一般关注相等性，而容器函数一般关注等价性
成员函数性能更优

区分count,find等算法

条件	使用算法		使用成员函数
	对未排序的区间	对排序区间	set/map	multiset/multimap
特定值是否存在?	find	binary_search	count	find
特定值是否存在？若存在，第一个该值对象在哪	find	equal_range	find	find/lower_bound
第一个不超过特定值的对象的位置	find_if	lower_bound	lower_bound	lower_bound
第一个在特定值之后的对象的位置	find_if	upper_bound	upper_bound	upper_bound
具有特定值的对象的个数	count	equal_rang再distance	count	count
所有具有特定值的对象的位置	find(反复调用)	equal_range	equal_range	equal_range

容器的成员函数优先于同名的算法

为什么要使用函数对象而不是函数作为STL算法的参数?

函数对象与inline

定义在class内部的函数默认为inline；而在外部的函数即使使用inline,但把他们作为参数传递给函数会转换为指针，编译器不会对这样的行为进行inline优化，也就是说函数指针参数抑制了inline
算法调用不一定正确

直接调用函数名字，可能会导致无法进行隐式转换/类型不匹配等原因而报错

避免产生”直写型”(write-only)代码

避免嵌套过多代码,会导致难以理解：

不要嵌套过多函数，可能导致难以理解且难以维护
不利于代码可读性
实在需要，可以写注释

#include正确的头文件

几何所有标准STL容器都被声明再与之同名的头文件中，但set和map是个例外，set声明set和multiset,mao声明map和multimap

除四个STL算法，其他所有算法都声明在<algorithm>；accumulate、inner_product、adjacent_difference和partial_sum声明在<numeric>

特殊的迭代器,istream_iterator和istreambuf_iterator声明在<iterator>

标准仿函数和仿函数配接器(如bind)声明在<functional>

STL相关编译器的诊断信息

vector和string的iterator通常是指针，当诊断信息是可能会引用到指针类型，说明错误使用iterator

若诊断信息提到back_insert_iterator/front_insert_iterator/insert_iterator，说明错误调用back_insert/front_insert/insert；若没有直接调用这些函数，说明是间接调用

若诊断信息提到binder1st/binder2nd,说明可能错误使用bind1st/bind2nd

若你正在使用一个很常见的STL组件，比如vector/string/for_each算法，但从错误消息看，编译器好像对此一无所知，那么可能是没有包含相应的头文件

reference

网站：

C++ 标准库参考 | Microsoft Learn

(25条消息) C++中的set_new_handler函数_尚书左仆射的博客-CSDN博客_set_new_handler

[STL] allocator 中关于allocator::difference_type 和 allocator::rebind-CSDN社区

代码随想录 (programmercarl.com)

哎，红黑树和哈希表,面试问三次了！ - 知乎 (zhihu.com)

(25条消息) C++ 仿函数_爱码大鲤鱼的博客-CSDN博客_仿函数

08 C++ 仿函数为何而生 - 知乎 (zhihu.com)

《Effective STL 》全书阅读笔记 - 知乎 (zhihu.com)

《Effective STL》学习笔记 - 贺大卫 - 博客园 (cnblogs.com)

书：

c++ primer 5th

stl源码剖析

effective stl

标签：总结,容器,const,迭代,iterator,stl,c++,vector,type
From： https://www.cnblogs.com/chenglixue/p/16966494.html

c++ stl总结

前言

stl原理

空间配置器

标准STL的allocator：

SGI STL

五种内存处理工具

迭代器

容器

顺序容器

顺序容器操作

vector

list

deque

stack 和 queue

heap 和 priority_queue

关联容器

pair模板

map 和 set

multiset 和 multimap

unordered_set 和 unordered_map

仿函数

effective stl

容器

慎重选择容器类型

不要试图编写独立于容器类型的代码

确保容器中的对象拷贝正确且高效

调用empty而不是检查size()是否0

区间成员函数应优于对应的单元素成员函数

C++会尽可能的将一条语句解释为函数声明

如果容器中包含了通过new操作创建的指针，切记在容器对象析构前将指针delete掉

切勿创建包含auto_ptr对象的容器

慎重选择删除元素的方法

分配子

切勿对STL容器的线程安全性有不切实际的依赖

vector和string

vector和string优先于动态分配的数组

使用reserve来避免不必要的内存分配

string实现的多样性

将vector和string的数据传给传统的API

使⽤“swap技巧”删去多余的容量

避免使用vector<bool>

关联容器

相等和等价的区别

为包含指针的关联容器指定比较类型

永远让比较函数对相等的值返回false

切勿直接修改set/multiset中的key

考虑用排序的vector代替关联容器

当效率很关键时尽量用map::insert代替map::operator

迭代器

尽量使用iterator代替const_iterator，reverse_iterator和const_reverse_iterator

const_iterators转化为iterators

由reverse_iterator的base()成员函数所产生的iterator的用法

需要逐字符输入时用istreambuf_iterator

算法

确保目的范围足够大

各种与排序有关的选择

如果确实需要删除元素,在remove这类算法后调用erase

当心在包含普通指针的容器使用remove这类的算法

需要排序的区间作为参数的算法

通过mismatch或lexicographical_compare实现忽略大小写字符串比较

copy_if算法

accumulate或for_each统计序列

仿函数，仿函数类，函数等

遵循按值传递的原则来设计函数子类

确保判别式是纯函数

理解ptr-fun,mem-fun和mem-fun-ref的来由

确保less<T>和operator<具有相同的含义

程序中的STL

算法的调用优先于手写循环

容器的成员函数优于同名算法

区分count,find等算法

容器的成员函数优先于同名的算法

避免产生”直写型”(write-only)代码

#include正确的头文件

STL相关编译器的诊断信息

reference

相关文章

赞助商

阅读排行