第10章 基本组件 Basic Components

10.1 pair
pair<T1, T2>

定义于头文件<utility>

只有T1 T2都有缺省构造函数时. 该pair才有缺省构造函数.
只有T1 T2都有赋值操作符= 时. 该pair才有=
只有T1 T2都有相等比较符==时. 该pair才可以比较相等.
只有T1 T2都有<操作符时. 该pair才能有<比较

pair还定义了下边的东西:

first_type // 第一个元素的类型
second_type //第二个元素的类型

pair(const T1&x, const T1& y) //构造器
pair(const pair&) //拷贝构造
template<class U1, class U2>
pair::pair(const pair<U1,U2> &p) //这个构造器允许构造pair时用另一个pair的两个元素分
                                      //别来构造当前pair的两个元素.
pair& operator=(const pair&)  //赋值

first //第一个元素
second //第二个元素

bool operator==(const pair&, const pair&) //全局的. 比较相等.
bool operator<(const pair& x,  const pair& y) //全局的. 比较< . 若x.first < y.first 则x<y.
           //或二者的first相等. 还需要比较second部分. second部分小的为小.

template <class T1, class T2>
pair <T1,T2> make_pair(const T1& x, const T2& y) // 全局的辅助函数. 用来产生一个pair
                   // 等价于 pair<T1,T2>(x,y) 但更方便一些;

10.2 Iterator 基本要素

10.2.1 iterator_traits
iterator_traits<Iterator>

template <class Iterator>
struct iterator_traits{
        typedef typename Iterator::iterator_category iterator_category; //标识迭代器的类型.如InputIterator
        typedef typename Iterator::value_type value_type; //
        typedef typename Iterator::difference_type differrence_type;
        typedef typename Iterator::pointer pointer;
        typedef typename Iterator::reference reference;
};

template<class T>
struct itertor_traits<T*> {         //上个类的一个偏特化
         typedef random_access_iterator_tag iterator_category;
         typedef T value_type;
         typedef ptrdiff_t  difference_type;
         typedef T* pointer;
         typedef T& reference;
};

//另一个偏特化. 用于处理const T*
template<class T>
struct iterator_traits<const T*> {
         typedef random_access_iterator_tag iterator_category;
         typedef T value_type;
         typedef ptrdiff_t  difference_type;
         typedef const T* pointer;
         typedef const T& reference;
};

10.2.3 distance

它是其他STL算法用的iterator的基本元素. 它计算first与last之间的距离.
因为迭代器的类型不同(如随即访问迭代器). 计算的时间复杂度也不同.

10.2.4 advance
template <class InputIterator, class Distance>
void advance(Inputiterator& i, Distance n);
它用来将迭代器前进n步. 它也是因为迭代器类型不同而所需时间复杂度不同.
另外. 只有当i属于Bidirectional Iterator时(可以做--运算). n才允许为负值.

10.2.5 Iterator 基类
iterator<Category, T, Distance, Pointer, Reference>

它是个空类.只在其中定义了一些typedef.如果你要定义自己的迭代器类,可以从它继承.如:

class my_forward_iterator : public std::iterator<forward_iterator_tag, double> { ... };

10.3 allocator
allocator<T>
定义于<memory>

STL 事先定义的容器都有一个缺省的allocator参数. 例如:
vector <int >
就等于是:
vector <int , allocator<int> >

10.4 内存管理基本元素
这儿的几个算法.作用于未初始化的存储空间.而不是实际的c++对象上. 主要用于
协助容器类的实现.

10.4.1 construct
template <class T1, class T2>
void construct(T1* p, const T2& value);
//p指向分配但并没有初始化的内存. 然后用value做参数调用T1的构造函数初始化该内存.
在c++中. new一般是先为对象分配内存.同时在该内存上构造对象.
但有时候用new的预分配内存策略. 把内存分配和对象的构造分开实现.特别是在容器中.
//这个函数/相当于表达式 new(p) T1(value);
// c++标准中没有这个函数了.

10.4.2 destroy
template <class T> void destroy(T* pointer>
或
template <class ForwardIterator>
void destroy(ForwardIterator first, ForwardIterator last);

c++中的delele会调用对象的析构函数并释放内存.这个函数将析构和释放两个动作分开.
和上边那个construct类似. 这个函数只析构.而不释放其内存.
注意:在c++标准中没有这个函数了.

10.4.3 uninitialized_copy
template<class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_copy (InputIterator first, InputIterator last,
                           ForwardIterator result);
//这是一个在stl中有用的函数. 定义于<memory>
其中前两个参数first和last为复制的源的区间.
第三个参数result则指向的是一段分配好的内存.但尚没有在该内存中构造对象.

这个函数将源区间内的每个元素的复制品放到这段内存中去.

但是这个函数有个要注意的地方: 复制时. 要么所有的对象构造成功.要么就一个也不构造.如:
template <class InputIterator , class ForwardIterator>
ForwardIterator
uninitialized_copy (InputIterator first, InputIterator last, ForwardIterator result){
     ForwardIterator cur = result;
     try {
           for ( ; first !=last; ++first, ++cur)
                 construct(& *cur, *first); //调用10.4.1那个函数实现对象的构造
           return cur;
      }
      catch (...) {
           destroy (result, cur);     //析构已经构造的部分. 调用10.4.2那个函数
           throw;
      }
}

下面给出一个使用该函数的例子:
int main(){
    int A1[] = {1,2,3,4,5,6}
    const int N = sizeof(A1) / sizeof(int);
    int *A2 = (int *) malloc ( N * sizeof (int)); //预分配内存
    uninitialized_copy(A1, A1+N, A2); // 事实上这里调用不能成功.
                     // 因为int缺少缺省构造函数.你可以把int封装到Int类中来改写一下.
}

10.4.4 uninitialized_full
template <class ForwardIterator , class T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T&x);
//这个函数于10.4.3节的类似.
// 它在一段预分配了的内存上用对象x填充该段内存. 填充时调用T的拷贝构造函数.
//同上个函数一样. 它要么fill时填充所有元素.要么一个都不填充. 请参考前面的例子.
定义于<memory>

使用如:
const int SZ = 100;
Int *A = (Int*) malloc(N *sizeof(Int)); //预分配存储空间.
Int val(3); //构造一个用来填充的对象.
uninitialized_fill(A, A+N, val);

10.4.5 uninitialized_fill_n
template <class ForwardIterator , class Size, class T>
ForwardIterator
uninitialized_fill_n(ForwardIterator first, Size n, const T& x);

//它的作用和原理与10.4.4中的类似.只是填充n个而已.下边给出一个使用该函数的例子:
const int SZ = 100;
Int *A = (Int*) malloc(N *sizeof(Int)); //预分配存储空间.
Int val(3); //构造一个用来填充的对象.
uninitialized_fill(A, N, val);

10.5 临时缓冲区 (Temporary Buffers)

10.5.1 get_temporary_buffer
template <class T>
pair<T*, ptrdiff_t> get_temporary_buffer(ptrdiff_t len);
用来分配临时空间. 例如:
get_temporary_buffer<T>(len)会返回一个缓冲区,此区足以容纳len个T对象.
它声明于 <memory>

10.2 return_temporary_buffer
template <class T> void return_temporary_buffer(T* p);
用来归还以get_temporary_buffer分配的内存.
声明于 <memory>

使用例子:
int main(){
   pair<int*, ptrdiff_t > p = get_temporary_buffer<int>(10000);
   int * buf = p.first;
   ptrdiff_t N = p.second;
   ............
   return_temporary_buffer(buf);
}