C++:list和forward_list操作元素

一些资料

来自书上的一些资料.留作参考.

在向容器添加元素后:

  • 如果容器是vectorstring,且存储空间被重新分配,则指向容器的迭代器、指针、和引用都会失效。
    如果存储空间未重新分配,指向插入位置之前的元素的迭代器、指针和引用仍有效,但指向插入位置之后元素的迭代器、指针和引用都会失效。
  • 对于deque,插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素,迭代器会失效,但指向存在的元素的引用和指针不会失效。
  • 对于listforward_list,指向容器的迭代器(包括尾后迭代器和首前迭代器)、指针和引用仍有效。

当我们从一个容器删除元素喉,指向被删除元素的迭代器、指针和引用会失效,这应该不会令人惊讶。毕竟,这些元素都已经被销毁了。当我们删除一个元素后:

  • 对于listforward_list,指向容器其他位置的迭代器(包括尾后迭代器和首前迭代器)、引用和指针仍有效。
  • 对于deque,如果在首尾之外的任何位置删除元素,那么指向被删除元素外其他元素的迭代器、引用、指针也会失效
    如果是删除deque的尾元素,则尾后迭代器也会失效,但其他迭代器、引用和指针不受影响;如果是删除首元素,这些也不会受影响。
  • 对于vectorstring,指向被删除元素之前的迭代器、引用和指针仍有效。
  • 请注意:当我们删除元素时,尾后迭代器总是会失效。使用失效的迭代器、指针或引用是严重的运行时错误!!

问题

请使用C++11进行编译运行.

从list和forward_list中删除偶数元素并复制奇数元素.

C++.
image-2052

源码


/*************************************************************************
> File Name: test.9.31.cpp
> Author: puruidong
> Mail: 1@w1520.com
> Created Time: 2014年05月18日
************************************************************************/

#include
#include #include
#include
using namespace std;

/*****************************
题目要求:
从list和forward_list中删除偶数元素并复制奇数元素.

-------------------------------------------------------------------
vector删除偶数值元素并复制奇数值元素的程序不能用于list或
forward_list。为什么?修改程序,使之可以用于list和forward_list.
---------------------------------------------------------------------
在list和forward_list容器中,添加/删除元素之后,引用,迭代器,指针
均还有效。

对于vector,指向被删元素之前元素的迭代器、引用和指针仍有效。
当我们删除元素时,尾后迭代器总是会失效.

****************************************/

int main()
{
list lis={0,1,2,3,4,5,6,7};
forward_list flt = {11,22,33,44,55,66,77,88,99,0};
for(list::iterator it=lis.begin();it!=lis.end();)//不要在这里累加迭代器
{
if(*it%2!=0)
{
it=lis.insert(it,*it);//复制当前元素.
advance(it,2);
//forward_list未定义+=符号.所以报错.
//it+=2;
}else
{
it=lis.erase(it);
}
}

for(forward_list::iterator its=flt.begin();its!=flt.end();)//不要在这里累加迭代器
{
if(*its%2!=0)
{
its = flt.insert_after(its,*its);
advance(its,2);//向后移动2个指针,作用与下面的相同.
//its+=2;
}else
{
its = flt.erase_after(its);
}
}

//输出处理后的值.
for(forward_list::const_iterator ita=flt.cbegin();ita!=flt.cend();++ita)
{
cout << "forward_list输出:" << *ita << endl; } for(list::const_iterator itb=lis.cbegin();itb!=lis.cend();++itb)
{
cout << "list输出:" << *itb << endl; } return 0; }

C++:forward_list尾部添加元素

“棘手”的问题

请使用C++11新标准编译运行.[此源码并非一个完美的解决方案.仅供测试学习.]

编写函数,接受一个forward_list和两个string共三个参数。函数应在链表中查找第一个string,并将第二个string插入到紧接着第一个string之后的位置.若第一个string未在链表中,则将第二个string插入到链表中。

从前面向forward_list插入数据很简单,而从尾部插入数据则难度很大。目前这个解决方案解决了题目的问题,但明显不是最好的解决方案。

C++.
image-2048

源码


/*************************************************************************
> File Name: test.9.28.cpp
> Author: puruidong
> Mail: 1@w1520.com
> Created Time: 2014年05月16日 星期五 18时42分53秒
************************************************************************/

#include
#include
#include
#include
using namespace std;

//只用作输出.
void out(const forward_list &lst,const string title)
{
cout << title << endl; for(forward_list::const_iterator it=lst.cbegin();it!=lst.cend();++it)
{
cout << *it << endl; } cout << "----------------------" << endl; } void insertFor(forward_list &lst,string name1,string name2)
{

/*
* 实现流程[当没有找到name1时,将name2添加到最后面.]:
* 1.先将原有数据保存到vector[可逆序输出]
* 2.用name2替换原有的内容
* 3.逆序将vector中的内容,添加到forward_list中.
*----------------------------------------------
* 当有name1的时候,直接添加完跳出循环即完成.
*/
vector vec(lst.begin(),lst.end());//拷贝lst中的值.
out(lst,"输出未改变前的forward_list:");//输出刚才获取的值.
for(forward_list::iterator it=lst.begin();it!=lst.end();++it)
{//用于查找,替换.
if((*it)==name1)//forward_list里面有name1.
{
lst.insert_after(it,name2);//插入到当前位置之后的位置.
break;//找到加入值之后就可以退出循环了.
}
else
{//没找到name1的值,用name2替换原来的值.
lst.assign({name2});//替换.
for(vector::reverse_iterator itsa=vec.rbegin();itsa!=vec.rend();++itsa)
{
lst.push_front(*itsa);//将已经被替换掉的逆序元素添加回去.
}
}
}
out(lst,"输出已经改变后的值");

}

int main()
{
forward_list lst = {"test","demo","java","cpp","c","hello"};
string name1 = "test",name2="slkjsd";//模式1
//string name1 = "testssa",name2="slkjsd";//模式2
insertFor(lst,name1,name2);//查找及替换.
return 0;
}