说明:
         感谢luckycat陈梓瀚(vczh) 的留言。
         下面的代码已经在Windows VC6/ Cygwin/ Suse Linux环境下编译测试通过.

#include <iostream>
#include 
<list>
#include 
<string>
#include 
<cctype>

using namespace std;

typedef unsigned 
int    UINT32;
typedef unsigned 
short  UINT16;

/************************************************************************/
/* 枚举定义: 性别                                         */
/************************************************************************/
typedef 
enum enumSexyType
{
    SEXY_TYPE_MAN,   
//男性
    SEXY_TYPE_WOMAN, //女性
    SEXY_TYPE_GAY,   //男同性恋
    SEXY_TYPE_LESIBAIN, //女同性恋

    SEXY_TYPE_BUTT   
//未知性别
}ENUM_SEXY_TYPE;

/************************************************************************/
/* 结构体定义:  人                                                      */
/************************************************************************/
typedef 
struct structMan
{
    UINT32    sexType; 
// 性别 ENUM_SEXY_TYPE
    UINT16      usAge;   // 年龄
    string    strName; // 名字
    string    strAddress; // 工作地址
    
    
bool operator < (const structMan &man) const
    {
        
return usAge < man.usAge;
    }

    
bool operator > (const structMan &man) const
    {
        
return usAge > man.usAge;
    }

    structMan(UINT32 enumSexType 
= SEXY_TYPE_MAN,\
              UINT16 usAge 
= 0 ,\
              
const string &refStrName = "" ,\
              
const string &refStrAddress = "")\
              : 
              sexType(enumSexType),\
              usAge(usAge) ,\
              strName(refStrName),\
              strAddress(refStrAddress)
    {
        
//DO NOTHING HERE
    }; 
}MAN;



//////////////////////////////////////////////////////////////////////////

typedef list
<MAN> Family;
typedef list
<MAN>::iterator FamilyIterator;

/*
 *    main函数 定义
 
*/
int main()
{
    
/* 初始化 */
    MAN stFather(SEXY_TYPE_MAN,   
28"倒霉熊老爸""华为技术有限公司");
    MAN stMother(SEXY_TYPE_WOMAN, 
27"虾米老妈""郑州大学第二附属医院");
    MAN stBaby  (SEXY_TYPE_BUTT,  
0,  "小天使",   "未知");
    Family myFamily;

    
/* 依次存放到list中    */
    myFamily.push_back(stFather);
    myFamily.push_back(stMother);
    myFamily.push_back(stBaby);

    
/* 调用list的sort函数进行排序, 默认会使用结构体重载的<号, 进行从小到大排序 */
    myFamily.sort();

    printf(
"按年龄从小到大排序:\n");
    FamilyIterator it 
= myFamily.begin();
    
while(it != myFamily.end())
    {
        printf(
"姓名: %s \n", it->strName.c_str());
        it
++;
    }

    
/* 调用模板函数 greater, 传入MAN结构体, 这样会调用结构体重载的>号, 进行从大到小排序 */
    greater
<MAN> gt;
    myFamily.sort(gt);

    printf(
"\n按年龄从大到小排序:\n");
    it 
= myFamily.begin();
    
while(it != myFamily.end())
    {
        printf(
"姓名: %s \n", it->strName.c_str());
        it
++;
    }

    
return 0;
}


Feedback

# re: C++基础知识: list结构体排序方法(一)[未登录]  回复  更多评论   

2010-03-06 16:23 by luckycat
看完代码,给我的第一感觉:代码存在严重的bug(不知道你自己测试过没有).
简单的说就是"不要对非POD类型进行memset操作".
在C++中不要对class进行memset操作;尽量不要对struct进行memset操作.

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 16:37 by luckycat
@小苏
sorry,没有注意到最后一句话"注意: 以上代码在VC6环境下编译、测试通过".
我所指出的bug依然存在,不同的编译器对"memset 非POD处理方式可能不一样".
即使VC6测试通过,你可以换个编译器试试.

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 18:23 by 陈梓瀚(vczh)
@luckycat
没有通过VC9或者GCC或者C++Builder编译过的C++代码,即使测试通过了,也是不能相信的。

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 18:24 by 小苏
@luckycat
你讲的非常又道理,这个代码拿到Cygwin和SuseLinux下面跑都是会出现段错误的。

