求逆序数的nlog(2n)复杂度的算法，其实就是归并排序的原理。只需要在排序的过程中记录一下交换得次数。稍微处理一下就可以了。 stack queue   和 priority_queue等classes 并非containers，他们提供Container操作行为的有限子集。

stack<T, Sequence>，是一种adapter，提供Container功能子集，它允许安插、移除以及审查stack最顶端元素。Sequence缺省的底部类型是deque，但可以明确指定不同的底部型别，Sequence 必须为Back Insertion Sequence的model。stack不具有iterator。

queue<T, Sequence>,是一种adapter，并且是一种FIFO的数据结构，它不具有iterator。Sequence应该隶属于Front Insertion Sequence 且为 Back Insertion Sequence的model，其缺省值为deque。

priority_queue<T, Sequence, Compare>,是一种adapter它提供安插、查看、移除最顶端元素的功能。priority_queue缺省的Sequence默认为vector，但可以明确指定不同的底部型别。通常以算法make_heap、push_heap、pop_heap来Sequence的heap状态。
C++ Standard提供了四种Associative Container Classes：set、map、multiset、multimap，这四个都是Sorted Associative Container的model。SGI STL扩展了Hashed Associative Containers。

set<Key, Compare, Allocator>,是一种Simple Associative Container，意指value type与其key type都是key。它同时是Unique Associative Container，表示没有两个元素相同。其元素一定会以递增顺序排序。和list一样安插和移除元素不会使iterator实效。可以用二叉查找树来实现。

multiset表示可以容纳两个或更多个相同元素，这也是set与multiset唯一不同之处。

map<Key, T, Compare, Allocator>,是一种Sorted Associative Container可以将型别为Key的objets与型别为T的objects系结在一起。它是一种Pair Associative Container，其中value_type为pair<const Key, T>。它同时也是Unique Associative Container。安插和删除元素不会使iterator失效。当map作为关联数组时，可以使用operator[] 来检索元素，它可以实现insert的功能，但区别是它返回的是引用，当某个key不存在时，首先插入默认的T value，然后返回该处值得引用。

multimap表示可以容纳两个或更多个相同元素，这也是map与multimap唯一不同之处。

SGI STL扩展的Hashed Associative Containers有 hash_set      hash_multiset       hash_map     hash_multimap
vector<T, Allocator>
vector是一种Sequence，支持随机访问元素，常量时间内在尾端安插和移除元素，以及线性时间内在开头和中间安插或移除元素。vector的元素个数能够动态变更，内存管理行为完全自动。通常它的实现方式是把元素安排在连续的存储块中，这使得vector的iterator可以是一般的指针。典型的vector有三个memeber variables，三个都是指针：start、finish、end_of_storage。vector的所有元素位于[start,finish)之中，而[finish, end_of_storage)则包含了未初始化的存储空间。vector的大小为finish-start，容量为end_of_storage-start。可以使用member function reserve 来预先分配内存，来防止iterator的实效。

list<T, Allocator>
list是一种双向连接链表，其中每个元素都有一个predecessor和一个sucessor。能以amortized const time在list的开头、尾端、中间处安插及移除元素，并且list的iterator不会实效。

slist是一种单向连接链表，它是SGI STL对C++ Standard的扩展，链表中的每个元素都连接至下一个元素，但不连接至前一个元素。slist的insert与erase等函数是很耗时的，因为slist中的元素没有记录predecessor。

deque<T, Allocator>
deque类似于vector,它也是一种Sequence,支持元素的随机访问、常量时间内于尾端安插或移除元素、线性时间内于中间安插和移除元素。注意在deque开头或尾端安插一个元素，需要amortized constant time，在中间处安插元素的复杂度则与n成线性关系，此处n是安插点距离deque开头与尾端的最短距离。deque不具备类似vector的capacity()和reserve()之类的member functions，但它保证将元素安插于deque开头或尾端不会造成deque中现存的任何元素被复制，它不会发生内存重新分配的行为。
通常，deque是以动态区段化的数组实现出来的，deque通常内涵一个表头，指向一组节点，每个节点含有固定数量并且连续存储的元素。当deque增长时便增加新的节点。它比vector复杂的多，也要慢一些，对deque排序几乎不是一个好主意，可以考虑将deque的元素复制到vector中，然后对vector排序，最后复制回来较佳，所以应该尽量使用vector。



Insert Iterators:

front_insert_iterator是具有Output Iterator功能的一个iterator adapter，可将object安插于Front Insertion Sequence中的第一个元素之前，具有安插语义，改变Seqence中元素的总个数。

back_insert_iterator具有和Output Iterator功能的一个iterator adapter，赋值动作可将object安插于Back Insertion Sequence的最后一个元素之后。

insert_iterator是一种iterator adapter，功能如同Output Iterator。通过insert_iterator,赋值动作可将object安插于Container之中。如果ii是个insert_iterator，那么ii会持续追踪一个Container c和一个安插点p。表达式*ii = t将执行安插动作c.insert(p,t)，它会为c新增元素，而非覆盖。对于Sorted Associative Container而言，虽定义有带两个参数的insert版本，但只是作为优化之用，第一个参数值是个提示，指向查找的起始位置。


