勤能补拙,Expter

成都游戏Coder,记录游戏开发过程的笔记和心得!

一个索引表 (风格,问题推广分析)


今天看到以前写的一个关于容器排序以及赋值问题。
先贴以前代码
#include <iostream>
#include 
<cstdlib>
#include 
<vector>
#include 
<algorithm>

using namespace std;

template
< class _RaType>
struct sort_idxtabl_pair 
{
                                                                          
// 数据容易暴露
    _RaType _ra; 
    
int     _val;

    
bool  operator < (const sort_idxtabl_pair &x)                         // 未声明未const函数
    {
        
return (*_ra) < (*(x._ra));
    }

    
void SetVal(_RaType & _r , int v) { _ra = _r ;  _val = v;}             // Set函数
}
;

template 
< class _RaType>
void Sort_index (_RaType first , _RaType last , int * tbl)
{
    typedef vector
< sort_idxtabl_pair<_RaType> > V;

    V vv(last
-first);                                        // 分配空间
    V::iterator vit = vv.begin();
    _RaType it 
= first; 
    
for (int i = 0 ; it <last ; it++,vit++,i++)                  // 重写
    {
            (
*vit).SetVal(it,i);
    }

                                                                            
// 排序
    std::sort(vv.begin(),vv.end());

    
int  *pi= tbl;
    vit 
= vv.begin();

    
for ( ; vit < vv.end(); pi++,vit++ )                                    // 赋值
    {
        
*pi = (*vit)._val;
    }

}



int main()
{
    
int arr[] = {10,9,8,7,6,4,2,3,1,5};

    vector
<int> val(arr,arr+10);                                            // 调用构造函数

    
int index[10];

    Sort_index(val.begin(),val.end(),index);

    
for(int i = 0 ; i <10 ; i++)
    
{
        cout 
<< " i = " << i                                                     // 输出数据
         << " , index[i] = " <<index[i]
             
<<" ,arr[index]= "<< arr[index[i]]
             
<<endl;
    }

    
    system(
"pause");
    
return 0;
}


运行结果
 i = 0 , index[i] = 8 ,arr[index]= 1
 i = 1 , index[i] = 6 ,arr[index]= 2
 i = 2 , index[i] = 7 ,arr[index]= 3
 i = 3 , index[i] = 5 ,arr[index]= 4
 i = 4 , index[i] = 9 ,arr[index]= 5
 i = 5 , index[i] = 4 ,arr[index]= 6
 i = 6 , index[i] = 3 ,arr[index]= 7
 i = 7 , index[i] = 2 ,arr[index]= 8
 i = 8 , index[i] = 1 ,arr[index]= 9
 i = 9 , index[i] = 0 ,arr[index]= 10
请按任意键继续. . .


1.分析风格,首先operator < 操作符 应该声明为const函数
2.排序函数应该更简单,很冗余
3.更多的复用
比如
template < class _RaType>
void Sort_index (_RaType first , _RaType last , int * tbl)
可以修改为

template 
< class _RaType, Out res>
void Sort_index (_RaType first , _RaType last , res  tbl)

4、在迭代器尽量不要写 <,应写!= 来比较


总结最近学习笔记,以及泛型编程 解决上面问题,以及风格问题:


 

方案一:
//  进行一些基本清理工作,运用原来数据结构
namespace s1
{
  template
<class _RaType>
  
class sort_idxtabl_pair{
        
   
public:
     
void SetVal(_RaType & _r , int v) { _ra = _r ;  _val = v;}
     
bool  operator < (const sort_idxtabl_pair &x) const                                 // 声明为const函数
    {
     
return (*_ra) < (*(x._ra));
    }

    
operator () constreturn _val);

   
private:
    
    _RaType _ra;
    
int     _val;
  }
;

  template 
< class _RaType , class ItOut>
    
void Sort_index (_RaType first , _RaType last , ItOut tbl)
  
{
   typedef vector
< sort_idxtabl_pair<_RaType> > V (last-first);            // 一个对象数组
   for ( int i = 0 ; i < last - first ; ++i) 
    V[i].SetVal(first
+i,i);                                                                                  // 调用每个对象方法
  
   sort(V.begin(),V.end());                                                                             
// 排序
   copy(V.begin(),V.end(),out);                                                                   // 调用copy函数
  }

}



方案二:
// 使用pair辅助类
namespace s2
{
  
//  比较方法
 template<class _RaType , class Val>
    
struct sort_idxtabl_pair{
         
bool  operator < (const pair<_RaType,Val>& x, const pair<_RaType,Val>& y ) const         // 声明为const函数
   {
     
return  *x.first < *b.first;
   }

 }
;
 
 template 
< class _RaType , class ItOut>
  
void Sort_index (_RaType first , _RaType last , ItOut tbl)
 
{
  typedef vector
< pair<_RaType,int> > V (last-first);                    // 对象数组
  for ( int i = 0 ; i < last - first ; ++i)                                                    // 利用pair来 添加新元素
   V[i]=std:make_pair(first+i,i);
  
  sort(V.begin(),V.end(),sort_idxtabl_pair
<_RaType,int>());       // 排序
  for (int i = 0 ; i <s.SIZE ; ++i ,++tbl)
    
*tbl = V[i].second;
  }

}


方案三:
//其实还可以利用multimap来消除单独排序步骤,利用transform来代替手写循环,


 

posted on 2009-03-08 14:58 expter 阅读(1220) 评论(2)  编辑 收藏 引用

评论

# re: 一个索引表 (风格,问题推广分析) 2009-04-26 13:51 lzmagic

写得真规范~
请问
typedef vector< pair<_RaType,int> > V (last-first); // 对象数组
就把V创建好了吗?  回复  更多评论   

# re: 一个索引表 (风格,问题推广分析) 2009-04-26 19:22 expter

@lzmagic

是的,调用构造函数。。。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理