map 和 set 的一起使用"/>
map 和 set 的一起使用
map 和 set 一起使用的场景其实也蛮多的,最近业务上就遇到了。需求是这样的,一条路径(mpls中的lsp)会申请多个 id,这个 id 是独一无二的。这里很显然就就一个”一对多“的情况,合适用这个容器不保存这些信息,如:std::map<uint32_t, std::set<bundle_set>> mLdpIdmMap; 下面为一个完成的可编译运行的代码,只是功能并不完善。
#include <mutex>
#include <map>
#include <set>
#include <string.h>#define IDM_BUNDLE_SET 9 //一个bundle 9 个set
#define BUNDLE_SET_ID 8 //每个 set 8 个id
#define IDM_MALLOC_16 16 //一次 16 个id
#define IDM_MALLOC_32 32int g_ECMP = 70;struct bundle_set
{uint32_t baseId;uint32_t endId;bool operator< (const bundle_set &a)const{return baseId < a.baseId;}
};
struct bundle_data
{uint32_t allocaNum; //一个bundle里已经分配的个数 bundle_set setId[IDM_BUNDLE_SET];
};class idm_bundle_manager
{
public:int assign(uint32_t baseId, uint32_t num, uint32_t ldpIdx);int getLdpById(uint32_t idmId);int getSetById(uint32_t idmId);void dumpBundleAll() const;void dumpBundleByIdx(uint32_t index) const;void dumpLdpAll()const;void dumpByLdpIdx(uint32_t ldpIdx)const;static idm_bundle_manager *instance();virtual ~idm_bundle_manager();
private:uint32_t mBundleIdx; //第几个 bundleuint32_t mSetIdx; //bundle里第几个set, 一共有9个setuint32_t mIdInBundle; //一个bundle里id数,为 IDM_BUNDLE_SET * BUNDLE_SET_IDuint32_t mBundleNum; //bundle总个数std::mutex mtx;bundle_data *mBundle;std::map<uint32_t, std::set<bundle_set>> mLdpIdmMap;private:int32_t findIdleBundle(uint32_t bundleIdx, uint32_t num);bool insertLdpIdm(uint32_t ldpIdx, uint32_t baseId, uint32_t num);idm_bundle_manager();idm_bundle_manager(const idm_bundle_manager&);idm_bundle_manager& operator=(const idm_bundle_manager&);
};idm_bundle_manager::idm_bundle_manager():
mBundleIdx(0),
mSetIdx(0),
mIdInBundle(IDM_BUNDLE_SET * BUNDLE_SET_ID),
mBundleNum(0),
mBundle(NULL)
{mBundleNum = (g_ECMP % IDM_BUNDLE_SET == 0)? g_ECMP / IDM_BUNDLE_SET : (g_ECMP % IDM_BUNDLE_SET + 1);mBundle = (bundle_data*)malloc(sizeof(bundle_data) * mBundleNum);memset(mBundle, 0, sizeof(bundle_data) * mBundleNum);
}idm_bundle_manager::~idm_bundle_manager()
{if(mBundle){free(mBundle);mBundle = NULL;}
}int32_t idm_bundle_manager::findIdleBundle(uint32_t bundleIdx, uint32_t num)
{uint32_t i = 0;for(i = 0; i < mBundleNum; i++) //全部找一遍,因为分配的num不一样导致各个bundle剩余的空间也不一样{if(i == bundleIdx) //当前那个不找{continue;}if(mIdInBundle - mBundle[i].allocaNum >= num){return i;}}return -1;
}int idm_bundle_manager::assign(uint32_t baseId, uint32_t num, uint32_t ldpIdx)
{std::lock_guard<std::mutex> guard(mtx);if(mBundleIdx >= mBundleNum) //bundle到最后一个时,重新从0开始{mBundleIdx = 0;}//当前的 bundle 已经不够容纳 num 个id,找一个空闲的 bundleif(num > mIdInBundle - mBundle[mBundleIdx].allocaNum){uint32_t idx = findIdleBundle(mBundleIdx, num);if(-1 == idx){return 0;//找不到能够容纳 num 的 bundle 了}mBundleIdx = idx;}//算出在bundle里的第几个set(0~8)mSetIdx = (mBundle[mBundleIdx].allocaNum == 0) ? 0 : mBundle[mBundleIdx].allocaNum / 8;if(IDM_MALLOC_32 == num){}else if(IDM_MALLOC_16 == num) //一次16个,跨两个 set{mBundle[mBundleIdx].setId[mSetIdx].baseId = baseId;mBundle[mBundleIdx].setId[mSetIdx].endId = baseId + IDM_MALLOC_16 / 2;mBundle[mBundleIdx].setId[mSetIdx + 1].baseId = baseId + IDM_MALLOC_16 / 2;mBundle[mBundleIdx].setId[mSetIdx + 1].endId = baseId + num;mBundle[mBundleIdx].allocaNum += num;}else{mBundle[mBundleIdx].setId[mSetIdx].baseId = baseId;mBundle[mBundleIdx].setId[mSetIdx].endId = baseId + num;mBundle[mBundleIdx].allocaNum += num; }mBundleIdx += 1;//直接插入map,if(!insertLdpIdm(ldpIdx, baseId, num)){printf("insert ldpIdx(%u) fail\n", ldpIdx);}return mSetIdx;
}int idm_bundle_manager::getLdpById(uint32_t idmId)
{std::lock_guard<std::mutex> guard(mtx);for(auto ite : mLdpIdmMap){if(idmId >= ite.second.begin()->baseId && idmId <= ite.second.end()->endId){return ite.first;}}return 0;
}bool idm_bundle_manager::insertLdpIdm(uint32_t ldpIdx, uint32_t baseId, uint32_t num)
{bundle_set set{baseId, baseId + num -1 };auto ret = mLdpIdmMap[ldpIdx].insert(set);return ret.second;
}int idm_bundle_manager::getSetById(uint32_t idmId)
{std::lock_guard<std::mutex> guard(mtx);for(uint32_t bundleIdx = 0; bundleIdx < mBundleNum; bundleIdx++){for(uint32_t setId = 0; setId < IDM_BUNDLE_SET; setId++){if(idmId >= mBundle[bundleIdx].setId[setId].baseId && idmId <= mBundle[bundleIdx].setId[setId].endId){return setId;}} }return -1;
}void idm_bundle_manager::dumpBundleAll()const
{for(uint32_t i = 0; i < mBundleNum; i++){printf("bundle_index: %u\n", i);dumpBundleByIdx(i);}
}void idm_bundle_manager::dumpBundleByIdx(uint32_t bundleIdx) const
{if(bundleIdx >= mBundleNum){return;}for(uint32_t i = 0; i < IDM_BUNDLE_SET; i++){printf("\tset_index: %u\n", i);if(mBundle[bundleIdx].setId[i].baseId){for(uint32_t j = 0; j < BUNDLE_SET_ID; j++){ printf("\t %u ", mBundle[bundleIdx].setId[i].baseId + j);}}printf("\n");}
}void idm_bundle_manager::dumpByLdpIdx(uint32_t ldpIdx)const
{if(!mLdpIdmMap.empty()){printf("ldpidx = %u\n", ldpIdx);auto ret = mLdpIdmMap.find(ldpIdx);if(ret != mLdpIdmMap.end()){for(auto ite : ret->second){printf("%u %u\n", ite.baseId, ite.endId);}}}
}idm_bundle_manager *idm_bundle_manager::instance()
{static idm_bundle_manager _instance;return &_instance;
}#define g_IdmBundleManager (*idm_bundle_manager::instance())int main()
{//每次分配8个,最多能分配72次for(int i = 0; i < 2; i++){int baseId = 1024 + i * 8;g_IdmBundleManager.assign(baseId, 8, 1073741832);}//每次分配16个,最多能分配 bundleNum * 4 次// for(int i = 0; i < 33; i++)// {// int baseId = 10024 + i * 16;// g_IdmBundleManager.assign(baseId, 16);// }g_IdmBundleManager.dumpBundleAll();g_IdmBundleManager.dumpByLdpIdx(1073741832);// int idm_id = 10808;// int setId = g_IdmBundleManager.getSetById(idm_id);// printf("setId of %d is %d\n", idm_id, setId);return 0;
}
这里主要借这个说明一下 set,set 里的元素是唯一的,且是有序的,它和 map 的底层实现同样的红黑树,所以如果 set 的元素类型是自定义类型的,则必须要实现 operator< 否则是无法编译的。如:
因为 set 的元素是有序的,所以每次插入元素都要进行比较。那实现 operator> 是否可行 ,反正都是比较,其实是不行的,因为它底层实现就是用的 小于号 < ,如错误所示。
使用 auto 进行插入及读取数据的代码:
int idm_bundle_manager::getLdpById(uint32_t idmId)
{std::lock_guard<std::mutex> guard(mtx);for(auto ite : mLdpIdmMap){if(idmId >= ite.second.begin()->baseId && idmId <= ite.second.end()->endId){return ite.first;}}return 0;
}bool idm_bundle_manager::insertLdpIdm(uint32_t ldpIdx, uint32_t baseId, uint32_t num)
{bundle_set set{baseId, baseId + num -1};auto ret = mLdpIdmMap[ldpIdx].insert(set);return ret.second;
}
更多推荐
map 和 set 的一起使用
发布评论