《CPrimer》第09章学习笔记.docx

C+ Primer 第09章学习笔记第09章：容器与算法学习摘录072：顺序容器将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素，这就是顺序容器。 vector 支持快速随机访问list 支持快速插入/删除deque 双端队列学习摘录073：顺序容器适配器适配器是根据原始的容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。stack后进先出（LIFO）栈queue先进先出（FIFO）队列priority_queue有优先级管理的队列第一节：顺序容器的定义（初始化）学习摘录074：新建一个容器初始化为另一个容器的副本vector ivec;vector ivec2(ivec);/ ok, ivec is vectorlist ilist(ivec);/ error: ivec is not listvector dvec(ivec); / error: ivec holds int now double将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。摘录有想074：这也就是说，容器复制的时候，只需考虑的是容器类型和元素类型，并不需要考虑原容器中的元素数量了，以前曾经想过这个问题。也会想一个问题，在定义新容器的时候，会不会出现溢出的情况呢？学习摘录075：初始化为一段元素的副本系统允许通过传递一对迭代器间接实现该功能。使用迭代器时，不要求容器类型相同，容器内的元素类型也可以不相同，只要它们相互兼容能进行转换即可。/ initialize slist with copy of each element of sveclist slist(svec.begin(), svec.end() );/ find midpoint in the vectorvector:iterator mid = svec.begin() + svec.size() / 2;/ initialize front with first half of svec: The elements up to but note include *middeque front(svec.begin(), mid);/ initialize back with second half of svec: The elements *mid through end of svecdeque back(mid, svec.end() );摘录有想075：利用迭代器复制相当的方便，减少了很多限制，还可以不同类型的复制，只是也要考虑到一个方面，稳定性，如果需要隐式转换的地方还是少用的好。一段段的复制挺好的。同时，注意考虑它的区间是左闭右开的区间来的。学习摘录076：容器内元素的类型约束元素类型必须支持赋值运算。元素类型的对象必须可复制。摘录有想076：这个问题，虽然不常发生，int型之类的内置类型不用考虑这个问题，而一些自己定义的类类型的话，真的得注意了。学习摘录077：容器的容器定义容器的容器时，有一个问题必须得注意的：vector vector lines; / ok:space required between cblosevectorvector lines; / error: treated as shift operator必须用空格隔开两个相邻的符号，以示这是两个分开的符号。否则，系统会认为是单个符号，为右移操作符，并结果导致编译时的错误。摘录有想077：网上的帖子看过很多人出现这个错，经典错误啊，就一个空格之差，让人看得纠结，写程序时，细节决定成败。第二节：迭代器和迭代器范围学习摘录078：迭代器范围C+语言使用一对迭代器标记迭代器范围，这两个迭代器分别指向同一个容器中的两个元素或超出末端的下一位置。通常，这两个迭代器命名为first和last，或beg和end，用于标记容器中的一段元素范围。该范围内的元素包括迭代器first指向的元素，以及从first开始一直到迭代器last指向的位置之前的所有元素。此类元素范围称“左闭合区间（left-inclusive interval） 表达式：first, last摘录有想078：要记得啊，常常出现的字眼“超出末端的下一位置”。这一知识点，记住左闭区间是关键。学习摘录079：使用左闭合区间的编程意义左闭合区间有两个方便使用的性质，得记住：1. 当first 与last 相等时，迭代器范围为空；2. 当first与 last 不相等时，迭代器范围内至少有一个元素，而first指向该区间的第一个元素。while(first != last) / safe to use *first because we know there is at least one element +first;摘录有想079：我想：左闭合区间的使用，总的来说可以概括为三个字吧“安全性”。第三节：顺序容器的操作每种顺序容器都提供了一组有用的类型定义以及以下操作：1. 在容器中添加元素2. 在容器中删除元素3. 设置容器的大小4. （如果有的话）获取容器内的第一个和最后一个元素。学习摘录080：在顺序容器中添加元素在容器中添加元素时，系统是将元素值复制到容器里。摘录有想080：这令我想到了指针，使用指针，改变的是值，而地址不变。这个原理吧。学习摘录081：在容器中的指定位置添加元素看代码后，你懂的！s.insert(迭代器, 插入的东西); 新元素是插入在迭代器指向的位置之前。返回指向新添加元素的迭代器。s.insert(iter, element); / insert element just before iter摘录有想081：考虑到有一种特例：push_back和push_front可以相当于iter为s.begin()和s.end() 时。学习摘录082：插入一段元素看代码后，你懂的！迭代器插入位置加上迭代器的前后位置构成的左闭合区间。string sarray4 = “quasi”, “samba”, “frollo”, “scar”; / insert all the element in sarray at end of slistslist.insert(slist.end(), sarray, sarray + 4);学习摘录083：关系操作符（比较大小）/* ivec1: 1 3 5 7 9 12 ivec2: 0 2 4 6 8 10 12 ivec3: 1 3 9 ivec4: 1 3 5 7 ivec5: 1 3 5 7 9 12*/ / ivec 1 and ivec2 differ at element0: ivec1 greater than ivec2/ ivec1 ivec2 / false/ ivec2 ivec1 / true/ ivec1 and ivec3 differ at element2: ivec1 less than ivec3ivec1 ivec3 / true/ all elements equal, but ivec4 has fewer elements, so ivec1 is greater than ivec4ivec1 ivec4 / falseivec1 = ivec5 / true; each element equal and same number of elementsivec1 = ivec4 / false; ivec4 has fewer element ivec1 != ivec4 / true; ivec4 has fewer elements than ivec1摘录有想083：很明显，在容器中，比较大小；.逐位对比，先比大小。（大者为大）.再比容器长度。（长者为大）学习摘录084：删除容器内所有的元素slist.clear(); / delete all the element within the containerslist.erase(slist.begin(), slist.end() ); / equivalent摘录有想084：要删除容器内所有的元素，可以调用clear函数，或将begin和end迭代器传递给erase函数。学习摘录085：容器中的赋值操作符赋值操作符首先删除其左操作数容器中的所有元素；然后将右操作数容器的所有元素插入到左边容器中；赋值后，左右两边的容器相等；赋值前可能两个容器长度不相等，但赋值后两个容器都具有右操作数的长度。c1 = c2; / replace contents of c1 with a copy of elements in c2/ equivalent operation using erase and insertc1.erase(c1.begin(), c1.end() ); / delete all elements in c1c1.insert(c1.begin(), c2.begin(), c2.end() ); / insert c2学习摘录086：重设容器c.assign(b,e) / 重新设置c的元素：将迭代器b和e标记的范围内所有的元素复制到c中。b和e必须不是指向c中元素的迭代器。c.assign(n, t) / 将容器c重新设置为存储n个值为t 的元素/ equivalent to: slist1.clear();/ followed by slist1.insert(slist1.begin(), 10, “Hiya!”);slist1.assign(10, “Hiya!”); / 10 elements; each one is Hiya!执行了上述语句后，容器slist1有10个元素，每个元素的值都是Hiya!摘录有想086：assign操作跟赋值操作符的操作原理差不多，都是先清空一个容器，然后再对已清空的容器进行插入操作。学习摘录087：交换容器swap操作实现交换两个容器内所有元素的功能。vector svec1(10); / vector with 10 elementsvector svec2(24); / vector with 24 elementssvec1.swap(svec2);执行swap后，容器svec1 中存储24个string类型的元素，而svec2则存储10个元素。关于swap的一个重要问题：1.该操作不会删除或插入任何元素；2.保证在常量时间内实现交换。3.由于容器内没有移动任何元素，因此迭代器不会失效。摘录有想087：对此表示疑惑，为什么没有移动元素就没失效？它的原理是？猜测可能是变了变量的地址，其它一切无发生改变。第四节：vector容器的自增长学习摘录088：vector的增长效率为了使vector容器实现快速的内存分配，其实际分配的容量要比当前所需的空间多一些。vector容器预留了这些额外的存储区，用于存放新添加的元素。于是，不必为每个新元素重新分配容器。所分配的额外内存容量的确切数目因库的实现不同而不同。比起每添加一个新元素就必须重新分配一次容器，这个分配策略带来显著的效率。事实上，其性能非常好，因此在实际应用中，比起list和deque容器，vector的增长效率通常会更高。学习摘录089：capacity成员弄清capacity（容量）与size（长度）的区别非常重要。size指容器当前拥有的元素个数；而capacity则指容器在必须分配新存储空间之前可以存储的元素总数。vector ivec;/ size should be zero; capacity is implementation definedcout “ivec: size: “ ivec.size() “ capacity: “ ivec.capacity() endl;/ give ivec 24 elementsfor (vector:size_type ix = 0; ix != 24; +x)ivec.push_back(ix);/ size should be 24; capacity will be = 24 and is implementation definedcout “ivec: size: “ ivec.size() “ capacity: “ ivec.capacity() endl;结果：ivec: size: 0 capacity: 0ivec: size: 24 capacity: 32学习摘录090：选择容器下面列举了四种选择容器的法则。1. 如果程序要求随机访问元素，则应使用vector或deque容器。2. 如果程序必须在容器的中间位置插入或删除元素，则应采用list容器。3. 如果程序不是在容器的中间位置，而是在容器首部或尾部插入或删除元素，则应采用deque容器。4. 如果只需在读取输入时在容器的中间位置插入元素，然后需要随机记问元素，则可考虑在输入时将元素读入到一个list容器，接着对此容器重新排序，使其适合顺序访问，然后将排序后的list容器复制到一个vector容器。第六节：string类型学习摘录091：string类型的查找操作几乎所有的查找操作，返回的是string:size_type类型的值，以下标形式标记查找匹配所发生的位置；当查找没有匹配值，将返回名为string:npos的特殊值。学习摘录092：string类型的定义（一少部分）s.find(a