std::map 自定义键的问题

gxsheng 2007-12-24 12:57:47

我自己定义了一个 struct MyKey{...}; 和一个 struct MyValue{...};

然后定义了一个 std::map<MyKey,MyValue>;

MyKey 是重载了 operator< 的。

但我每次用 std::map<MyKey,MyValue>::find 时，除非map是空的，其余情况都查找成功，而键的值明显是不同的。

我知道键值是用hash表管理的，在自定义key情况下，我如何才能正常使用find功能呢？

谢谢！

...全文

702 10 打赏收藏转发到动态举报

写回复

用AI写文章

10 条回复

切换为时间正序

请发表友善的回复…

发表回复

visame 2007-12-27

打赏
举报

gxsheng:
做得不错，学习学习！

gxsheng 2007-12-26

打赏
举报

谢谢大家.
知道问题所在了.
确实是符号重载的问题.

没用 class 是因为这是个很小的类,在结构中比较底层,数量多,频繁使用.

我把符号重载改成了:



	bool operator<(const GxEleCode& in )	const

	{

		int len = strlen(data) ;

		int inLen = strlen( in.data ) ;

		if( len < inLen )

			return  true ;



		WORD* pVal = (WORD*)data ;

		WORD* pInVal = (WORD*)(in.data) ;



		if( *pVal < *pInVal )

			return true ;



		return false ;

        }

就好了

Vitin 2007-12-26

打赏
举报

楼主的operator <没有满足strict weakly ordering.问题出在这里:



    if( data[0] < in.data[0] )

        return true ;



    if( data[1] < in.data[1] )

        return true ;

如果对两个GxEleCode对象a,b满足a.data[0]>b.data[0]并且a.data[1]<b.data[1],则同时得到a<b并且b<a.

应该这样修改:



    if( data[0] < in.data[0] )

        return true ;



    if(( data[0] == in.data[0] ) && ( data[1] < in.data[1] ))

        return true ;

visame 2007-12-26

打赏
举报

有几个地方不明白。
你的那个 Clear() ;是干什么的？
C++中很少使用memset...
另外，你存储中文汉字为什么不用wchar_t而是用char [3]？优点在哪里？
构造函数也不太规范，应该使用初始化列表。
而且我有把struct换成class的冲动。。。为什么用struct，为什么没有对一些数据成员进行private保护？
C++的特色没有体现出来啊。。。

struct GxEleCode

{

    char data[3] ;



    DWORD    frequency ;

    GxEleCode()

    {

        Clear() ;

    }

    GxEleCode(const char* pIn)

    {

        Clear() ;

        SetValue(pIn) ;

    }

    bool SetValue(const char* pIn)

    {

        if( !pIn )

            return false ;



        int len = strlen(pIn) ;



        if( len > 2 )

            return false ;



        // 汉字，但没拖尾，非法

        if( ( pIn[0] & 0x80 ) && len == 1 )

            return false ;



        for( int i = 0 ; i < len ; i ++ )

            data[i] = pIn[i] ;



        return true ;

    }

    void Clear()

    {

        memset(this , 0 , sizeof(GxEleCode)) ;

    }

    bool operator<(const GxEleCode& in )    const

    {

        if ( data[0] == in.data[0] && data[1] == in.data[1] && data[2] == in.data[2] )

            return false ;



        int len = strlen(data) ;

        int inLen = strlen( in.data ) ;

        if( len < inLen )

            return  true ;



        if( data[0] < in.data[0] )

            return true ;



        if( data[1] < in.data[1] )

            return true ;



        return false ;

    }

    bool operator==(const GxEleCode& in)

    {

        if( data[0] == in.data[0] && data[1] == in.data[1] && data[2] == in.data[2] )

            return true ;



        return false ;

    }

};

gxsheng 2007-12-25

打赏
举报

谢谢大家.
我修改了代码,已经可以编译通过,在VS2003下运行DEBUG时,发现问题:用 find 无法找到以前存在的键.
这个结构很简单,就是存储单个的英文/符号或者汉字.

请大家看看是否重载 operator<时，没完全满足条件。

