C++通用容器

1. 容器简介

1.1 容器的分类

• 序列容器 vector, list, deque

• 容器适配器 queue, stack, priority_queue

• 关联容器 set, map, multiset, multimap

序列容器是提供一组线性储存的容器，而容器适配器负责将它们按照数据结构的方式组织起来，关联容器提供关键字与值之间的关系可以用来快速访问。

vector是一种允许快速随机访问其中元素的线性序列,在末尾添加新的元素比较快

deque是双端队列，两边可以同时添加元素，而且访问速度与vector差不多快

list是双向链表，插入操作比vector和deque要快，但是随机访问要慢得多

1.2 容器与指针

在容器中存放指针，容器并不会帮忙调用指针的析构函数，所以程序员必须自己管理存放的指针。

vector<int> v;

v.push_back(new int(4));

必须自己去删除里面的指针所指向的内存

delete v[i];

2.迭代器

2.1 普通迭代器

一般来讲，容器都有用于遍历的迭代器，除了容器适配器外，因为容器适配器的行为和迭代器的行为是冲突的。

定义一个用于某种容器的迭代器的方法如下：

<ContainerType>::iterator

<ContainerType>::const_iterator

第一个是普通迭代器，第二个是只读迭代器

容器的begin和end方法分别会产生一个指向开头和指向超越末尾的迭代器，如果容器是const，则产生的迭代器也会是const

迭代器支持++和!=，==，等运算，可以用迭代器遍历容器

#include <iostream>
#include<vector>
#include<iterator>
using namespace std;
int main(int argc, char** argv) {int buf[] = {1,2,3,4,5,6,7,8,9,10};vector<int> v;copy(begin(buf), end(buf), back_inserter(v));vector<int>::iterator v_it = v.begin();while(v_it != v.end()){cout << *v_it << " "; v_it++;}cout << endl;return 0;
}

2.2可逆迭代器

可逆迭代器从末尾反向移动，产生可逆迭代器的方法:

<ContainerType>reverse_iterator

<ContainerType>const_revese_iterator

容器的rbegin和rend会产生相应的反向迭代器