我又重新修改了一下,你在审阅下,看看还有什么问题?
因为我的焦点在List排序方法上,所以没有考虑内存越界问题...hoho

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 18:54 by 小苏
@luckycat

恩,说的没错。

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 19:01 by 空明流转
@luckycat
有关于POD的问题:
如果所有成员均为POD,且不带虚函数的struct,class,由于采用的是C兼容的内存布局,仍然可以看成是POD的。

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 19:52 by 陈梓瀚(vczh)
@小苏
乱来嘛。luckycat跟你说非POD不要用memset,也就是说你原本类用的是string就写个构造函数嘛。现在倒好,回归原始……而且还先赋值给string再memcpy,干嘛不直接strcpy了事。

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 20:29 by luckycat
呵呵,我就喜欢大家这种踊跃讨论的氛围,互相学习:)

上面的代码你在VC6下面测试通过了,因为从我的第一感觉来看,必定:coredump.
当时我还真不太相信,所以我自己也测试了一下,结果如下:
Win32: VC2005 debug/release下均可运行正常,不过因为memset非POD,出现内存泄漏.
Win32: MinGW Studio 直接abort.(这是我预期的结果).

Linux: Slackware32/GCC 直接abort.(这也是我预期的结果).

为了证明上在win32/VC2005下上面的代码出现内存泄漏,大家可以用下面的代码做测试:
(这里把小苏同学的代码取了一部分用于配合测试)

运行下面的代码,大家在任务管理器中观察内存增长情况:)


#include "Windows.h"

#include <string>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef unsigned int UINT32;
typedef unsigned short UINT16;

typedef struct structMan
{
UINT32 sexType; //ENUM_SEXY_TYPE
UINT16 usAge;
string strName;
string strAddress;

bool operator < (const structMan &man) const
{
return usAge < man.usAge;
}

bool operator > (const structMan &man) const
{
return usAge > man.usAge;
}
}MAN;

int main( int argc , char *argv[] )
{

while( true )
{
MAN man;
memset( &man , 0 , sizeof( MAN ) );
man.strAddress = "abcdef";
man.strName = "abc";
Sleep( 10 ); //这里sleep是为了让大家有时间在任务管理器中看到内存增长的过程,不至于一下子耗尽内存.
}


return 0;
}

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 21:01 by luckycat
@小苏
你后续修改的代码,在我看来,即使在多个编译器下都是OK的,但是就代码风格来说,还有改进的地方.
在编码过程中,我很少会对struct进行memset操作,只是偶尔会对sockaddr进行memset操作;更不会对class进行memset操作.

在你上述的代码中,你对MAN进行memset操作,无非也就是想将各个成员的初值清零,如果基于这个出发点,那设计一个构造函数多好:
structMan::structMan( UINT32 enumSexType = SEXY_TYPE_MAN , \
UINT16 uiAge = 0 , \
const std::string &refStrName = "" , \
const std::string &refStrAddress = "" )
:sexType( enumSexType ) , usAge( uiAge ) , \
strName( refStrName ) , strAddress( refStrAddress )
{
// check parameters here。
}

只需要少量的代码就会带来大量的方便,而且你也就再也不用memset.
你也就不需要对struct的各个成员依次赋值了,直接传参构造就可以了,这样代码应该会更优雅一些.

