优秀网站有哪些,网站建设是必须的吗,网站开发技术三大件,白城百度网站建设9.3顺序容器操作
顺序容器和关联容器的不同之处在于两者组织元素的方式。这些不同之处直接关系到了元素如何存储、访问、添加以及删除。上一节介绍了所有容器都支持的操作#xff08;罗列于表9.2#xff08;第295页#xff09;#xff09;。本章剩余部分将介绍顺序容器所特…9.3顺序容器操作
顺序容器和关联容器的不同之处在于两者组织元素的方式。这些不同之处直接关系到了元素如何存储、访问、添加以及删除。上一节介绍了所有容器都支持的操作罗列于表9.2第295页。本章剩余部分将介绍顺序容器所特有的操作。
9.3.1向顺序容器添加元素
除array外所有标准库容器都提供灵活的内存管理。在运行时可以动态添加或删除元素来改变容器大小。表9.5列出了向顺序容器非array添加元素的操作。当我们使用这些操作时必须记得不同容器使用不同的策略来分配元素空间而这些策略直接影响性能。在一个vector或string的尾部之外的任何位置或是一个deque的首尾之外的任何位置添加元素都需要移动元素。而且向一个vector或string添加元素可能引起整个对象存储空间的重新分配。重新分配一个对象的存储空间需要分配新的内存并将元素从旧的空间移动到新的空间中。
使用push_back
在3.3.2节(第90页)中我们看到push_back将一个元素追加到一个vector的尾部。除array和forward_list之外每个顺序容器(包括string类型)都支持push_back例如下面的循环每次读取一个string到word中然后追加到容器尾部//从标准输入读取数据将每个单词放到容器末尾string word;while(cinword)container.push_back(word);对push_back的调用在container尾部创建了一个新的元素将container的size增大了.该元素的值为word的一个拷贝。container的类型可以是list、vector或deque由于string是一个字符容器我们也可以用push_back在string末尾添加字符
void pluralize(size_tent,stringword)
{
if(ent1)
word.push_back(*sr);//等价于words
}
容器元素是拷贝
当我们用一个对象来初始化容器时或将一个对象插入到容器中时实际上放入到容器中的是对象值的一个拷贝而不是对象本身。就像我们将一个对象传递给非引用参数(参见3.2.2节第79页)一样容器中的元素与提供值的对象之间没有任何关联。随后对容器中元素的任何改变都不会影响到原始对象反之亦然。
使用push_front
除了push_back,list,forward_list和deque容器还支持名为push_front的类似操作。此操作将元素插入到容器头部listintilist;//将元素添加到ilist开头for(size_tix0;ix!4;ix)ilist.push_front(ix);此循环将元素0、1、2、3添加到ilist头部。每个元素都插入到list的新的开始位置(newbeginning)。即当我们插入1时它会被放置在0之前2被放置在1之前依此类推。因此在循环中以这种方式将元素添加到容器中最终会形成逆序。在循环执行完毕后ilist保存序列3、2、1、0。注意deque像vector一样提供了随机访问元素的能力但它提供了vector所不支持的push_front。deque保证在容器首尾进行插入和删除元素的操作都只花费常数时间。与vector一样在deque首尾之外的位置插入元素会很耗时。
在容器中的特定位置添加元素
push_back和push_front操作提供了一种方便地在顺序容器尾部或头部插入单个元素的方法。insert成员提供了更一般的添加功能它允许我们在容器中任意位置插入0个或多个元素。vector、deque、list和string都支持insert成员。forward_list提供了特殊版本的insert成员我们将在9.3.4节(第312页)中介绍。每个insert函数都接受一个迭代器作为其第一个参数。迭代器指出了在容器中什么位置放置新元素。它可以指向容器中任何位置包括容器尾部之后的下一个位置。由于迭代器可能指向容器尾部之后不存在的元素的位置而且在容器开始位置插入元素是很有用的功能所以insert函数将元素插入到迭代器所指定的位置之前。例如下面的语句slist.insert(iter,Hello!);//将Hello!添加到iter之前的位置将一个值为Hello的string插入到iter指向的元素之前的位置。虽然某些容器不支持push_front操作但它们对于insert操作并无类似的限制(插入开始位置)比如vector。因此我们可以将元素插入到容器的开始位置而不必担心容器是否支持push_frontvectorstringsvec;liststringslist;//等价于调用slist.push_front(Hello!*);slist.insert(slist.begin(),Hello!);//vector不支持push_front,但我们可以插入到begin()之前//警告插入到vector末尾之外的任何位置都可能很慢 svec.insert(svec.begin(),Hello!);
插入范围内元素
除了第一个迭代器参数之外insert函数还可以接受更多的参数这与容器构造函数类似。其中一个版本接受一个元素数目和一个值它将指定数量的元素添加到指定位置之前这些元素都按给定值初始化svec.insert(svec.end(),10,Anna);这行代码将10个元素插入到svec的末尾并将所有元素都初始化为stringAnna?接受一对迭代器或一个初始化列表的insert版本将给定范围中的元素插入到指定位置之前vectorstringv{quasin,simba,frollo,nscarH);//将v的最后两个元素添加到slist的开始位置slist.insert(slist.begin(),v.end()-2, v.end());slist.insert(slist.end(),(these,“words”will,ngon,natn,the,“end”});slist.insert(slist.begin(), slist.begin(), slist.end); / / 运行时错误迭代器表示要拷贝的范围不能指向与目的位置相同的容器如果我们传递给insert 一对迭代器它们不能指向添加元素的目标容器。 在新标准下接受元素个数或范围的insert版本返回指向第一 新加入元素的迭代器。(在旧版本的标准库中这些操作返回void。)如果范围为空不插入任何元素.insert操作会将第一个参数返回。使 用 insert 的返回值
通过使用insert 的返回值可以在容器中一个特定位置反复插入元素liststring 1st; auto iter 1st.begin(); while (cin » word) iter 1st. insert (iter, word) ; // 等价于调用 push_front在循环之前我们将iter初始化为lst.begin()。第一次调用insert会将我们刚刚读入的string插入到iter所指向的元素之前的位置。insert返回的迭代器恰好指向这个新元素。我们将此迭代器赋予iter并重复循环读取下一个单词。只要继续有单词读入每步while循环就会将一个新元素插入到iter之前并将iter改变为新加入元素的位置。此元素为(新的)首元素。因此每步循环将一个新元素插入到list首元素之前的位置。
使用emplace操作
新标准引入了三个新成员emplace_front、emplace和emplace_back这些操作构造而不是拷贝元素。这些操作分别对应push_front、insert和push_back,允许我们将元素放置在容器头部、一个指定位置之前或容器尾部。当调用push或insert成员函数时我们将元素类型的对象传递给它们这些对象被拷贝到容器中。而当我们调用一个emplace成员函数时则是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。之前的是(push_front、insert和push_back)对元素的拷贝浪费内存。例如假定c保存Sales_data(参见7.1.4节第237页)元素//在c的末尾构造一个Sales_data对象c.emplace_back(978-0590353403,25,15.99); //使用三个参数的Sales_data构造函数c.push_back(M978-0590353403n,25,15.99); //错误没有接受三个参数的push_back版本c.push_back(Sales_data(H978-0590353403n,25,15.99)); //正确创建一个临时的Sales_data对象传递给push_back其中对emplace_back的调用和第二个push_back调用都会创建新的Sales_data对象。在调用emplace_back时会在容器管理的内存空间中直接创建对象。而调用push_back则会创建一个局部临时对象并将其压入容器中。emplace函数的参数根据元素类型而变化参数必须与元素类型的构造函数相匹配://iter指向c中一个元素其中保存了Salesdata元素c.emplace_back();//使用Sales_data的默认构造函数c.emplace(iter,”999-999999999”)//使用Sales_data(string)//使用Sales_data的接受一个ISBN、一个count和一个price的构造函数 c.emplace_front(978-0590353403**,25,15.99);emplace函数在容器中直接构造元素”传递给emplace函数的参数必须与元素类型的构造函数相匹配“
9.3.2访问元素击
表9.6列出了我们可以用来在顺序容器中访问元素的操作。如果容器中没有元素访问操作的结果是未定义的。包括array在内的每个顺序容器都有一个front成员函数而除forward_list之外的所有顺序容器都有一个back成员函数。这两个操作分别返回首元素和尾元素的引用//在解引用一个迭代器或调用front或back之前检查是否有元素if(!c.empty())(//val和val_2是c中第一个元素值的拷贝auto val*c.begin(),val2c.front();//val3和va_4是c中最后一个元素值的拷贝auto lastc.end();auto val3*(--last);//不能递减forward_list迭代器auto val4c.back();//forward_list不支持此程序用两种不同方式来获取c中的首元素和尾元素的引用。直接的方法是调用front和back。而间接的方法是通过解引用begin返回的迭代器来获得首元素的引用以及通过递减然后解引用end返回的迭代器来获得尾元素的引用。这个程序有两点值得注意迭代器end指向的是容器尾元素之后的(不存在的)元素。为了获取尾元素必须首先递减此迭代器。另一个重要之处是在调用front和back或解引用begin和end返回的迭代器之前要确保c非空。如果容器为空if中操作的行为将是未定义的。访问成员函数返回的是引用
在容器中访问元素的成员函数即front、back、下标和at返回的都是引用。如果容器是一个const对象则返回值是const的引用。如果容器不是const的则返回值是普通引用我们可以用来改变元素的值if(!c.empty())(c.front()42; //将42赋予c中的第一个元素autovc.back(); //获得指向最后一个元素的引用 v指向c存储的最后一个位置空间v1024; //改变c中的元素auto v2c.back(); //v2不是一个引用它是c.back的一个拷贝 将c存储的最后一个空间的数据复制一份到v2v20;} //未改变c中的元素与往常一样如果我们使用auto变量来保存这些函数的返回值(auto只需要一个元素不需要很多)并且希望使用此变量来改变元素的值必须记得将变量定义为引用类型。
下标操作和安全的随机访问
提供快速随机访问的容器string、vector、deque和array也都提供下标运算符参见3.3.3节第91页。就像我们已经看到的那样下标运算符接受一个下标参数返问容器中该位置的元素的引用。给定下标必须在范围内”即大于等于0,且小于容器的大小。保证下标有效是程序员的责任下标运算符并不检查下标是否在合法范围内。使用越界的下标是一种严重的程序设计错误而且编译器并不检查这种错误。如果我们希望确保下标是合法的可以使用at成员函数。at成员函数类似下标运算符但如果下标越界at会抛出一个out_of_range异常参见5.6节第173页vectorstringsvec;//空vectorcoutsvec[0];//运行时错误svec中没有元素coutsvec.at0;//抛出一个out_of_range异常
9.3.3删除元素
与添加元素的多种方式类似(非array)容器也有多种删除元素的方式。表9.7列出了这些成员函数pop_front和pop_back成员函数
pop_front和pop_back成员函数分别删除首元素和尾元素。与vector和string不支持push_front一样这些类型也不支持pop_front。类似的forward_list不支持pop_back。与元素访问成员函数类似不能对一个空容器执行弹出操作。这些操作返回void。如果你需要弹出的元素的值就必须在执行弹出操作之前保存它
while(!list.empty()){process(ilist.front());// 对ilist的首个元素进行一些处理ilist.pop_front();// 完成之后删除首个元素
}
从容器内部删除一个元素
成员函数erase从容器中指定位置删除元素。我们可以删除由一个迭代器指定的单个元素也可以删除由一对迭代器指定的范围内的所有元素。两种形式的erase都返回指向删除的(最后一个)元素之后位置的迭代器。即若j是i之后的元素那么erase(i)将返回指向j的迭代器和insert相反假设在i之前添加jinsert添加返回的是指向j的迭代器。例如下面的循环删除一个list中的所有奇数元素
list int lst {0,1,2,3,4,5,6,7,8,9};
auto it : lst.begin()
while(it ! lst.end()){if(*it % 2)it lst.erase(it);elseit;
}
每个循环步中首先检查当前元素是否是奇数。如果是就删除该元素并将it设置为我们所删除的元素之后的元素。如果*it为偶数我们将it递增从而在下一步循环检查下一个元素。
删除多个元素
接受一对迭代器的erase版本允许我们删除一个范围内的元素//删除两个迭代器表示的范围内的元素//返回指向最后一个被删元素之后位置的送代器elem1slist.erase(elem1,elem2);//调用后elem1elem2迭代器elem1指向我们要删除的第一个元素elem2指向我们要删除的最后一个元素之后的位置。为了删除一个容器中的所有元素我们既可以调用clear,也可以用begin和end获得的迭代器作为参数调用eraseslist.clear();//删除容器中所有元素slist.erase(slist.begin(),slist.end());//等价调用
9.3.4特殊的forwardJist操作
为了理解forward_list为什么有特殊版本的添加和删除操作考虑当我们从一个单向链表中删除一个元素时会发生什么。如图9.1所示删除一个元素会改变序列中的链接。在此情况下删除elem3也会改变elem2,elem2原来指向elem3.但删除elem3后elem2指向了elem4当添加或删除一个元素时删除或添加的元素之前的那个元素的后继会发生改变。为了添加或删除一个元素我们需要访问其前驱以便改变前驱的链接。但是forward_list是单向链表。在一个单向链表中没有简单的方法来获取一个元素的前驱。出于这个原因在一个forward_list中添加或删除元素的操作是通过改变给定元素之后的元素来完成的。这样我们总是可以访问到被添加或删除操作所影响的元素。由于这些操作与其他容器上的操作的实现方式不同forward_list并未定义insert、emplace和erase,而是定义了名为insert_after、emplace_after和erase_after的操作参见表9.8。例如在我们的例子中为了删除elem3,应该用指向elem2的迭代器调用erase_after。为了支持这些操作forward_list也定义了before_begin,它返回一个首前off-the-beginning迭代器。这个迭代器允许我们在链表首元素之前并不存在的元素之后”添加或删除元素亦即在链表首元素之前添加删除元素。当在forward_list中添加或删除元素时我们必须关注两个迭代器-----个指向我们要处理的元素另一个指向其前驱。例如可以改写第312页中从list中删除奇数元素的循环程序将其改为从forward_list中删除元素
forward_listint flst {0,1,2,3,4,5,6,7,8,9};
auto prev flst.before_begin(); // 表示flst的首前元素
auto curr flst.begin() ;//表示flst的第一个元素while(curr ! flst.end){if(*flst % 2)curr flst.erase_after(prev);else{prev curr;//移动迭代器curr 指向下一个元素 prev 指向curr之前的元素curr;}
}
此例中curr表示我们要处理的元素prev表示curr的前驱。调用begin来初始化curr,这样第一步循环就会检查第一个元素是否是奇数。我们用before_begin来初始化prev,它返回指向curr之前不存在的元素的迭代器。当找到奇数元素后我们将prev传递给erase_after,此调用将prev之后的元素删除即删除curr指向的元素。然后我们将curr重置为erase_after的返回值,使得curr指向序列中下一个元素prev保持不变仍指向(新)curr之前的元素。如果curr指向的元素不是奇数在else中我们将两个迭代器都向前移动。
9.3.5改变容器大小
如表9.9所描述我们可以用resize来增大或缩小容器与往常一样array不支持resize。如果当前大小大于所要求的大小容器后部的元素会被删除如果当前大小小于新大小会将新元素添加到容器后部listintilist(10,42);//10个int每个的值都是42ilist.resize(15);//将5个值为0的元素添加到ilist的末尾ilist.resize(25,-1);//将10个值为的元素添加到ilist的末尾从ilist末尾ilist.resize(5);//删除20个元素resize操作接受一个可选的元素值参数用来初始化添加到容器中的元素。如果调用者未提供此参数新元素进行值初始化(参见3.3.1节第88页)。如果容器保存的是类类型元素且resize向容器添加新元素则我们必须提供初始值或者元素类型必须提供一个默认构造函数9.3.6容器操作可能使迭代器失效
向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针、引用或迭代器失效。一个失效的指针、引用或迭代器将不再表示任何元素。使用失效的指针、引用或迭代器是一种严重的程序设计错误很可能引起与使用未初始化指针一样的问题参见2.3.2节第49页
在向容器添加元素后
如果容器是vector或string,且存储空间被重新分配则指向容器的迭代器、指针和引用都会失效空间重新分配比如当前空间太小了增大空间但是空间不足需要将整个容器移到别的地方重新开辟指向先前的地址的迭代器、指针和引用就会失效。如果存储空间未重新分配指向插入位置之前的元素的迭代器、指针和引用仍有效但指向插入位置之后元素的迭代器、指针和引用将会失效和前面一样如果增大的空间不是很大在原有的空间后面追加开辟空间先前的仍然保留。对于deque,插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素迭代器会失效但指向存在的元素的引用和指针不会失效。对于list和forward_list,指向容器的迭代器包括尾后迭代器和首前迭代器、指针和引用仍有效。当我们从一个容器中删除元素后指向被删除元素的迭代器、指针和引用会失效这应该不会令人惊讶。毕竟这些元素都已经被销毁了。当我们删除一个元素后对于list和forward_list,指向容器其他位置的迭代器包括尾后迭代器和首前迭代器、引用和指针仍有效。对于deque,如果在首尾之外的任何位置删除元素那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除deque的尾元素则尾后迭代器也会失效但其他迭代器、引用和指针不受影响如果是删除首元素这些也不会受影响。对于vector和string,指向被删元素之前元素的迭代器、引用和指针仍有效。注意当我们删除元素时尾后迭代器总是会失效。因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。这个建议对vector、string和deque尤为重要。
编写改变容器的循环程序
添加/删除vector、string或deque元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。程序必须保证每个循环步中都更新迭代器、引用或指针。如果循环中调用的是insert或erase,那么更新迭代器很容易。这些操作都返回迭代器我们可以用来更新
//傻瓜循环 删除偶数元素 复制每个奇数元素
vectorint vi {0,1,2,3,4,5,6,7,8,9};
auto iter vi.begin();//使用begin而不是cbegin因为需要改变元素
while(iter ! vi.end){if(*iter % 2){iter vi.insert(iter,*iter);//复制当前元素iter 2;//跳过当前元素 以及插入到他之前的元素}else{iter vi.erase(iter);//删除偶数元素//不需要移动迭代器 iter删除元素之后 指向删除元素之后的元素}
}
此程序删除vector中的偶数值元素并复制每个奇数值元素。我们在调用insert和 erase后都更新迭代器因为两者都会使迭代器失效。 在调用erase后不必递增迭代器因为erase返回的迭代器已经指向序列中下一 个元素。调用insert后需要递增迭代器两次。记住insert在给定位置之前插入新 元素然后返回指向新插入元素的迭代器。因此在调用insert后iter指向新插入 元素位于我们正在处理的元素之前。我们将迭代器递增两次恰好越过了新添加的元素和正在处理的元素指向下一个未处理的元素。
不要保存end返回的迭代器
当我们添加/删除vector或 string的元素后或在deque中首元素之外任何位置 添加/删除元素后原来end返回的迭代器总是会失效。因此添加或删除元素的循环程序必须反复调用end,而不能在循环之前保存end返回的迭代器一直当作容器末尾使用。通常C标准库的实现中end()操作都很快部分就是因为这个原因。 例如考虑这样一个循环它处理容器中的每个元素在其后添加一个新元素。我们希望循环能跳过新添加的元素只处理原有元素。在每步循环之后我们将定位迭代器使其指向下一个原有元素。如果我们试图“优化”这个循环在循环之前保存end ()返回 的迭代器一直用作容器末尾就会导致一场灾难
//灾难 此循环的行为是未定义的
auto begin v.begin();
auto end v.end(); //保存尾迭代器的数值是一个坏主意
while(begin ! end){//做一些处理//传入新值对begin进行重新赋值 否则他会失效begin;// 向前移动begin 因为我们想在这个元素之后插入元素begin v.insert(begin,42);begin;//向前移动跳过新加入的元素
}
此代码的行为是未定义的。在很多标准库实现上此代码会导致无限循环。问题在于我们将 end操作返回的迭代器保存在一个名为end的局部变量中。在循环体中我们向容器中添加了一个元素这个操作使保存在end中的迭代器失效了。这个迭代器不再指向v 中任何元素或是v 中尾元素之后的位置。如果在一个循环中插入/删除deque、string或vector中的元素不要缓存end返回的迭代器。必须在每次插入操作后重新调用end(),而不能在循环开始前保存它返回的迭代器
//更安全的做法是 每个循环添加/删除元素之后 都重新计算end
while(begin ! end){begin();// 向前移动begin 因为想在此元素之后插入元素begin v.insert(begin,42);//插入新值begin;//向前移动begin 跳过新加入的元素
}