#include <iostream>
#include<vector>
#include<iterator>
using namespace std;
int main(int argc, char** argv) {int buf[] = {1,2,3,4,5,6,7,8,9,10};vector<int> v;copy(begin(buf), end(buf), back_inserter(v));vector<int>::reverse_iterator v_it = v.rbegin();while(v_it != v.rend()){cout << *v_it << " "; //输出10 9 8 7 6 5 4 3 2 1v_it++;}cout << endl;return 0;
}

2.3迭代器的种类

1.输入迭代器

定义：istream_iterator 和 istreambuf_iterator

只能读取，而是是一次传递，只对每一个值做一次解析，只允许前向移动。

2.输出迭代器

ostream_iterator,ostreambuf_iterator

基本输入迭代器一样，只是用于写入的

3.前向迭代器

它既可以读，也可以写，而且支持多次读写解析，但是只允许前向移动

4.双向迭代器

它比前向迭代器多一个后向移动的功能

5.随机访问迭代器

它和普通指针一样，但是没有空的概念

输入输出迭代器的程序案例：

    istream_iterator<int> it(cin);istream_iterator<int> eof;vector<int> v;copy(it, eof, back_inserter(v));ostream_iterator<int> out(cout," ");copy(v.begin(), v.end(), out);

2.4迭代器的定义与继承体系

struct input_iterator_tag{};//输入迭代器

struct output_iterator_tag{};//输出迭代器

struct forward_iterator_tag: public input_iterator{};//前向迭代器

struct bidirectional_iterator_tag: public forward_iterator_tag{};//双向迭代器

struct random_access_iterator_tag: public bidirectional_iterator_tag{};//随机迭代器

2.5预定义迭代器

C++STL有一个便利的预定义迭代器集合，比如rend和rbegin会返回一个reverse_iterator迭代器。

而插入迭代器则替代operator=给容器赋值，它是一种插入或者压入容器的操作。比如当容器已经满了的时候，这种操作就会分配新的空间。

back_insert_iterator和 front_insert_iterator迭代器的构造函数的参数就是一个序列，然后调用push_back和push_front进行赋值。

back_insert和front_insert函数会产生这样这样对应的迭代器

2.6 流迭代器

istream_iterator有一个默认的构造函数，指向流的末尾的迭代器，所以可用默认的流迭代器对象标注末尾的位置

ostream_iterator没有末尾迭代器，需要一个办法指示末尾

    int main(int argc, char** argv) {ifstream in("main.cpp");if(!in)return 0;istream_iterator<char> in_it(in), in_end;ostream_iterator<char> out_it(cout);while(in_it != in_end){*out_it = *in_it++;}return 0;}

2.7 操作未初始化的储存区

raw_storage_iterator是一个输出迭代器，它可以把未初始化的去储存区赋值

    int* ptr = new int[10];raw_storage_iterator<int* , int> raw_int_ptr(ptr);for(int i = 0; i < 10; i++)*raw_int_ptr++ = i*i;copy(ptr, ptr+10, ostream_iterator<int>(cout, " "));delete [] ptr

raw_storage_iterator使用的是operator=来给未初始化的储存区赋值，同时，储存区的类型必须与写入的对象要一致，不一致就要进行类型转化。

3.基本序列容器

3.1 vector

这个容器是一个连续的数组，可以快速访问，但是向其中插入新的元素，是基本不可能的，除了push_back()，使用插入算法会造成巨大的代价

并且，vector储存区满了的时候，也会有很多令人诟病的问题.

当vector满了的时候，会自动扩充容量，然后把原来储存的对象复制到新的储存区，原来如果使用迭代器做了某些操作，迭代器将会失效。

当然，这里不是指不能对vector进行删除和插入，而是代价过大，相对而言不值得。

对容器末尾使用插入和删除是可以的。对其他地方，则会造成巨大的开销，比如在vector中间部分插入一个元素，则会导致vector中间开始的元素全体向后移动。

    struct ex* p = (struct ex*)malloc(sizeof(struct ex));p->s = (char*)malloc(sizeof(char) * 10);free(p->s);free(p);

3.2 deque

这是一种类似于vector的容器，但是和vector的不同之处在于,deque实际上不是连续的储存区，而是分散的若干连续块储存，然后用一个映射关系来记录各部分。

它可以在两端进行插入和删除，vector只能进行末端的插入的删除。除此之外，deque的push_back要比vector更为高效。vector的随机访问要比deque更快

3.3 序列之间的转换

比如要把deque的内容放到vector之中

这些基本序列都有一个函数assign,只需要传入起点迭代器和终点迭代器，就可以复制给新的容器

3.4 迭代器失效

比如对vector插入一个值，原本的迭代器将会出现未知的错误

template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}int main(int argc, char** argv) {int buf[] = {1,2,3,4,5,6,7,8,9,10};vector<int> v;v.assign(begin(buf), end(buf));vector<int>::iterator first, last;first = v.begin(), last = v.end();print(first,last);v.push_back(11);//使用push_back之后，迭代器将会失效 print(first,last);return 0;
}

3.5 随机访问

vector和deque都可以通过operator[]，和at方法访问，但是operator[]没有边界检查，at有边界检查，如果超过边界，则会抛出异常，但是operator[]的访问速度要比at快

3.6 list

这是一个双向链表，它没办法进行随机访问，也就是不能存在operator[]，但是它方便进行删除和插入，这方面的效率远高于vector和deque，list对象被创建之后，绝对不会

被移动，也不会被删除，因为移动意味着链表的结构会被改变。

template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}int main(int argc, char** argv) {int buf[] = {1,2,3,4,5,6,7,8,9,10};list<int> v;v.assign(begin(buf), end(buf));list<int>::iterator first, last;first = v.begin(), last = v.end();print(first,last);v.push_back(11);//list即使是使用了push_back也不会失效 print(first,last);return 0;
}

对list的排序和反转，最好使用其自带的方法，这样效率更高

3.7 链表与集合

对链表使用sort和unique之后，链表其实就有了集合的性质，不同的是，链表的效率没有集合高，集合是使用平衡树。

3.8 交换序列

这里的交换序列，指的是类型相同的序列进行交换，虽然STL有通用的swap算法，但是，自带的效率要更高一些