另一方面,对 std::list 进行sort操作从逻辑上是没有问题的,但是设计风格上是有问题的:
因为std::list中的每一个成员是基于链的形式连接在一起的,所以我们不能对其进行随机访问,
如果我们要访问std::list中的第N个成员,那么我们需要从链表头开始向链表尾部依次迭代N次,
在这种情况下,如果一个链表过大,那么这里就有效率问题.

一般情况下,我们只对"类似于数组的可以随机访问"的std容器进行排序.

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 21:25 by 陈梓瀚(vczh)
@luckycat
我在想他用list估计是因为别的语言都叫list,不知道C++叫的是vector……

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 21:29 by 小苏
@luckycat

这段测试代码我跑了二十分钟,内存也没见增长啊~~~
各位大侠都看出来啦,我很少用C++写程序~~~~

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 21:35 by luckycat
@小苏
你运行后仔细观察这个编译后运行的exe在"windows任务管理器"中对应的
"内存使用"数值.
我用VC2005和VC2008都测试过,结果是"内存不停增长".

还用哪位同学运行过我上面的测试代码,出来公布一下测试结果,谢谢!

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 22:10 by 小苏
@luckycat

能否解释一下,为什么内存使用会不停增长呢?

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 22:50 by luckycat
@小苏
在阅读下面的分析之前,希望你对"C++对象的内部布局"有一定的了解.
既然你也发现了内存泄漏的情况,那么你再用下面的测试代码运行一下:



#include "Windows.h"

#include <string>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef unsigned int UINT32;
typedef unsigned short UINT16;

typedef struct structMan
{
UINT32 sexType; //ENUM_SEXY_TYPE
UINT16 usAge;
string strName;
string strAddress;

bool operator < (const structMan &man) const
{
return usAge < man.usAge;
}

bool operator > (const structMan &man) const
{
return usAge > man.usAge;
}
}MAN;

int main( int argc , char *argv[] )
{

while( true )
{
MAN man;
fprintf( stdout , "before memset: char buffer address( heap address ) to store string = %p , size = %lu , capacity = %lu\n" , \
*reinterpret_cast< const int* >( man.strName.c_str() ) , \
man.strName.size() , man.strName.capacity() );
memset( &man , 0 , sizeof( MAN ) );
fprintf( stdout , "after memset: char buffer address( heap address ) to store string = %p , size = %lu , capacity = %lu\n\n\n" , \
*reinterpret_cast< const int* >( man.strName.c_str() ) , \
man.strName.size() , man.strName.capacity() );

man.strAddress = "abcdef";
man.strName = "abc";
Sleep( 1000 ); //这里sleep是为了让大家有时间在任务管理器中看到内存增长的过程,不至于一下子耗尽内存.
}


return 0;
}


我选取我这里的一个循环中的输出,如下:


before memset: char buffer address( heap address ) to store string = 00636200 ,
size = 0 , capacity = 15
after memset: char buffer address( heap address ) to store string = 00000000 ,
size = 0 , capacity = 0

下面把上述代码进行简化便于分析:

