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++ 设计新思维》 下载见

C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码

读C++ Primer 之构造函数陷阱

读C++ Primer 之智能指针

读C++ Primer 之句柄类

将C语言梳理一下，分布在以下10个章节中：

  1. Linux-C成长之路（一）：Linux下C编程概要
  2. Linux-C成长之路（二）：基本数据类型
  3. Linux-C成长之路（三）：基本IO函数操作
  4. Linux-C成长之路（四）：运算符
  5. Linux-C成长之路（五）：控制流
  6. Linux-C成长之路（六）：函数要义
  7. Linux-C成长之路（七）：数组与指针
  8. Linux-C成长之路（八）：存储类，动态内存
  9. Linux-C成长之路（九）：复合数据类型
  10. Linux-C成长之路（十）：其他高级议题

本文永久更新链接地址：

相关内容