我个人常用stl vector来构建基础数据结构,实现一些算法。有时候会有这样的需求,就是我要删除满足某些条件的vector中的元素,例如:删除所有大于零的元素。这就需要遍历整个数组,找到这些元素,并且删除。有两种策略。直观的一种是在遍历的过程中,判断当前元素是否符合删除条件,如果符合,则调用vector的erase函数进行删除,注意这时候数组内容发生变化,iterator原则上失效,会影响到遍历过程。
不过我更在意这种策略的效率。调用erase函数的时候,所有当前删除位置之后的元素都向前移动一个位置。当数组元素是n个、待删除元素是m个的时候,算法复杂度是O(mn)。有点高,不利索。
另一种策略,就是今天列出来的,简单地说就是用空间来换时间。用一个n大小的vector存放0-1变量,1表示目标vector的这个位置的元素要删除,0表示要保留。同时遍历目标vector和这个标志vector,一次性删除所有要删除的元素。在时间上,因为在生成标志vector的时候需要遍历目标vector,在删除的时候,又要遍历一遍,所以总共遍历两遍,复杂度是O(2n)=O(n)。当待删除元素数目比较大的时候,这个算法还是比较有效率的。需要注意的是:1. 在删除过程中要同时遍历两个vector;2. 对于目标vector,需要维护两个下标,一个是遍历的当前位置下标,一个是写元素位置下标。
核心代码如下:
bool RmSomeElementsInVec (vector<int> & NumVec, vector<bool> & FlagVec)
{
int iSize = (int)NumVec.size(); //目标数组大小
if (iSize != (int)FlagVec.size()) //防御性代码
return false;
int iWritePos = 0; // 写位置下标,数组后续元素不断向前移动,这个是下一个要移动到的位置
for (int iIterPos = 0; iIterPos < iSize; iIterPos++)
{
if (!FlagVec.at(iIterPos)) // flag是0,表示保留当前位置的元素在数组中
{
if (iWritePos != iIterPos) // 将该元素移动到正确的位置上,同时避免在同一个位置上写操作,以提高效率
NumVec.at (iWritePos) = NumVec.at (iIterPos);
iWritePos++;
}
}
if (iSize != iWritePos) //缩减数组大小到实际大小
NumVec.resize (iWritePos);
return true;
}
写个程序做了两个假的输入数组NumVec和FlagVec,用来测试上面的代码,测试通过。代码如下:
void InitNumVecAndFlagVec (vector<int> & NumVec, vector<bool> & FlagVec)
{
for (int i=0; i<1000; i++)
{
NumVec.push_back (Array[i]);
if (0 == i%2)
FlagVec.push_back (1);
else
FlagVec.push_back (0);
}
}
只保留偶数位置上的元素。Array是一个已经初始化好的数组,大小是1000。
还有更进一步的做法。如果生成n大小的flag vector比较浪费空间的话,可以只把需要删除的位置记录下来,记录到一个小于n的vector中。在删除的过程中,类似上面的过程,同时遍历两个vector,进行元素删除,代码如下:
bool RmSomeElementsInVec2 (vector<int> & NumVec, vector<int> & PosVec)
{
int iNumSize = (int)NumVec.size ();
if (0 == iNumSize)
return false;
int iPosSize = (int)PosVec.size();
if (0 == iPosSize)
return true;
for (int i=0, j=0, iWritePos=0; i<iNumSize, j<iPosSize; )
{
if (i < PosVec.at(j))
{
if (i != iWritePos)
NumVec.at (iWritePos) = NumVec.at (i);
i++;
iWritePos++;
}
else if (i == PosVec.at (j))
{
i++;
j++;
}
else
cerr << "Never get here" << endl;
}
return true;
}
由于遍历的两个vector长度不一样,就需要多一个下标变量。思路和上面的差不多,我就没有补充注释。同样,伪造了NumVec和PosVec,用来测试,代码如下:
void InitNumVecAndPosVec (vector<int> & NumVec, vector<int> & PosVec)
{
for (int i=0; i<1000; i++)
{
NumVec.push_back (Array[i]);
if (0 == i%2)
PosVec.push_back (i);
}
}
测试通过。
分享到:
相关推荐
STL vector 知识详解 STL vector 知识详解 STL vector 知识详解 STL vector 知识详解 STL vector 知识详解
SGI STL之vector源码,带注释
c++的STL的vector的一个实现。使用了c++11的大部分特性,包含vector的几乎所有功能。仅作学习之用。
使用VC++控制台应用程序编写,测试了:vector对象的排序,对象中的大小无序,有重复。
STL中vector、list、deque和map的区别
C++ 利用MAP和VECTOR实现多节点树,VC++ 利用STL中的MAP和VECTOR实现的一个多节点树。
该文档详细讲解了C++中标准容器的使用,是一份不错的学习资料哦
c++ STL source code, hash and vector etc
vector list map pair stl 标准模板库 c++ 程序示例
心希盼 c++ STL Vector 类源码 详细说明“心希盼 Vector.doc”
详细讲解了STL中vector容器的用法.
SGI vector源码
实现统计一段文章的每个单词的个数 其中CountDemo使用STL中的Map来实现的 CountDemo2是用一般语言实现,没有用到STL实现的; MapCount是用STL中的Vector和Map共同实现的...此题目是学习STL中的Map和Vector必练的经典题目
C++STL vector list map set dqueue 等应用举例及PPT讲解示例,代码演示
仿写C++ STL标准库 vector 源码,可直接在cpp文件中调用实现
非常实用的STL容器讲解学习,内容全,讲解详细 包括Vector、Vector、String、Deque、sort、set、map,绝对有用!!
给大家介绍 stl vector用法,主要知识点在如何恰当的使用它们的成员函数,涉及到条件函数和函数指针在迭代算法中的使用,对stl vector用法感兴趣的朋友可以参考下本
标准模板库中map、vector、以及sort等的用法讲解
每个Timer的对象有一个编号(可以是一个无符号的long或 short),以方便在全局中区分每个Timer对象。 基类提供一个纯虚函数GetTimerID 来取得Timer的编号。
STL VECTOR 、迭代器,DEV C++ 编译运行