===============================
Stream Iterators:

istream_iterator是一种Input Iterator，它能为来自某个basic_istream的objects执行格式化输入动作。一旦stream结束，istream_iterator便呈现一个特别的stream终结值，此值为past-the-end iterator.
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(V));

ostream_iterator是一种Output Iterator，它能将一个T Objects格式化输出到某个特定的basic_ostream中。

istreambuf_iterator和istream_iterator非常相似，它从input stream读入单个字符。是一种input Iterator。
ostreambuf_iterator和ostream_iterator非常相似，可以将字符写入一个output ostream之中。

reverse_iterator是一种iterator adapter，能够在range上逆向移动。在reverse_iterator<Iter> object上执行operator++ 和 在object上执行operator--的结果是相同的。Reverse iterator的同一性为：&*(reverse_iterator(i)) == &*(i-1)

raw_storage_iterator是一种adapter，可以让STL算法与低阶内存操作彼此结合起来。当我们有必要将内存的分配与对象的构造分开处理时，可以派上用场。 *i = x 等价于 construct（&*i, x)


STL包含四种不同的二分查找算法，binary_search    lower_bound  upper_bound   equal_range.他们作用的range是已sorted。

binary_search试图在已排序的[first, last)中寻找元素value。如果[first, last)内有等价于value的元素，它会返回true，否则返回false，它不返回查找位置。

lower_bound它试图在已排序的[first,last)中寻找元素value。如果[first, last)具有等价于value的元素，lower_bound返回一个iterator指向其中第一个元素。如果没有这样的元素存在，它便返回假设这样的元素存在的话，会出现的位置。即指向第一个不小于value的元素。如果value大于[first, last)的任何一个元素，则返回last。

upper_bound它试图在已排序的[first,last)中寻找value，返回可安插value的最后一个合适的位置。如果value存在，lower_bound 返回的是指向该元素的iterator。相较之下upper_bound并不这么做，它返回value可被安插的最后一个合适位置。如果value存在，那么它返回的iterator将指向value的下一个位置，而非value自身。

equal_range的返回值本质上结合了lower_bound和upper_bound两者的返回值。其返回值是一对iterator i 和 j ， 其中i是value可安插的第一个位置，j则是value可安插的最后一个位置。可以推演出：[i，j)中的每个元素都等价于value，而且[i, j)是[first, last)之中符合上述性质的一个最大子区间。  算法lower_bound返回该range的第一个iterator， 算法upper_bound返回该range的past-the-end iterator，算法equal_range则是以pair的形式将两者都返回。 template< class T1, class T2 >
void construct(T1* p, const T2& value)
在C++中new 操作符首先分配object的内存，然后调用构造函数在该内存位置上构造object。可以分开如下：
int* pI = (int *)::operator new(sizeof (int))；
::new (pI) int(100);
其中算法uninitialized_copy 、 uninitialized_file 、 unintialized_fill_n 和算法copy 、fill、fill_n的区别就在于此,前者们属于低阶算法，他们在给定的address处进行值copy

C++类似的操作符还有delete


有些算法，如stable_sort和inplace_merge,是所谓的"adaptive".他们会尝试分配额外的临时空间来放置中介结果.如果成功,则具有较佳运行时期复杂度。get_temporary_buffer 和return_temporary_buffer可以用来分配和释放未初始化的内存。至于get_temporary_buffer应该使用malloc或operator new，并没有任何规定。这些函数应该只用于内存真正是临时性的情况下，如果一个函数以get_temporary_buffer分配内存，则在该函数返回前，必得调用return_temporary_buffer来归还内存。
template<class _Ty> inline
    pair<_Ty *, _PDFT>
        get_temporary_buffer(_PDFT _Count)
    {    // get raw temporary buffer of up to _Count elements
    _Ty  *_Pbuf;

    if (_Count <= 0)
        _Count = 0;
    else if (((size_t)(-1) / _Count) < sizeof (_Ty))
        _THROW_NCEE(std::bad_alloc, NULL);

    for (_Pbuf = 0; 0 < _Count; _Count /= 2)
        if ((_Pbuf = (_Ty _FARQ *)operator new(
            (_SIZT)_Count * sizeof (_Ty), nothrow)) != 0)
            break;

    return (pair<_Ty _FARQ *, _PDFT>(_Pbuf, _Count));
    }


template<class _Ty> inline
    void return_temporary_buffer(_Ty *_Pbuf)
    {    // delete raw temporary buffer
    operator delete(_Pbuf);
    }

所谓Associative Container是一种可变大小的Container，它支持以key为基础，有效率地取出元素的方法。它并不允许将元素安插于特定位置。如Sorted Associative Container 、Hashed Associative Container，对于Simple Associative Container而言，元素自身就是它自己的key，因此嵌套型别iterator 和 const_iterator在功能上完全相同，可以移除元素，但不能改变其内容。对于Pair Associative Container，它具有两个不同的嵌套型别：iterator 和 const_iterator。其实这里的iterator并非是个mutable iterator，因为你不能写出 *i = t。但它不完全是const_ierator，因为i->second = 数值  成立。至于Unique Associative Container 保证没有两个元素相同的key。Multiple Associative Container则允许多个元素具有相同的（same）key。same key指两个keys互不小于对方。

