企业官网建设流程全解析

以下代码中,s是待删除元素的数组.v_deleted以s德索引为索引，指出s中索引对应的元素是否需要删除.即若v_deleted[i]=true,则s[i]需要删除,否则应当保留
算法的目标是删除s中所有被v_deleted标记的元素,同时返回一个数组,数组索引为i的元素指出被删除元素后的s索引为i的元素在删除前的s中的索引.
该算法有两种不同的实现，分别由delete_in_list和delete_in_list2两个函数给出
两种算法的最明显的不同之处在于,delete_in_list先将s拷贝到链表assist_space,在assist_space上删除，再把assist_space拷贝回s,而delete_in_list2直接在s上执行删除,这样当s非常大或要删除的元素很多且T的析构开销非常大时, delete_in_list的效率会比delete_in_list2更高
C++代码:

#include<iostream>#include<vector>#include<list>usingstd::vector;usingstd::list;template<typenameT>vector<size_t>delete_in_list(vector<T>&s,constvector<int>&v_deleted)//从left中删除被标记被删除的顶点,返回旧顶点索引和新索引映射关系的数组{vector<size_t>assist_v(s.size());for(size_t k=0;k<assist_v.size();++k){assist_v[k]=k;}list<T>assist_space;assist_space.insert(assist_space.end(),s.begin(),s.end());boolfind_new_delete_start=false;size_t new_delete_start_index=0;size_t new_delete_start_for_assist=0;typenamelist<T>::iterator it=assist_space.begin();size_t k=0;for(;k<s.size();++k){if(v_deleted[k]==1){if(find_new_delete_start==false){find_new_delete_start=true;new_delete_start_index=k;}}else{if(find_new_delete_start){autod_r=assist_v.erase(assist_v.begin()+new_delete_start_for_assist,assist_v.begin()+(new_delete_start_for_assist+k-new_delete_start_index));autorun_it=it;for(size_t m=0;m<k-new_delete_start_index;++m){++run_it;}it=assist_space.erase(it,run_it);find_new_delete_start=false;new_delete_start_for_assist=d_r-assist_v.begin();}++new_delete_start_for_assist;++it;}}if(find_new_delete_start){assist_v.erase(assist_v.begin()+new_delete_start_for_assist,assist_v.end());assist_space.erase(it,assist_space.end());}//size_t v_num_before_delete = left.size();s.clear();s.insert(s.end(),assist_space.begin(),assist_space.end());/*vector<size_t> index_after_delete_to_original(v_num_before_delete); for (size_t m = 0; m < assist_v.size(); ++m) { index_after_delete_to_original[assist_v[m]] = m; }*/returnassist_v;}template<typenameT>vector<size_t>delete_in_list2(vector<T>&s,constvector<int>&v_deleted){typenamevector<T>::iterator it=s.begin();vector<size_t>assist_v(s.size());for(size_t i=0;i<assist_v.size();++i){assist_v[i]=i;}vector<size_t>::iterator run_a=assist_v.begin();typenamevector<T>::iterator delete_start;vector<size_t>::iterator delete_start_a;while(true){while(it!=s.end()&&v_deleted[*run_a]==0){++it;++run_a;}if(it==s.end()){break;}delete_start=it;delete_start_a=run_a;do{++it;++run_a;}while(it!=s.end()&&v_deleted[*run_a]==1);it=s.erase(delete_start,it);run_a=assist_v.erase(delete_start_a,run_a);if(it==s.end()){break;}}returnassist_v;}//当s非常大或要删除的元素很多且T的析构开销非常大时, delete_in_list的效率会比delete_in_list2更高template<typenameT>voidsubset(vector<int>&v_deleted,size_t index,constvector<T>&s){if(index==s.size()){vector<T>t1=s;vector<size_t>r1=delete_in_list2(t1,v_deleted);vector<T>t2=s;vector<size_t>r2=delete_in_list(t2,v_deleted);if(t1!=t2||r1!=r2){std::cout<<"error"<<std::endl;exit(-1);}return;}v_deleted[index]=0;subset(v_deleted,index+1,s);v_deleted[index]=1;subset(v_deleted,index+1,s);}intmain(){constintN=5;vector<int>s(N);for(inti=0;i<N;++i){s[i]=i;}vector<int>v_deleted(N);subset(v_deleted,0,s);return0;}