while( true )
{
MAN man; //这里会使用man由编译器自动生成缺省构造函数来调用strName的缺省构造函数对strName进行构造.

memset( &man , 0 , sizeof( MAN ) );
上面的memset操作会把 &man 这个地址开始的 sizeof( MAN )字节的内存空间全部清零.
这也就意味着 man 对象内部的每个成员子对象所占据的内存都被清零.
man 对象内部一个 std::string , 而std::string 内部包含一个std::string用于实际存储字符串的指向动态分配的堆内存的指针,
我们假设这个指针的名称为 m_pCharBuffer;
在std::string的析构函数中释放这个动态分配的堆内存的时候需要使用这个m_pCharBuffer,也即是调用 delete[] m_pCharBuffer;
如果我写出下在的代码:
char *m_pCharBuffer = new char[ BUFFER_SIZE ]; 这一个操作即是strName的缺少构造函数的操作,只不过 BUFFER_SIZE = 15 + 1(最后有一个'\0');
m_pCharBuffer = NULL; //这一个操作与上述的 memset 对 man.strName中用于指向动态内存的指针所产生的作用相同:将指针所指向的堆内存地址清零.
delete[] m_pCharBuffer; //此时 m_pCharBuffer 为NULL , 不过在C++中, delete NULL指针是安全的.不过因为 m_pCharBuffer 已经不指向上述new出来的内存
//所以这里进行 delete[] m_pCharBuffer 时已经不能进行资源的释放了,也即是发生了内存泄漏.

man.strName = "abc";
上面的赋值操作中,实际上要调用: std::string::operator=( const char* );
首先,operator=会判断当前的strName的 capacity能否容纳下"abc",由上面的memset之后我们可以看出此时存储 capacity 值的变量因为memset为0,所以
man.strName.capacity() 输出为0,这也就意味着这个"容积"不能容纳下3个字节的"abc".

所以这时 operator= 要扩大内部用于存储字符串的缓冲区,扩充的基本原理如下:(代码进行简化处理)

std::string& operator=( const char *szString )
{
// check parameter

if( m_pCharBuffer != szString ) // 防止 self-assign
{
delete[] m_pCharBuffer;
m_pCharBuffer = new char[ NEW_SIZE ];
memcpy( m_pCharBuffer , szString , strlen( szString ) + 1 );
}

return *this;

}

上面的操作: *reinterpret_cast< const int* >( man.strName.c_str() ) 即是相当于获取这个 m_pCharBuffer 的地址.
这一点你一定要明白.

由上面的代码以及运行输出可以知道,
注意: 在调用 strName = "abc"时,已经进行了memset操作,此时的 m_pCharBuffer 已经因为上面的 memset操作而被清零,即是 m_pCharBuffer = NULL,
因为memset操作不会调用析构函数 ,所以实际上在清零之前它所指向的动态内存块并没有被释放,
在 operator=中,delete[] m_pCharBuffer; 相当于 delete[] NULL;
这就不能释放 m_pCharBuffer 之前在缺省构造时所指向的动态分配的 15 + 1 字节的内存了,所以出现了内存泄漏.

}

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 23:10 by luckycat
@小苏
为了更好的理解我上面的分析,你可以打开VC2005/VC2008(我这里是VC2008)的单步调试,
在调试模式下的"自动窗口"(位于IDE下方).
观察memset 前后"man -> strName -> _Bx -> _Ptr"的值的变化
_Ptr 实际上就是std::string内部用于存储字符串的堆内存缓冲区的地址,也相当于我上面提到的 m_pCharBuffer

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 23:10 by 小苏
@luckycat

我的测试结果是:
before memset: char buffer address( heap address ) to store string = 0000000 ,
size = 0 , capacity = 0
after memset: char buffer address( heap address ) to store string = 00000000 ,
size = 0 , capacity = 0

这里没法贴图,我的QQ是270083015,比这里讨论快一点
我用的VC6 我想这是我的内存没有增长的原因吧。

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-06 23:15 by luckycat
@小苏
VC6我这里没有,我上面的输出是在VC2008下的测试结果,你换用VC2005/2008再试试.
我的建议是学习C++就不要用VC6了,可以用VC2005/2008.
如果你想用一个轻量级的环境学习C++,MinGW Studio,
wxDev-Cpp , CodeBlocks , CodeLite 都是不错的选择.

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-07 10:07 by zuhd
luckcat解释的很中肯,学习了

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-07 13:03 by 凡客诚品官方网站
施法时间开的飞快见说道

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2010-03-07 21:02 by 一个建议
瞄了一眼代码,输出全是printf ,C语言的不良习惯太多了。为什么不用cout呢。

# re: C++基础知识: list结构体排序方法(一)  回复  更多评论   

2013-09-23 22:32 by toman
呵呵,路过,今天面试被问list vector区别,我竟然说vector比较好些,
然后就是胡诌........面试啊面试

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理