4.集合

集合只保留一份副本，按照顺序对元素进行排序，底层使用平衡树，查找速度是对数级。

#include <iostream>
#include<vector>
#include<iterator>
#include<string>
#include<algorithm>
#include<fstream>
#include<memory> 
#include<list>
#include<set> 
#include<cctype>
#include<cstring>
#include<sstream>
using namespace std;template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}
//用空格替换字母和'以外的字符 
char replaceJunk(char c){return isalpha(c) || c=='\'' ? c : ' '; 
}int main(int argc, char** argv) {ifstream in("test.txt",ios::in);if(!in){cerr << "open fail\n";return 0;}set<string> wordList;string line;while(getline(in, line)){transform(line.begin(), line.end(), line.begin(), replaceJunk);istringstream is(line);string word;while(is >> word){wordList.insert(word);}}print(wordList.begin(), wordList.end(),"set","\n");return 0;

下面的程序将使用更加简单的办法，引入流缓冲迭代器

#include <iostream>
#include<iterator>
#include<string>
#include<algorithm>
#include<fstream>
#include<memory> 
#include<set> 
#include<cctype>
#include<cstring>
#include<sstream>
using namespace std;template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}int main(int argc, char** argv) {ifstream in("test.txt",ios::in);if(!in){cerr << "open fail\n";return 0;}set<string> wordList;istreambuf_iterator<char> p(in),end;//输入流迭代器没有末尾迭代器的标志while(p != end){string word;insert_iterator<string> ii(word,word.begin());//这个迭代器需要一个容器和插入容器中的起始位置while(p != end && !isalpha(*p)) //跳过所有的空格++p;while(p != end && isalpha(*p))//如果是字符，则插入到word中*ii++ = *p++;if(word.size() != 0)wordList.insert(word);} print(wordList.begin(), wordList.end(),"set","\n");return 0;
}

istreambuf_iterator是一个输入流迭代器，所以需要一个默认构造的迭代器作为结束的标志，而插入迭代器是输出迭代器，它包含了容器的指针和一个指向容器的某处的迭代器，

初始化之后，对迭代器的输入，则是从指向此处的迭代器的位置开始的。

5.可完全重用的标识符识别器

创建自己的迭代器

