网站建设 seo商情网,罗湖商城网站设计,海南网络广播电视台少儿频道,无棣网站定制容器简介1.1 容器的分类序列容器 vector, list, deque容器适配器 queue, stack, priority_queue关联容器 set, map, multiset, multimap序列容器是提供一组线性储存的容器#xff0c;而容器适配器负责将它们按照数据结构的方式组织起来#xff0c;关联容器提供关键字与值之间…容器简介1.1 容器的分类序列容器 vector, list, deque容器适配器 queue, stack, priority_queue关联容器 set, map, multiset, multimap序列容器是提供一组线性储存的容器而容器适配器负责将它们按照数据结构的方式组织起来关联容器提供关键字与值之间的关系可以用来快速访问。vector是一种允许快速随机访问其中元素的线性序列,在末尾添加新的元素比较快deque是双端队列两边可以同时添加元素而且访问速度与vector差不多快list是双向链表插入操作比vector和deque要快但是随机访问要慢得多1.2 容器与指针在容器中存放指针容器并不会帮忙调用指针的析构函数所以程序员必须自己管理存放的指针。vectorint v;v.push_back(new int(4));必须自己去删除里面的指针所指向的内存delete v[i];2.迭代器2.1 普通迭代器一般来讲容器都有用于遍历的迭代器除了容器适配器外因为容器适配器的行为和迭代器的行为是冲突的。定义一个用于某种容器的迭代器的方法如下ContainerType::iterator ContainerType::const_iterator 第一个是普通迭代器第二个是只读迭代器容器的begin和end方法分别会产生一个指向开头和指向超越末尾的迭代器如果容器是const则产生的迭代器也会是const迭代器支持和!等运算可以用迭代器遍历容器#include iostream
#includevector
#includeiterator
using namespace std;
int main(int argc, char** argv) {int buf[] {1,2,3,4,5,6,7,8,9,10};vectorint v;copy(begin(buf), end(buf), back_inserter(v));vectorint::iterator v_it v.begin();while(v_it ! v.end()){cout *v_it ; v_it;}cout endl;return 0;
}2.2可逆迭代器可逆迭代器从末尾反向移动产生可逆迭代器的方法:ContainerTypereverse_iteratorContainerTypeconst_revese_iterator容器的rbegin和rend会产生相应的反向迭代器#include iostream
#includevector
#includeiterator
using namespace std;
int main(int argc, char** argv) {int buf[] {1,2,3,4,5,6,7,8,9,10};vectorint v;copy(begin(buf), end(buf), back_inserter(v));vectorint::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_iteratorint it(cin);istream_iteratorint eof;vectorint v;copy(it, eof, back_inserter(v));ostream_iteratorint 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预定义迭代器CSTL有一个便利的预定义迭代器集合比如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_iteratorchar in_it(in), in_end;ostream_iteratorchar 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_iteratorint* , int raw_int_ptr(ptr);for(int i 0; i 10; i)*raw_int_ptr i*i;copy(ptr, ptr10, ostream_iteratorint(cout, ));delete [] ptrraw_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插入一个值原本的迭代器将会出现未知的错误templatetypename 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};vectorint v;v.assign(begin(buf), end(buf));vectorint::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和dequelist对象被创建之后绝对不会被移动也不会被删除因为移动意味着链表的结构会被改变。templatetypename 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};listint v;v.assign(begin(buf), end(buf));listint::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
#includevector
#includeiterator
#includestring
#includealgorithm
#includefstream
#includememory
#includelist
#includeset
#includecctype
#includecstring
#includesstream
using namespace std;templatetypename 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;}setstring 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
#includeiterator
#includestring
#includealgorithm
#includefstream
#includememory
#includeset
#includecctype
#includecstring
#includesstream
using namespace std;templatetypename 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;}setstring wordList;istreambuf_iteratorchar p(in),end;//输入流迭代器没有末尾迭代器的标志while(p ! end){string word;insert_iteratorstring 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.可完全重用的标识符识别器创建自己的迭代器关于迭代器的定义 templatetypename _Category, typename _Tp, typename _Distance ptrdiff_t,typename _Pointer _Tp*, typename _Reference _Tpstruct iterator{/// One of the link iterator_tags tag typesendlink.typedef _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
#includealgorithm
#includefunctional
#includeiterator
#includestring
#includecctype
using namespace std;
//这个程序可以在一个字符流上运算可以根据分割符来提取单词 //判定字符是否为数字或者字母
struct Isalpha : public unary_functionchar, bool{bool operator()(char c){return isalpha(c);}
};//分割符合的判定
class Delimiters : public unary_functionchar, bool{
private:string exclude;
public:Delimiters(){}Delimiters(string excl) : exclude(excl){}bool operator()(char c){return exclude.find(c) string::npos;}
};//类型函数对象
templateclass InputIter, class Pred Isalpha
class TokenIterator : public iteratorinput_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){}//iTokenIterator 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);}
};
#endifint main(int argc, char** argv){ifstream in(test.txt);assert(in ! NULL);istreambuf_iteratorchar cBegin(in), end;Delimiters delimiters( ,.\t\n\\?!);TokenIteratoristreambuf_iteratorchar, Delimiters wordIter(cBegin, end, delimiters), tend;vectorstring 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. 堆栈stackstack适配器的默认容器是deque,定义如下这是直接复制粘贴的源代码。templateclass T,class Container std::dequeTclass stack;
templatetypename _Tp, typename _Sequence deque_Tp class stack{// concept requirementstypedef typename _Sequence::value_type _Sequence_value_type;templatetypename _Tp1, typename _Seq1friend booloperator(const stack_Tp1, _Seq1, const stack_Tp1, _Seq1);templatetypename _Tp1, typename _Seq1friend 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)); }templatetypename... _Argsvoidemplace(_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 elements* 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};vectorint v(begin(buf), end(buf));stackint,vectorint 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定义如下templatetypename _Tp, typename _Sequence vector_Tp,typename _Compare lesstypename _Sequence::value_type class priority_queue其中的保护成员是 protected: _Sequence c;//优先队列使用的容器--我们可以通过公有继承来获取这个序列 _Compare comp;//优先队列使用的比较函数以上是优先队列的定义默认容器是vector默认使用的比较函数对象是lessT所以默认的优先队列是升序排列内部使用的底层算法全都是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_queueint,vectorint,greaterint q(begin(buf), end(buf));//修改比较函数使其升序排列while(!q.empty()){cout q.top() endl;q.pop();}接下来是直接输出优先队列的容器内容这里我们使用公有继承templatetypename 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_queueint{
public:vectorint 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);}vectorint v testQ.getContainer();print(begin(v), end(v));return 0;
}8.持有二进制位C提供了bitset和vectorbool来表示二进制但是bitset和STL实际上没有多大关系和其他的STL组织方式相去甚远只有vectorbool是vector的一种特殊形式8.1 bitsetnbitset模板接受一个无符号整型的参数参数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 bitsetSZ BS;//产生随机的32位bit
templateint bit
bitsetbit randBitset(){bitsetbit r(rand());for(int i 0; i bit/16-1; i){r 16;r | bitsetbit(rand());}return r;
}int main(int argc, char** argv){srand(time(NULL));cout sizeof(bitset16) sizeof(bitset16) endl;//4cout sizeof(bitset32) sizeof(bitset32) endl;//4cout sizeof(bitset48) sizeof(bitset48) endl;//8cout sizeof(bitset64) sizeof(bitset64) endl;//8cout sizeof(bitset65) sizeof(bitset65) endl;//12//因为最低4个字节一个字节8位BS a(randBitsetSZ()), b(randBitsetSZ());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位a1;cout 右移一位 a endl; cout a.set() a.set() endl;//全部置为1 bitset10 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 vectorbool里面的内容不是按字节存放的而是按位存放所以它的性质与其他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底层的数据结构是平衡树根据它的定义我们知道它的键与值是一样的所以也算是关联容器templatetypename _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::templaterebind_Key::other _Key_alloc_type; typedef _Rb_treekey_type, value_type, _Identityvalue_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如果使用这个方法的时候超出范围则是在这里创建一个关联值#includeiostream
#includefstream
#includedeque
#includevector
#includelist
#includeset
#includecassert
#includestack
#includequeue
#includemap
#includefunctional
#includep4.h
#includebitset
#includectime
#includecstdlib
using namespace std;templatetypename 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::createendl;cout Noisy copy: Noisy::copyconsendl;cout Noisy assignments: Noisy::assign endl;cout Noisy Destroy: Noisy::destroy endl;}
};int main(int argc, char** argv){Noisy na[7];//构造setsetNoisy 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_iteratorNoisy(cout, ));cout endl;//map容器mapint,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));//输出mapint, 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已经有很多相近的方法了可以使用类似的方式来#includeiostream
#includedeque
#includevector
#includelist
#includeset
#includecassert
#includestack
#includequeue
#includemap
#includefunctional
#includep4.h
#includebitset
#includectime
#includecstdlib
using namespace std;int randInt(){int i rand() %10;return i;
}//针对map容器的插入
templatetypename 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容器的插入
templatetypename 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};vectorint v(10);listint l(10);dequeint 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_iteratorint(cout, ));cout endl;copy(begin(l), end(l), ostream_iteratorint(cout, ));cout endl;copy(begin(d), end(d), ostream_iteratorint(cout, ));cout endl;//上面是使用基本容器//但是使用关联容器则是一个难点 则需要自己定义类似得生成算法//但是generate和fill这样的算法是一种复制方法对于关联式容器没有效果//可以使用类似generate_n和fill_n mapint, int m;assocFill_n(m, 10, 10, 10);mapint, int::iterator it m.begin();for( ;it ! m.end(); it){cout it-first it-second endl;}//同样的方法可以用在set上 setint s;assocFill_n(s, 10, 7);copy(s.begin(), s.end(), ostream_iteratorint(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(pairKey_type,Value_type(keyArr[n-1],valueArr[n-1]));--n;}
}//输出模板
templateclass key_type, class value_type
void print(const pairkey_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};multimapstring, int person;MapGenerate(person, name, number, 7);for_each(begin(person), end(person), printstring, int); //查找关键字--返回值是multimap指向开头和末尾的迭代器 //而每一个map存储的是一个pairfirst,second//所以返回值的first是一个mappair,pair typedef multimapstring, int::iterator RangeIterator;pairRangeIterator,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 cstddefusing namespace std;template class T
void print(const valarrayT 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};valarraydouble v(n, sizeof(n)/sizeof(n[0]));//数组数组数量初始化 print(v, v);valarraydouble sh(v.shift(1));///左移动,空出来的位置补0cshift是循环移动 print(sh,sh);valarraydouble acc(v sh);///维度相同的相加 print(acc,acc);valarraydouble trig(sin(v) sin(sh));//所有的数学函数和运算符号都进行了重载 print(trig, trig);valarraydouble p(pow(v, 3.0));//同类型初始化 print(p, p);valarraydouble app(v.apply(f));//apply调用函数 print(app, app);valarraybool 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 cstddefusing namespace std;template class T
void print(const valarrayT 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};valarrayint v(data, 12); //数组初始化 print(v,v);valarrayint r(v[slice(0,4,3)]);//起点个数距离 print(r, v[slice[0,4,3]);valarrayint r2(v[v6]);//只能用在初始化中 print(r2, v6);int buf[] {1, 4, 7, 10};valarrayint save(buf, 4);v[slice(0,4,3)] save;print(v,v);//valarraysize_t siz(2);siz[0] 2;siz[1] 3;print(siz,siz); valarraysize_t gap(2);gap[0] 6;gap[1] 2;print(gap,gap); //相当于提取一个2D数组/**/ valarrayint r3(v[gslice(0,siz,gap)]); print(r3,v[gslice(0,siz,gap));return 0;
}
