c++map使用自定义结构做关键字

map在STL中的定义

template , class Alloc = alloc> 第⼀个参数Key是关键字类型第⼆个参数T是值类型

第三个参数Compare是⽐较函数（仿函数）第四个参数是内存配置对象

map内部存储机制实际是以红⿊树为基础，红⿊树在插⼊节点时，必须依照⼤⼩⽐对之后在⼀个合适的位置上执⾏插⼊动作。所以作为关键字，起码必须有“<”这个⽐较操作符。我们知道，int，float，enum，size_t等等简单关键字，都有内置的⽐较函数，与map搭配⽆论是插⼊还是查找，都没什么问题。但是作为复杂数据类型，如果没有明确定义“<”⽐较操作符，就不能与map直接搭配使⽤，除⾮我们⾃⼰定义第三个参数。

在选择map的关键字时，注意以下两点，同时这两点也是改错的⽅法：a） 关键字明确定义“<”⽐较操作符

b） 没有“<”⽐较操作符，⾃定义仿函数替代第三个参数Compare，该仿函数实现“()”操作符，提供⽐较功能。插⼊时各节点顺序以该仿函数为纲。

以std::pair为关键字掺⼊map

下⾯我们先写⼀个有错误的函数，在分析错误原因之后，逐步进⾏修正。#include

std::map, int> res; res.insert(std::make_pair(12,33), 33);}

这个程序⼀定失败，如果⾮要如此使⽤，上述a⽅法显然不适合，std::pair是已定义好的结构体不可修改。只能使⽤b⽅法了，定义⼀个⽐较类改造如下：

#include

struct comp {

typedef std::pair value_type;

bool operator () (const value_type & ls, const value_type &rs)

{

return ls.first < rs.first || (ls.first == rs.first && ls.second < rs.second);

} };

int main() {

std::map, int, comp> res;

res.insert(std::make_pair(std::make_pair(12,33), 33));

res.insert(std::make_pair(std::make_pair(121,331), 331));

res.insert(std::make_pair(std::make_pair(122,332), 332));

std::map, int, comp>::iterator it = res.find(std::make_pair(121,331));

if (it == res.end())

printf(\"NULL\"n\");

else

printf(\"%d %d %d \"n\

return 0; }

以结构体或类为关键字插⼊map

#include

struct st {

int a, b;

st():a(0), b(0){}

st(int x, int y):a(x), b(y){} };

int main() {

std::map res;

res.insert(std::make_pair(st(1,2), 12));

res.insert(std::make_pair(st(30,4), 34));

res.insert(std::make_pair(st(5,6), 56));

std::map::iterator it = res.find(st(30,4));

if (it == res.end())

printf(\"NULL\"n\");

else

printf(\"first:%d second:%d %d\"n\

return 0; }

编译这个程序也是错误的，错误意思⼤概也是没有定义“<”⽐较函数。因为struct st是我们⾃⼰定义的结构体，所以修改这个程序可以使⽤上⾯a、b两种⽅法。我们先谈第⼀种，第⼀次修改时我也搞错了，我是这样定义⽐较函数的。

struct st {

int a, b;

st():a(0), b(0){}

st(int x, int y):a(x), b(y){}

bool operator < (const struct st &rs) {return (this->a < rs.a || (this->a == rs.a && this->b < rs.b));} };

按照这个改动再次编译程序还是错误，有个如下这样的提⽰：

/usr/include/c++/3.2.3/bits/stl_function.h:197: passing `const st' as `this' argument of `bool st::operator<(const st&)' discards qualifiers 为什么会出现这个 问题呢？我们深⼊STL的源代码看下。既然说是/usr/include/c++/3.2.3/bits/stl_function.h的197⾏出了问题，且看这⾏是什么。

／／ One of the @link s20_3_3_comparisons comparison . template

struct less : public binary_function<_Tp,_Tp,bool>

　{

bool operator()(const _Tp& __x, const _Tp& __y) const { return __x < __y; } 　 };

struct st中的“<”在编译后真正是什么样⼦呢？⼤概是bool operator < (struct st &ls, const struct st &rs)。在less调⽤这个⽐较符时，它都是以const⽅式传⼊，不可能再以⾮const⽅式调⽤，故出错。修正如下struct st{

int a, b; st():a(0), b(0){}

st(int x, int y):a(x), b(y){}

friend bool operator < (const struct st &ls, const struct st &rs);};

inline bool operator < (const struct st &ls, const struct st &rs){return (ls.a < rs.a || (ls.a == rs.a && ls.b < rs.b));}

以友联函数代替函数内部定义的⽐较操作符，STL内部也多是以这种⽅式定义的。如果我⾮要以内部定义的⽅式呢？可以使⽤b⽅法，我们⾃定义⼀个⽐较仿函数，替代默认的less。插⼊函数返回值

在map容器中插⼊数据有很多函数可⽤，这⾥只讨论最普通的insert操作，在STL中它是这样定义的。

pair insert(const value_type& x);

map容器不允许键值重复，在执⾏插⼊操作后，可以凭借该返回值获取操作结果。返回值是⼀个迭代器和布尔值的键值对，迭代器指向map中具有该值的元素，布尔值表⽰是否插⼊成功。如果布尔值为true，表⽰插⼊成功，则迭代器为新插⼊值在map中的位置；布尔值为false，表⽰插⼊失败（已经存在该值），迭代器为原有值在map中的位置。

#include

class Key {

public: Key(); Key(int v); int _key; ~Key();

/*重载<作为成员函数不⾏，两个操作数都要求是const*/ //bool operator <(const Key& key); };

bool operator <(const Key &key1,const Key &key2) {

if(key1._keyreturn false; }

Key::Key() { }

Key::Key(int v) {

_key=v; }

Key::~Key() { }

void main() {

map ClassMap; Key one(1);

ClassMap.insert(make_pair(one,1)); Key two(2);

ClassMap.insert(make_pair(two,2)); Key three(3);

ClassMap.insert(make_pair(three,3));

map::iterator itor=ClassMap.begin(); while(itor!=ClassMap.end()) {

cout<first._key<<\" ~~ \"<second<纠正上例中的⼀个错误，重载<的时候，也可以这么做：

#include

#include using namespace std;

class Key {

public: Key(); Key(int v); int _key; ~Key();

bool operator <(const Key& key) const; };

bool Key::operator <(const Key &key) const {

if(this->_keyreturn false; }

Key::Key() { }

Key::Key(int v) {

_key=v; }

Key::~Key() { }

void main() {

map ClassMap; Key one(1);

ClassMap.insert(make_pair(one,1)); Key two(2);

ClassMap.insert(make_pair(two,2)); Key three(3);

ClassMap.insert(make_pair(three,3));

map::iterator itor=ClassMap.begin(); while(itor!=ClassMap.end()) {

cout<first._key<<\" ~~ \"<second<