所谓Container是一种object，能够存储其他的objects作为元素，并拥有访问元素的方法。每个container model 都具有一个相关的iterator，最一般化的container concept，它只要求其相关的iterator必须是input iterator的一个model，所以，我们不应该对container的iterators做出比input iterator还多的假设。


所谓Forward Container是一种Container， 其元素依据明确的次序规则来排列。这个次序规则不会在迭代过程中自行改变。它所提供的iterators满足Forward Iterator的需求条件。因此Forward Container支持multipass算法，并允许同一个container同时拥有多个有效的iterators。

所谓Reversible Container是一种Forward Container，而且其iterator是一种Bidirectional iterator。它拥有额外的一些member functions 和嵌套型别，不但可以向前遍历，也可以回头遍历。

所谓Random Access Container是一种Reversible Container，而且其iterator type是一种Random Access Iterator。它提供operator [] member function访问其元素。

===============================================
所谓Sequence是一种可变大小的Container， 其元素是以strict liner order加以排列。它导入许多新的member functions，用以安插或删除任意位置上的单个或某区间的元素。STL Container如vector、deque、list 、slist都是Sequence。他们的主要区别在于vector 、deque提供Random Access Iterators，list提供Bidirectional iterators， slist提供Forward iterators。

所谓Front Insertion Sequence是一种Sequence，可以在amortized constant time内将元素安插与起始点或是取得起始位置的元素，front() 成员方法以及push_front()、pop_front() 要比begin()、insert()、erase()更具有效率，但功能上基本相同，在STL Container中list、slist和deque都是Front Insertion Sequence的model，vector不是，vector拥有front()，但不具有pop_front() 和push_front()方法。


所谓Back Insertion Sequence与Front Insertion Sequence类似，他可以在amortized constant time内将元素安插与尾端，或取出最后元素。back()    push_back() pop_back()成员方法 。STL Containers中vector 、list、deque 都是Back Insertion Sequence的model 。slist就不是，slist拥有back，但不具备push_back 和 pop_back，它是单向连接链表，访问其最后元素不是constant time行为。 1.Trivial Iterator:此Iterator可以不具有累加性但他必须是dereference的 *x成立，dereference assignment即：*x=t，Member Access（成员访问）：x-〉m成立。STL定义的所有iterator types都具有累加性，他们不仅仅是Trivial Iterator的Models。

2.Input Iterator，此类iterator可以被提取值，可以累加以获得序列中的下一个iterator，但他不保证多次提取某个位置都是成功的，例如，他不保证一定能够访问同一个input iterator i 两次，Input Iterator的model type不需在单一range内支持一个以上的现行有效的（active）iterator。    Input Iterator是 Trivial Iterator的refinement，注意，每个可以累加的iterator i都必须是可dereference的， 而past-the-end 不是可以dereference的。istream_iterator是它的一个恰当的model

3.Output Iterator提供一种机制，用来存储数值序列，但不必提供取出数值的方法，它的接口更受约束。它不必支持member Access 或 相等比较（equality），也不必拥有相关类型defference_type或者value_type, 它同Input Iterator一样，可以不支持multipass dereference，不保证有效的访问同一个Output Iterator两次，直觉上可以把output Iterator想象为磁带：可以写数值到目前位置上，然后前进到下一个位置；但不能读出，也不能回转或者倒带。注意Output Iterator不是Trivial Iterator的refinement，它仅是Assignable的refinement，即：*x=t有效，但*x却未必有意义。必须有效的表达式有：y=x 、 *x = t、 ++x、x++、 *x++=t。 STL中的Models 有：front_insert_iterator、back_insert_iterator、insert_iterator、ostream_iterator。

4.Forward Iterator,符合线性数值序列的直觉概念,它可应用于multipass dereference的算法中，将一个Forward Iterator累加，并不会造成旧值得副本无效。但它不必支持在range中回头移动,但必须支持向前移动.他是 Input Iterator 、Output Iterator、Default Constructible的refinement。STL中的models有slist<int>::iterator, slist<int>::const_iterator。

5.Bidirectional Iterator，是一种可以累加、递减的iterator。递减是Bidirectional Iterator与Forward Iterator之间的唯一区别，它是Forward Iterator的refinement。  (++i; --i)或者(--i;++i)后必须保持位置不动。

6.Random Access Iterator，是一种可累加、递减的iterator，同时向前或回头移动任意步数时，以及在比较两个iterators时，耗用固定时间 O(c)。它是Birectional iterator和Strict Weakly Comparable的refinement。有效的表达式有：i += n （n可以为负整数）； i-j返回 difference_type 差距。 i<j  、 i[n] 为 *（i+n）、 i[n] = t。 STL中的models有：vector<int>::iterator、vector<int>::const_iterator、 deque<int>::iterator、deque<int>::const_iterator