关于迭代器的定义

  template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,typename _Pointer = _Tp*, typename _Reference = _Tp&>struct iterator{/// One of the @link iterator_tags tag [e-mail] _Category  iterator_category;/// The type "pointed to" by the iterator.typedef _Tp        value_type;/// Distance between iterators is represented as this type.typedef _Distance  difference_type;/// This type represents a pointer-to-value_type.typedef _Pointer   pointer;/// This type represents a reference-to-value_type.typedef _Reference reference;};
//创建自己的迭代器需要以上的类型说明

#ifndef __MY_ITERATOR__
#define __MY_ITERATOR__
#include <iostream>
#include<algorithm>
#include<functional>
#include<iterator>
#include<string>
#include<cctype>
using namespace std;
//这个程序可以在一个字符流上运算，可以根据分割符来提取单词 //判定字符是否为数字或者字母 
struct Isalpha : public unary_function<char, bool>{bool operator()(char c){return isalpha(c);}
};//分割符合的判定 
class Delimiters : public unary_function<char, bool>{
private:string exclude;
public:Delimiters(){}Delimiters(string excl) : exclude(excl){}bool operator()(char c){return exclude.find(c) == string::npos;}    
};//类型，函数对象 
template<class InputIter, class Pred = Isalpha>
class TokenIterator : public iterator<input_iterator_tag,string, ptrdiff_t>{
private:InputIter first;InputIter last;string word;Pred predicate;
public:TokenIterator(){}//End sentialTokenIterator(InputIter begin, InputIter end, Pred pred = Pred()) : first(begin), last(end), predicate(pred){}//i++TokenIterator& operator++(){word.resize(0);first = std::find_if(first, last, predicate);while(first != last && predicate(*first)){word += *first++;}return *this;}//new classclass CaptureState{private:string word;public:CaptureState(string& w): word(w){}string operator*(){    return word;}    };//++iCaptureState operator++(int){CaptureState d(word);++*this;return d;}//取值 string operator*() const{return word;}string* operator->()const{return &word;} //比较迭代器 --这里只关心是否到了迭代器的末尾bool operator==(const TokenIterator&){return word.size() == 0 && first == last;} bool operator!=(const TokenIterator& rv){return !(*this == rv);}
};
#endif

int main(int argc, char** argv){ifstream in("test.txt");assert(in != NULL);istreambuf_iterator<char> cBegin(in), end;Delimiters delimiters(" ,.\t\n\\?!");TokenIterator<istreambuf_iterator<char>, Delimiters> wordIter(cBegin, end, delimiters), tend;vector<string> v;copy(wordIter, tend, back_inserter(v));print(v.begin(), v.end(),"vector","\n");return 0;
}

以上程序实际上是做了一个单词的读取程序，test.txt文档中读取单词，迭代器会自动查询delimiters对象，这个对象会存放固定的分隔符号，比如空格，读取到这个分隔符，代表一个单词就结束了，然后写入word，然后插入vector中，vector负责存放单词。

TokenIterator类是一个封装好的迭代器，它的是从iterator类继承而来，只使用了一个输入迭代器，由于输入迭代器没有指示末尾的标志，所以需要一个last迭代器来指示末尾

下面将要介绍适配器，适配器有stack, priority_queue, queue三种， 他们是通过调整某一适配器来符合自己的性质，容器适配器不能使用迭代器进行遍历，因为这与他们的性质不符。

5. 堆栈stack

stack适配器的默认容器是deque,定义如下，这是直接复制粘贴的源代码。

template<class T,class Container = std::deque<T>
> class stack;
template<typename _Tp, typename _Sequence = deque<_Tp> >class stack{// concept requirementstypedef typename _Sequence::value_type _Sequence_value_type;template<typename _Tp1, typename _Seq1>friend booloperator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);template<typename _Tp1, typename _Seq1>friend booloperator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);public:typedef typename _Sequence::value_type                value_type;typedef typename _Sequence::reference                 reference;typedef typename _Sequence::const_reference           const_reference;typedef typename _Sequence::size_type                 size_type;typedef          _Sequence                            container_type;protected://  See queue::c for notes on this name._Sequence c;public:explicitstack(const _Sequence& __c = _Sequence()): c(__c) { }explicitstack(_Sequence&& __c = _Sequence()): c(std::move(__c)) { }/***  Returns true if the %stack is empty.*/boolempty() const{ return c.empty(); }/**  Returns the number of elements in the %stack.  */size_typesize() const{ return c.size(); }/***  Returns a read/write reference to the data at the first*  element of the %stack.*/referencetop(){__glibcxx_requires_nonempty();return c.back();}/***  Returns a read-only (constant) reference to the data at the first*  element of the %stack.*/const_referencetop() const{return c.back();}/***  @brief  Add data to the top of the %stack.*  @param  __x  Data to be added.**  This is a typical %stack operation.  The function creates an*  element at the top of the %stack and assigns the given data*  to it.  The time complexity of the operation depends on the*  underlying sequence.*/voidpush(value_type&& __x){ c.push_back(std::move(__x)); }template<typename... _Args>voidemplace(_Args&&... __args){ c.emplace_back(std::forward<_Args>(__args)...); }/***  @brief  Removes first element.**  This is a typical %stack operation.  It shrinks the %stack*  by one.  The time complexity of the operation depends on the*  underlying sequence.**  Note that no data is returned, and if the first element's*  data is needed, it should be retrieved before pop() is*  called.*/void pop(){c.pop_back();}void swap(stack& __s){using std::swap;swap(c, __s.c);}};

它使用的方式是has-a，也就是内部的容器定义为_Swqueue c;

可以使用一个容器对其初始化

我们也可以更改它的底层容器

固定需要的方法如下：

(1)T& top()获取栈顶元素

(2)void pop() 弹出栈顶元素

(3)void push()向栈顶添加元素

(4)bool empty() 判断是否为空

(5)int size() 返回元素个数

int buf[10] = {1,2,3,4,5,6,7,8,9,10};vector<int> v(begin(buf), end(buf));stack<int,vector<int>> s(v);while(!s.empty()){cout << s.top() << endl;s.pop();}

栈的概念就是先进后出。所以对栈的操纵都是对栈顶的操作

6.队列 queue

队列的除了行为和栈不一样，实现方式其实和stack差不多，所以这里就不写定义了。它默认使用deque,一般来讲，也不需要改变默认容器

队列是一种先进先出的数据结构，其行为如下

(1)bool empty()判断是否为空

(2)size_type size() 获取元素数量

(3)T& front() 获取队列首位的元素

(4)T& back()获取队列的末尾元素

(5)void push()入队

(6)void swap()交换两个序列

(7)void pop()删除首个元素

7.优先队列 priority_queue

定义如下：

template<typename _Tp, typename _Sequence = vector<_Tp>,typename _Compare  = less<typename _Sequence::value_type> >class priority_queue；

其中的保护成员是：

protected:

_Sequence c;//优先队列使用的容器--我们可以通过公有继承来获取这个序列

_Compare comp;//优先队列使用的比较函数

以上是优先队列的定义，默认容器是vector，默认使用的比较函数对象是less<T>，所以默认的优先队列是升序排列

内部使用的底层算法全都是make_heap, push_heap,pop_heap;

优先队列实际上就是一个堆

常用的方法如下:

(1)bool empty()
(2)size_type size()
(3)const T& top()const 获取堆顶的元素
(4)void push() 插入堆
(5)void pop() 删除堆顶的元素
(5)void swap() 交换两个队列

需要注意的是，优先队列所比较函数的比较函数operator<在没有默认提供的前提下必须自己提供，

    int buf[10] = {1,2,3,4,5,6,7,8,9,10};priority_queue<int,vector<int>,greater<int>> q(begin(buf), end(buf));//修改比较函数，使其升序排列while(!q.empty()){cout << q.top() << endl;q.pop();}

接下来是直接输出优先队列的容器内容，这里我们使用公有继承

template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}class Test_priority_queue: public priority_queue<int>{
public:vector<int>& getContainer(){return c;}
};int main(int argc, char** argv){int buf[10] = {1,2,3,4,5,6,7,8,9,10};Test_priority_queue testQ;for(int i =0 ; i < 10; i++){testQ.push(i);}vector<int> v = testQ.getContainer();print(begin(v), end(v));return 0;
}

8.持有二进制位

C++提供了bitset和vector<bool>来表示二进制，但是bitset和STL实际上没有多大关系，和其他的STL组织方式相去甚远，只有vector<bool>是vector的一种特殊形式

8.1 bitset<n>

bitset模板接受一个无符号整型的参数，参数n用来表示二进制的位数，另外参数不同就代表类型不同，两者相当于属于不同的类。

将bitset转换为整数的方法是to_ulong

超出设置范围会抛出异常

(1)可以只含有01的字符串初始化,如果超出了范围n，则只取前面的部分

(2)支持各种位移运算，>> << | & ^~

移位运算会补0

(3)bitset& set() 全部置为1， set(N)左边第N位置位1

(4)bool test(n) 第n位如果置位了，则返回true

(5)flip() 反转全部的位 flip(N)第N位反转

(6)count 置位的位数

(7)none() 不存在置位的二进制吗？存在则返回0，不存在返回1

(8)any() 是否存在置位的二进制

(9)all() 是否全置位

(10)operator[] 返回第N位的结果

constexpr int SZ = 32;
typedef bitset<SZ> BS;//产生随机的32位bit 
template<int bit>
bitset<bit> randBitset(){bitset<bit> r(rand());for(int i = 0; i < bit/16-1; i++){r <<= 16;r |= bitset<bit>(rand());}return r;
}int main(int argc, char** argv){srand(time(NULL));cout << " sizeof(bitset<16>) " << sizeof(bitset<16>) << endl;//4cout << " sizeof(bitset<32>) " << sizeof(bitset<32>) << endl;//4cout << " sizeof(bitset<48>) " << sizeof(bitset<48>) << endl;//8cout << " sizeof(bitset<64>) " << sizeof(bitset<64>) << endl;//8cout << " sizeof(bitset<65>) " << sizeof(bitset<65>) << endl;//12//因为最低4个字节，一个字节8位BS a(randBitset<SZ>()), b(randBitset<SZ>());cout <<"a = " << a << endl;cout <<"b = " << b << endl;unsigned long ul = a.to_ulong();//转化为整数 cout << ul << endl;//用只含有01的字符串初始哈string cbits("0101");cout << BS(cbits) << endl;//不足32位则会补0cout << BS(cbits,0,3) << endl;//设置0-2位a>>=1;cout <<"右移一位 = "<< a <<endl; cout << "a.set() = " << a.set() << endl;//全部置为1 bitset<10> c;cout <<"c = " << c << endl;cout << "c.set(2) = " << c.set(2) << endl;cout << "c.test(2) =" << c.test(2) << " c.test(1) = "<< c.test(1) << endl;cout << " c.flip() = " << c.flip() << endl; cout << " ~c = " << ~c << endl;cout <<"c.count() = " <<c.count()<<endl;cout <<"c.any() = "<< c.any() << endl;cout <<"c.none() = " << c.none() << endl;cout << "c.reset() = " << c.reset() << endl;return 0;
}

8.2 vector<bool>

里面的内容不是按字节存放的，而是按位存放，所以它的性质与其他STL不相同，比如以下方式就无法用

T& r = vb.front();

T* = &vb[0];

因为它返回的是一个二进制的位，无法索引这个位置

它比普通的vector多一个flip函数。

建议不要使用这个东西

9.关联容器

set， map, multiset， multimap被称为关联式容器，而set可以看作没有关键字只有值的map

关联式容器都有方法count(value),返回有多少个value，对于set和map会返回0或者1,但是杜宇multimap和multiset则会返回多个

set底层的数据结构是平衡树，根据它的定义我们知道，它的键与值是一样的，所以也算是关联容器

template<typename _Key, typename _Compare = std::less<_Key>,

typename _Alloc = std::allocator<_Key> >

class set{

public:

typedef _Key key_type;//键的类型

typedef _Key value_type;//值的类型--set的键和值的类型一样

typedef _Compare key_compare;//键的比较函数

typedef _Compare value_compare;//值的比较函数--比较函数也是一样的

typedef _Alloc allocator_type;//空间分配器

private://下面是空间分配的类型和性质

typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template

rebind<_Key>::other _Key_alloc_type;

typedef _Rb_tree<key_type, value_type, _Identity<value_type>,

key_compare, _Key_alloc_type> _Rep_type;

_Rep_type _M_t; // Red-black tree representing set.--set的核心数据，一棵红黑树

typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;

......

}；

set和map都有insert方法。

而对于operator[],map如果使用这个方法的时候，超出范围，则是在这里创建一个关联值

#include<iostream>
#include<fstream>
#include<deque>
#include<vector>
#include<list>
#include<set> 
#include<cassert>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include"p4.h"
#include<bitset>
#include<ctime>
#include<cstdlib>
using namespace std;template<typename Container>
void print(Container first, Container last, const string& title = "", const string& space = " "){if(title != "")cout << title << ":";while(first != last){cout << *first++ << space;}cout << endl;
}class Noisy{
private:static long create, assign, copycons, destroy;long id;
public:Noisy(): id(create++){cout << "d[" << id << "]" << endl;}Noisy(const Noisy& rv): id(rv.id){cout << "c[" << id << "]" << endl;copycons++;}~Noisy(){cout << "~[" << id << "]" << endl;++destroy;}Noisy& operator=(const Noisy& rv){cout << "(" << id << ")=[" << rv.id << "]" << endl;id = rv.id;++assign;return *this;}friend bool operator<(const Noisy& lv, const Noisy& rv){return lv.id < rv.id;}friend bool operator>(const Noisy& lv, const Noisy& rv){return lv.id > rv.id;}friend bool operator==(const Noisy& lv, const Noisy& rv){return lv.id == rv.id;}friend ostream& operator<<(ostream& out, const Noisy& n){return out << n.id;}friend class NoisyReport;
};long Noisy::create = 0;
long Noisy::assign = 0;
long Noisy::copycons = 0;
long Noisy::destroy = 0;struct NoisyGen{Noisy operator()(){return Noisy();}
};class NoisyReport{static NoisyReport nr;NoisyReport(){}NoisyReport& operator=(NoisyReport&);NoisyReport(const NoisyReport&);
public:~NoisyReport(){cout <<"Noisy create:" << Noisy::create<<endl;cout <<"Noisy copy:" << Noisy::copycons<<endl;cout << "Noisy assignments: " << Noisy::assign << endl;cout << "Noisy Destroy:" << Noisy::destroy << endl;}        
};int main(int argc, char** argv){Noisy na[7];//构造setset<Noisy> ns(na, na + sizeof(na)/sizeof(Noisy));Noisy n;//set插入一个新元素 ns.insert(n); //count查看某个元素存在多少个 cout << "ns.count(n) = " << ns.count(n) << endl;//findif(ns.find(n) != ns.end()) cout << n <<  "存在" << endl;//打印全部元素copy(ns.begin(), ns.end(), ostream_iterator<Noisy>(cout," "));cout << endl;//map容器map<int,Noisy> nm;for(int i = 0; i < 10;i++){//自动创建键值对nm[i]; }for(int i = 0; i < 10; i++){cout << "nm["<<i<<"]"<<nm[i] << endl;}//自动创建一个键值对nm[10] = n;//插入一个键值对 nm.insert(make_pair(47,n));//输出map<int, Noisy>::iterator it;for(it = nm.begin(); it != nm.end(); ++it)cout << it->first << it->second << endl;return 0;
}

map和pair一样有两个迭代器，first指向键，second指向值

而map的insert返回一个pair迭代器，first指向被插入对的迭代器，second指向bool元素，如果插入成功，则bool值为真

9.1 对关联式容器使用生成器和填充器

对于普通的填充器fill,fill_n,generate,generate_n，用在基本容器上有效，但是对于关联式容器就无法使用了。这里就需要根据实际情况来构造自己的生成器

比如下面的程序。实际上c++已经有很多相近的方法了，可以使用类似的方式来

#include<iostream>
#include<deque>
#include<vector>
#include<list>
#include<set> 
#include<cassert>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include"p4.h"
#include<bitset>
#include<ctime>
#include<cstdlib>
using namespace std;int randInt(){int i = rand() %10;return i;
}//针对map容器的插入 
template<typename Assoc, typename Count, typename key_type, typename value_type>
void assocFill_n(Assoc& a, Count n, const key_type& key, const value_type& val){while(n > 0){a.insert(make_pair(key,val));--n;}
}//针对set容器的插入 
template<typename Assoc, typename Count, typename value_type>
void assocFill_n(Assoc& a, Count n, const value_type& val){while(n > 0){a.insert(val);--n;}
}int main(int argc, char** argv){int buf[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};vector<int> v(10);list<int> l(10);deque<int> d(10); srand(time(0));generate(begin(v), end(v), randInt); generate(begin(l), end(l), randInt); generate(begin(d), end(d), randInt); copy(begin(v), end(v), ostream_iterator<int>(cout," "));cout << endl;copy(begin(l), end(l), ostream_iterator<int>(cout," "));cout << endl;copy(begin(d), end(d), ostream_iterator<int>(cout," "));cout << endl;//上面是使用基本容器//但是使用关联容器则是一个难点 ，则需要自己定义类似得生成算法//但是，generate和fill这样的算法是一种复制方法，对于关联式容器没有效果//可以使用类似generate_n和fill_n map<int, int> m;assocFill_n(m, 10, 10, 10);map<int, int>::iterator it = m.begin();for( ;it != m.end(); ++it){cout <<it->first  << " " << it->second << endl;}//同样的方法可以用在set上 set<int> s;assocFill_n(s, 10, 7);copy(s.begin(), s.end(), ostream_iterator<int>(cout," "));return 0;
}

9.2多重映像和重复的关键字 multimap

这是一个包含重复关键字的关联容器，这就好像身份证一样，身份证号码是唯一的，但是人名却可以重复

//生成值
template <class Map_type, class Key_type, class Value_type>
void MapGenerate(Map_type& m,const Key_type* keyArr, const Value_type* valueArr, int n){while(n > 0){m.insert(pair<Key_type,Value_type>(keyArr[n-1],valueArr[n-1]));--n;}
}//输出模板
template<class key_type, class  value_type>
void print(const pair<key_type, value_type>& p){cout << p.first << " " << p.second << endl;
}int main(int argc, char** argv){
//假设有这么几个名字 string name[] = {"aaa", "bbb", "aaa", "aaa", "ccc","fff","ddd"};int number[] = {1,2,3,4,5,6,7};multimap<string, int> person;MapGenerate(person, name, number, 7);for_each(begin(person), end(person), print<string, int>);    //查找关键字--返回值是multimap指向开头和末尾的迭代器 //而每一个map存储的是一个pair<first,second>//所以返回值的first是一个map<pair,pair> typedef multimap<string, int>::iterator RangeIterator;pair<RangeIterator,RangeIterator> ptr = person.equal_range("aaa");auto it = ptr.first;while(it!= ptr.second){cout<< it->first << " " << it->second <<endl;it++;}}

对于multiset其实差不多，没有什么好说的了

10 STL的扩充

STL用其他方式实现了set,map 这是因为现在的set和map使用的是红黑树，查找方面已经是对数级别的速度，但是仍然显得不尽如人意，而使用hash算法，索引速度能达到常数级，

但是这种方式消耗的内存要高于红黑树。hash算法实现的STL有hash_map, hash_set, hash_multiset, hash_multimao,slist(单链表), rope(这是一个string的变种，相当于string的优化)

11.非STL容器

前面说过的bitset就是一种非STL容器，另外还有valarray容器，这是一种类vector容器，非STL容器都不支持迭代器，这两个容器的作用是对数值计算进行的特化

#include <iostream>
#include <valarray>
#include <cstddef>using namespace std;template <class T>
void print(const valarray<T>& a, const string& s = ""){if(s != "")cout << s << ":";for(size_t i = 0; i < a.size(); ++i){cout << a[i] << " ";} cout << endl;
}double f(double x){return 2.0 * x - 1;}int main(){double n[] = {1.0, 2.0, 3.0, 4.0};valarray<double> v(n, sizeof(n)/sizeof(n[0]));//数组+数组数量初始化 print(v, "v");valarray<double> sh(v.shift(1));///左移动,空出来的位置补0，cshift是循环移动 print(sh,"sh");valarray<double> acc(v + sh);///维度相同的相加 print(acc,"acc");valarray<double> trig(sin(v) + sin(sh));//所有的数学函数和运算符号都进行了重载 print(trig, "trig");valarray<double> p(pow(v, 3.0));//同类型初始化 print(p, "p");valarray<double> app(v.apply(f));//apply调用函数 print(app, "app");valarray<bool> eq(v == app);//比较返回一个结果数组 print(eq, "bool eq");double x = v.max();double y = v.min();double z = v.sum();cout << x << " " << y << " " << z << endl; return 0; 
}

切片

#include <iostream>
#include <valarray>
#include <cstddef>using namespace std;template <class T>
void print(const valarray<T>& a, const string& s = ""){if(s != "")cout << s << ":";for(size_t i = 0; i < a.size(); ++i){cout << a[i] << " ";} cout << endl;
}double f(double x){return 2.0 * x - 1;}int main(){int data[] = {1,2,3,4,5,6,7,8,9,10,11,12};valarray<int> v(data, 12); //数组初始化 print(v,"v");valarray<int> r(v[slice(0,4,3)]);//起点，个数，距离 print(r, "v[slice[0,4,3]");valarray<int> r2(v[v>6]);//只能用在初始化中 print(r2, "v>6");int buf[] = {1, 4, 7, 10};valarray<int> save(buf, 4);v[slice(0,4,3)] = save;print(v,"v");//valarray<size_t> siz(2);siz[0] = 2;siz[1] = 3;print(siz,"siz"); valarray<size_t> gap(2);gap[0] = 6;gap[1] = 2;print(gap,"gap"); //相当于提取一个2D数组/**/ valarray<int> r3(v[gslice(0,siz,gap)]); print(r3,"v[gslice(0,siz,gap)");return 0; 
}