歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C++編程 – 快速查找一個對象

在初始階段會有大量數據增刪改,而後期很少有更改,後期大部分是查詢操作。

建立索引,使用排序的vector,使用二分法查找

以用戶信息為例

用戶信息包括,ID,名字,性別,手機號碼

 

class CGender
{
public:
 enum
 {
  Female=0,
  Male=1, 
  NotSpecified=2
 };
};

 


class CUser
{
public:
 UINT64 m_nID;
 CString m_strName;
 int m_nGender;
 UINT64 m_nPhoneNumber;

 

};

首先需要一個容器存儲數據。
使用關聯容器map還是使用順序容器vector?
關聯容器的map元素以鍵值(key,value)對的形式組織,正好用key表示索引,如果無論什麼時候都會增刪改查,那麼使用map正好。
但是本例在初始階段有大量數據增刪改,而後期很少有更改大部分都是查詢操作。
所以使用排序的vector更好。 

定義用戶列表和索引

vector存儲什麼?
vector 通過push_back 之類的操作向容器中寫入對象時,存入容器的是對象的拷貝。
在繼承關系的情況下,拷貝動作會導致切片(slicing )。如果創建了一個存放基類對象的容器,插入了派生類的對象,派生類中特有的部分將會丟失。
所以vector中要存儲的是指針(CUser*)而不是對象(CUser)。
因為要建立索引所以vector存儲了pair<K, V>,相當於模仿了map,key是用戶ID,value是指針(CUser*)


使用new創建一個對象時,需要注意
1如果只有new,沒有delete就會產生資源洩漏
2單個對象要用delete,數組對象用deleter[]
3一個對象delete多次就出錯
4因為vector存儲的是指針,所以在vector在析構前要將指針delete

為了避免資源洩漏采用智能指針shared_ptr

typedef std::pair<UINT64,std::shared_ptr<CUser>> USER;

建立針對用戶操作的引擎

插入

根據ID查看是否存在該用戶

根據ID查找用戶

 

class CUserEngine
{
public:
 
 static std::vector<USER> m_vecUser;
 static void InsertUser(std::shared_ptr<CUser> p);
 static bool IsExist(UINT64 nID);
 static std::shared_ptr<CUser> QueryUserByID(UINT64 nID);

 

};

實現插入

一個自定義比較函數

//小ID在前
bool UserIDSort (const USER& a, const USER& b)
{
 return (a.first < b.first);
}

void CUserEngine::InsertUser(std::shared_ptr<CUser> p)
{
 m_vecUser.push_back(USER(p->m_nID,p));
 std::sort(m_vecUser.begin(),m_vecUser.end(),UserIDSort);

}

實現查找用戶

因為不知道哪個參數先傳遞所以需要兩個用於查找的比較函數:一個key值先傳遞,一個value先傳遞

struct UserIDCompare
{
 bool operator()(USER user, UINT64 nID) const
 {
  return user.first < nID;
 }
 bool operator()(UINT64 nID, USER user) const
 {
  return nID < user.first;
 }
};

bool CUserEngine::IsExist(UINT64 nID)
{
 return std::binary_search(m_vecUser.begin(),m_vecUser.end(),nID,UserIDCompare());
}


std::shared_ptr<CUser> CUserEngine::QueryUserByID(UINT64 nID)
{
 std::shared_ptr<CUser>p=nullptr;

 std::vector<USER>::iterator iter=std::lower_bound(m_vecUser.begin(),m_vecUser.end(),nID,UserIDCompare());
 if (iter!=m_vecUser.end() && !(UserIDCompare()(nID,*iter)))
 {
  p=(*iter).second;
 }
 return p;

}

測試

//隨機生成用戶信息
std::default_random_engine dre;
std::uniform_int_distribution<int> diGender(CGender::Female,CGender::NotSpecified);
std::uniform_int_distribution<UINT64> diPhoneNUmber(10000000000,19999999999);


for (int i=1;i<10;i++)
{
 std::shared_ptr<CUser> p(new CUser());
 p->m_nID=i;
 p->m_nGender=diGender(dre);
 p->m_nPhoneNumber=diPhoneNUmber(dre);
 CUserEngine::InsertUser(p);
}
for each(auto e in CUserEngine::m_vecUser)
{
 //輸出用戶信息
}

if(CUserEngine::IsExist(5))
{
 //查找是否存在ID為5的用戶
}
std::shared_ptr<CUser> p=CUserEngine::QueryUserByID(3);
if (nullptr!=p)
{
 //輸入ID為3的用戶信息
}

以上程序在win7+VC++2010下調試通過

C++ 設計新思維》 下載見 http://www.linuxidc.com/Linux/2014-07/104850.htm

C++ Primer Plus 第6版 中文版 清晰有書簽PDF+源代碼 http://www.linuxidc.com/Linux/2014-05/101227.htm

讀C++ Primer 之構造函數陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm

讀C++ Primer 之智能指針 http://www.linuxidc.com/Linux/2011-08/40177.htm

讀C++ Primer 之句柄類 http://www.linuxidc.com/Linux/2011-08/40175.htm

將C語言梳理一下,分布在以下10個章節中:

  1. Linux-C成長之路(一):Linux下C編程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
  2. Linux-C成長之路(二):基本數據類型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
  3. Linux-C成長之路(三):基本IO函數操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
  4. Linux-C成長之路(四):運算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
  5. Linux-C成長之路(五):控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
  6. Linux-C成長之路(六):函數要義 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
  7. Linux-C成長之路(七):數組與指針 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
  8. Linux-C成長之路(八):存儲類,動態內存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
  9. Linux-C成長之路(九):復合數據類型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
  10. Linux-C成長之路(十):其他高級議題

Copyright © Linux教程網 All Rights Reserved