我对排序的设想是：英文在前，中文在后；如果都是中文，分别以两个字节的大小来排。
我认为这样可以满足严格的先后顺序了。

成员 frequency 对排序有影响吗？我重载的<号运算里并没考虑它。



struct GxEleCode

{

	char data[3] ;



	DWORD	frequency ;

	GxEleCode()

	{

		Clear() ;

	}

	GxEleCode(const char* pIn)

	{

		Clear() ;

		SetValue(pIn) ;

	}

	bool SetValue(const char* pIn)

	{

		if( !pIn )

			return false ;



		int len = strlen(pIn) ;



		if( len > 2 )

			return false ;



		// 汉字，但没拖尾，非法

		if( ( pIn[0] & 0x80 ) && len == 1 )

			return false ;



		for( int i = 0 ; i < len ; i ++ )

			data[i] = pIn[i] ;



		return true ;

	}

	void Clear()

	{

		memset(this , 0 , sizeof(GxEleCode)) ;

	}

	bool operator<(const GxEleCode& in )	const

	{

		if ( data[0] == in.data[0] && data[1] == in.data[1] && data[2] == in.data[2] )

			return false ;



		int len = strlen(data) ;

		int inLen = strlen( in.data ) ;

		if( len < inLen )

			return  true ;



		if( data[0] < in.data[0] )

			return true ;



		if( data[1] < in.data[1] )

			return true ;



		return false ;

	}

	bool operator==(const GxEleCode& in)

	{

		if( data[0] == in.data[0] && data[1] == in.data[1] && data[2] == in.data[2] )

			return true ;



		return false ;

	}

};

dingdexin 2007-12-24

打赏
举报

你可以看看
写得不太好但可以说明问题

#include<map>
#include <string>
#include<iostream>
using namespace std;
typedef struct STU
{
int id;
string name;
bool operator<( STU const &A)const
{
if(id<A.id)
return true;
if(id==A.id)
return name<A.name;
return false;
}
}STUTYPE;

typedef struct STUdd
{
int aa;
int bb;
}STUTYPE2;
void main()
{
map<STUTYPE,STUTYPE2>m;
STUTYPE t1;
t1.id=1;
t1.name="aa";

STUTYPE2 t2;

t2.aa=2;
t2.bb=3;
m[t1]=t2;

t1.id=1;
t1.name="bb";

t2.aa=2;
t2.bb=4;
m[t1]=t2;
map<STUTYPE,STUTYPE2>::iterator p;
for(p=m.begin();p!=m.end();p++)
cout<<(p->first).id<<' '<<(p->first).name<<' '<<(p->second).aa<<' '<<(p->second).bb<<endl;
cout<<"find 1,aa:";
p=m.find(t1);
if(p!=m.end())
cout<<"has find:"<<(p->first).id<<' '<<(p->first).name<<endl;

cout<<"find 1,aaaa:";
t1.name="aaaa";
p=m.find(t1);
if(p!=m.end())
{
cout<<"has find:"<<(p->first).id<<' '<<(p->first).name<<endl;
}
else
cout<<"not find!";
}

calss_cyl 2007-12-24

打赏
举报

2楼说的对。

光跃 2007-12-24

打赏
举报

lz说的是这个意思吗：



typedef struct Key{

	int a;

	int b;

}MyKey;



typedef std::map<MyKey, string> __STDMAP;



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

	return key1.a < key2.a;

};

我试过了，调用map的find(),是可以正常查找的，没有出错啊

Vitin 2007-12-24

打赏
举报

首先纠正一个错误: std::map不是用hash表实现的,是用红黑树实现的;hash_map是用hash表实现的.
std::map::find的原型是 iterator map::find(const key_type& k).
输入一个键值,返回它在map中的iterator.
LZ的问题有必要表述得更详细一些,比如贴出代码,并用一个例子说明你的疑惑.
现在我只能大致地说,有以下两个可能:
1.非正确地使用了find.
2.非正确地定义了MyKey的operator <.它在语义上必须满足strict weakly ordering.

gxsheng 2007-12-24