分类目录归档:C/C++编程

Linux下C/C++编程相关的技术文章

STL中list的使用

STL中list的使用

STL中list的使用:

STL中的list就是一双向链表,可高效地进行插入删除元素。现总结一下它的操作。

文中所用到两个list对象c1,c2分别有元素c1(10,20,30)  c2(40,50,60)。还有一个list<int>::iterator citer用来指向c1或c2元素。

list对象的声明构造():

A.      list<int>c0;                 //空链表

B.      list<int>c1(3);             //建一个含三个默认值是0的元素的链表

C.      list<int>c2(5,2);            //建一个含五个元素的链表,值都是2

D.      list<int>c4(c2);             //建一个c2的copy链表

E.       list<int>c5(c1.begin(),c1.end());

//c5含c1一个区域的元素[_First, _Last)。

1.       assign()分配值,有两个重载:

c1.assign(++c2.begin(), c2.end()) //c1现在为(50,60)。

c1.assing(7,4)  //c1中现在为7个4,c1(4,4,4,4,4,4,4)。

2.       back()返回最后一元素的引用:

int i=c1.back();  //i=30

const int i=c2.back();  //i=60且不可修改

3.       begin()返回第一个元素的指针(iterator)

citer=c1.begin();    // *citer=10

list<int>::const_iterator cciter=c1.begin(); //*cciter=10且为const。

4.       clear()删除所有元素

c1.clear();   //c1为空  c1.size为0;

5.       empty()判断是否链表为空

bool B=c1.empty(); //若c1为空B=true;否则B=false;

6.       end()返回最后一个元素的下一位置的指针(list为空时end()=begin())

citer=c1.end(); //*(–citer)=30;

同begin()返回一个常指针,不能修改其中元素。

7.       erase()删除一个元素或一个区域的元素(两个重载)

c1.erase(c1.begin()); // c1现为(20,30);

c1.erase(++c1.begin(),c1.end()); // c1现为(10);

8.       front() 返回第一个元素的引用:

int i=c1.front(); //i=10;

const int i=c1.front(); //i=10且不可修改。

9.       insert()在指定位置插入一个或多个元素(三个重载):

c1.insert(++c1.begin(),100);   //c1(10,100,20,30)

c1.insert(c1.begin(),2,200);  //c1(200,200,20,30);

c1.insert(++c1.begin(),c2.begin(),–c2.end());

//c1(10,40,50,20,30);

10.    max_size()返回链表最大可能长度(size_type就是int型):

list<int>::size_type i=c1.max_size();  //i=1073741823

11.    merge()合并两个链表并使之默认升序(也可改):

c2.merge(c1);   //c1现为空;c2现为c2(10,20,30,40,50,60)

c2.merge(c1,greater<int>()); //同上,但c2现为降序

12.    pop_back()删除链表尾的一个元素

c1.pop_back()  //c1(10,20);

13.    pop_front()删除链表头的一元素

c1.pop_front() //c1(20,30)

14.    push_back()增加一元素到链表尾

c1.push_back(100) //c1(10,20,30,100)

15.    push_front()增加一元素到链表头

c1.push_front(100) //c1(100,10,20,30)

16.    rbegin()返回链表最后一元素的后向指针(reverse_iterator or const)

list<int>::reverse_iterator riter=c1.rbegin(); //*riter=30

17.    rend()返回链表第一元素的下一位置的后向指针

list<int>::reverse_iterator riter=c1.rend(); // *(–riter)=10

18.    remove()删除链表中匹配值的元素(匹配元素全部删除)

c1.remove(10);     //c1(20,30)

19.    remove_if()删除条件满足的元素(会遍历一遍链表)

c1.remove_if( is_odd<int> () ); //c1(10,20,30)

//is_odd自己写(表奇数)

20.    resize()重新定义链表长度(两重载):

c1.resize(4)  //c1(10,20,30,0)用默认值填补

c1.resize(4,100) //c1(10,20,30,100)用指定值填补

21.    reverse()反转链表:

c1.reverse(); //c1(30,20,10)

22.    size()返回链表中元素个数

list<int>::size_type i=c1.size();  //i=3

23.    sort()对链表排序,默认升序(可自定义)

c1.sort();  //c1(10,20,30)

c1.sort(great<int>()); //c1(30,20,10)

24.    splice()对两个链表进行结合(三个重载)

c1.splice(++c1.begin(),c2);

//c1(10,40,50,60,20,30) c2为空 全合并

c1.splice(++c1.begin(),c2,++c2.begin());

//c1(10,50,20,30) ; c2(40,60) 指定元素合并

c1.splice(++c1.begin(),c2,++c2.begin(),c2.end());

//c1(10,50,60,20,30); c2(40) 指定范围合并

25.    swap()交换两个链表(两个重载)

c1.swap(c2);  //c1(40,50,60);

swap(c1,c2);  //c1(40,50,60)

26.    unique()删除相邻重复元素(断言已经排序,因为它不会删除不相邻的相同元素)

c1.unique();

//假设c1开始(-10,10,10,20,20,-10)则之后为c1(-10,10,20,-10)

c1.unique(mypred); //自定义谓词

indent 命令

indent 命令

功能说明:调整C原始代码文件的格式。 

语  法:indent [参数][源文件] 或 indent [参数][源文件][-o 目标文件]
补充说明:indent可辨识C的原始代码文件,并加以格式化,以方便程序设计师阅读。
参  数:
-bad或--blank-lines-after-declarations   在声明区段或加上空白行。 
-bap或--blank-lines-after-procedures  在程序或加上空白行。 
-bbb或--blank-lines-after-block-comments  在注释区段后加上空白行。 
-bc或--blank-lines-after-commas   在声明区段中,若出现逗号即换行。 
-bl或--braces-after-if-line  if(或是else,for等等)与后面执行区段的""自成一行。 
-bli<缩排格数>或--brace-indent<缩排格数>  设置缩排的格数。 
-br或--braces-on-if-line  if(或是else,for等等)与后面执行跛段的""自成一行。 
-bs或--blank-before-sizeof  在sizeof之后空一格。 
-c<栏数>或--comment-indentation<栏数>  将注释置于程序码右侧指定的栏位。 
-cd<栏数>或--declaration-comment-column<栏数>  将注释置于声明右侧指定的栏位。 
-cdb或--comment-delimiters-on-blank-lines  注释符号自成一行。 
-ce或--cuddle-else  将else置于"}"(if执行区段的结尾)之后。 
-ci<缩排格数>或--continuation-indentation<缩排格数>  叙述过长而换行时,指定换行后缩排的格数。 
-cli<缩排格数>或--case-indentation-<缩排格数>  使用case时,switch缩排的格数。 
-cp<栏数>或-else-endif-column<栏数>  将注释置于else与elseif叙述右侧定的栏位。 
-cs或--space-after-cast  在cast之后空一格。 
-d<缩排格数>或-line-comments-indentation<缩排格数>  针对不是放在程序码右侧的注释,设置其缩排格数。 
-di<栏数>或--declaration-indentation<栏数>  将声明区段的变量置于指定的栏位。 
-fc1或--format-first-column-comments  针对放在每行最前端的注释,设置其格式。 
-fca或--format-all-comments  设置所有注释的格式。 
-gnu或--gnu-style  指定使用GNU的格式,此为预设值。 
-i<格数>或--indent-level<格数>  设置缩排的格数。 
-ip<格数>或--parameter-indentation<格数>  设置参数的缩排格数。 
-kr或--k-and-r-style  指定使用Kernighan&Ritchie的格式。 
-lp或--continue-at-parentheses  叙述过长而换行,且叙述中包含了括弧时,将括弧中的每行起始栏位内容垂直对其排列。 
-nbad或--no-blank-lines-after-declarations  在声明区段后不要加上空白行。 
-nbap或--no-blank-lines-after-procedures  在程序后不要加上空白行。 
-nbbb或--no-blank-lines-after-block-comments  在注释区段后不要加上空白行。 
-nbc或--no-blank-lines-after-commas  在声明区段中,即使出现逗号,仍旧不要换行。 
-ncdb或--no-comment-delimiters-on-blank-lines  注释符号不要自成一行。 
-nce或--dont-cuddle-else  不要将else置于"}"之后。 
-ncs或--no-space-after-casts  不要在cast之后空一格。 
-nfc1或--dont-format-first-column-comments  不要格式化放在每行最前端的注释。 
-nfca或--dont-format-comments  不要格式化任何的注释。 
-nip或--no-parameter-indentation  参数不要缩排。 
-nlp或--dont-line-up-parentheses  叙述过长而换行,且叙述中包含了括弧时,不用将括弧中的每行起始栏位垂直对其排列。 
-npcs或--no-space-after-function-call-names  在调用的函数名称之后,不要加上空格。 
-npro或--ignore-profile  不要读取indent的配置文件.indent.pro。 
-npsl或--dont-break-procedure-type  程序类型与程序名称放在同一行。 
-nsc或--dont-star-comments  注解左侧不要加上星号(*)。 
-nsob或--leave-optional-semicolon  不用处理多余的空白行。 
-nss或--dont-space-special-semicolon   若for或while区段仅有一行时,在分号前不加上空格。 
-nv或--no-verbosity  不显示详细的信息。 
-orig或--original  使用Berkeley的格式。 
-pcs或--space-after-procedure-calls  在调用的函数名称与"{"之间加上空格。 
-psl或--procnames-start-lines  程序类型置于程序名称的前一行。 
-sc或--start-left-side-of-comments  在每行注释左侧加上星号(*)。 
-sob或--swallow-optional-blank-lines  删除多余的空白行。 
-ss或--space-special-semicolon  若for或swile区段今有一行时,在分号前加上空格。 
-st或--standard-output  将结果显示在标准输出设备。 
-T  数据类型名称缩排。 
-ts<格数>或--tab-size<格数>  设置tab的长度。 
-v或--verbose  执行时显示详细的信息。 
-version  显示版本信息。
例  子:
indent -kr -i8 -ts8 -sob -l80 -ss -bs -npsl <file>
indent  -kr -bap -nce -i8 -ts8 -sob -l80 -ss -bs -npsl -bl  -bli0 <file>
使用的indent参数 含义
--blank-lines-after-declarations bad 变量声明后加空行
--blank-lines-after-procedures bap 函数结束后加空行
--blank-lines-before-block-comments bbb 块注释前加空行
--break-before-boolean-operator bbo 较长的行,在逻辑运算符前分行
--blank-lines-after-commas nbc 变量声明中,逗号分隔的变量不分行
--braces-after-if-line bl "if"和"{"分做两行
--brace-indent 0 bli0 "{"不继续缩进
--braces-after-struct-decl-line bls 定义结构,"struct"和"{"分行
--comment-indentationn c33 语句后注释开始于行33
--declaration-comment-columnn cd33 变量声明后注释开始于行33
--comment-delimiters-on-blank-lines ncdb 不将单行注释变为块注释
--cuddle-do-while ncdw "do --- while"的"while"和其前面的"}"另起一行
--cuddle-else nce "else"和其前面的"}"另起一行
--case-indentation 0 cli0 switch中的case语句所进0个空格
--else-endif-columnn cp33 #else, #endif后面的注释开始于行33
--space-after-cast cs 在类型转换后面加空格
--line-comments-indentation n d0 单行注释(不从1列开始的),不向左缩进
--break-function-decl-args nbfda 关闭:函数的参数一个一行
--declaration-indentationn di2 变量声明,变量开始于2行,即不必对齐
--format-first-column-comments nfc1 不格式化起于第一行的注释
--format-all-comments nfca 不开启全部格式化注释的开关
--honour-newlines hnl Prefer to break long lines at the position of newlines in the input.
--indent-leveln i4 设置缩进多少字符,如果为tab的整数倍,用tab来缩进,否则用空格填充。
--parameter-indentationn ip5 旧风格的函数定义中参数说明缩进5个空格
--line-length 75 l75 非注释行最长75
--continue-at-parentheses lp 续行从上一行出现的括号开始
--space-after-procedure-calls pcs 函数和"("之间插入一个空格
--space-after-parentheses nprs 在"("后")"前不插入空格
--procnames-start-lines psl 将函数名和返回类型放在两行定义
--space-after-for saf for后面有空格
--space-after-if sai if后面有空格
--space-after-while saw while后面有空格
--start-left-side-of-comments nsc 不在生成的块注释中加*
--swallow-optional-blank-lines nsob 不去掉可添加的空行
--space-special-semicolon nss 一行的for或while语句,在";"前不加空。
--tab-size ts4 一个tab为4个空格(要能整除"-in")
--use-tabs ut 使用tab来缩进
如上参数可写入用户目录下的文件:”.indent.pro”,作为运行indent的缺省参数。

setsockopt和getsockopt

#include	"netfunc.h"
#include			/* for TCP_xxx defines */

union val {
  int				i_val;
  long				l_val;
  struct linger		linger_val;
  struct timeval	timeval_val;
} val;

static char	*sock_str_flag(union val *, int);
static char	*sock_str_int(union val *, int);
static char	*sock_str_linger(union val *, int);
static char	*sock_str_timeval(union val *, int);

struct sock_opts {
  const char	   *opt_str;
  int		opt_level;
  int		opt_name;
  char   *(*opt_val_str)(union val *, int);
} sock_opts[] = {
	{ "SO_BROADCAST",		SOL_SOCKET,	SO_BROADCAST,	sock_str_flag },
	{ "SO_DEBUG",			SOL_SOCKET,	SO_DEBUG,		sock_str_flag },
	{ "SO_DONTROUTE",		SOL_SOCKET,	SO_DONTROUTE,	sock_str_flag },
	{ "SO_ERROR",			SOL_SOCKET,	SO_ERROR,		sock_str_int },
	{ "SO_KEEPALIVE",		SOL_SOCKET,	SO_KEEPALIVE,	sock_str_flag },
	{ "SO_LINGER",			SOL_SOCKET,	SO_LINGER,		sock_str_linger },
	{ "SO_OOBINLINE",		SOL_SOCKET,	SO_OOBINLINE,	sock_str_flag },
	{ "SO_RCVBUF",			SOL_SOCKET,	SO_RCVBUF,		sock_str_int },
	{ "SO_SNDBUF",			SOL_SOCKET,	SO_SNDBUF,		sock_str_int },
	{ "SO_RCVLOWAT",		SOL_SOCKET,	SO_RCVLOWAT,	sock_str_int },
	{ "SO_SNDLOWAT",		SOL_SOCKET,	SO_SNDLOWAT,	sock_str_int },
	{ "SO_RCVTIMEO",		SOL_SOCKET,	SO_RCVTIMEO,	sock_str_timeval },
	{ "SO_SNDTIMEO",		SOL_SOCKET,	SO_SNDTIMEO,	sock_str_timeval },
	{ "SO_REUSEADDR",		SOL_SOCKET,	SO_REUSEADDR,	sock_str_flag },
#ifdef	SO_REUSEPORT
	{ "SO_REUSEPORT",		SOL_SOCKET,	SO_REUSEPORT,	sock_str_flag },
#else
	{ "SO_REUSEPORT",		0,			0,				NULL },
#endif
	{ "SO_TYPE",			SOL_SOCKET,	SO_TYPE,		sock_str_int },
	//{ "SO_USELOOPBACK",		SOL_SOCKET,	SO_USELOOPBACK,	sock_str_flag },
	{ "IP_TOS",				IPPROTO_IP,	IP_TOS,			sock_str_int },
	{ "IP_TTL",				IPPROTO_IP,	IP_TTL,			sock_str_int },
#ifdef	IPV6_DONTFRAG
	{ "IPV6_DONTFRAG",		IPPROTO_IPV6,IPV6_DONTFRAG,	sock_str_flag },
#else
	{ "IPV6_DONTFRAG",		0,			0,				NULL },
#endif
#ifdef	IPV6_UNICAST_HOPS
	{ "IPV6_UNICAST_HOPS",	IPPROTO_IPV6,IPV6_UNICAST_HOPS,sock_str_int },
#else
	{ "IPV6_UNICAST_HOPS",	0,			0,				NULL },
#endif
#ifdef	IPV6_V6ONLY
	{ "IPV6_V6ONLY",		IPPROTO_IPV6,IPV6_V6ONLY,	sock_str_flag },
#else
	{ "IPV6_V6ONLY",		0,			0,				NULL },
#endif
	{ "TCP_MAXSEG",			IPPROTO_TCP,TCP_MAXSEG,		sock_str_int },
	{ "TCP_NODELAY",		IPPROTO_TCP,TCP_NODELAY,	sock_str_flag },
#ifdef	SCTP_AUTOCLOSE
	{ "SCTP_AUTOCLOSE",		IPPROTO_SCTP,SCTP_AUTOCLOSE,sock_str_int },
#else
	{ "SCTP_AUTOCLOSE",		0,			0,				NULL },
#endif
#ifdef	SCTP_MAXBURST
	{ "SCTP_MAXBURST",		IPPROTO_SCTP,SCTP_MAXBURST,	sock_str_int },
#else
	{ "SCTP_MAXBURST",		0,			0,				NULL },
#endif
#ifdef	SCTP_MAXSEG
	{ "SCTP_MAXSEG",		IPPROTO_SCTP,SCTP_MAXSEG,	sock_str_int },
#else
	{ "SCTP_MAXSEG",		0,			0,				NULL },
#endif
#ifdef	SCTP_NODELAY
	{ "SCTP_NODELAY",		IPPROTO_SCTP,SCTP_NODELAY,	sock_str_flag },
#else
	{ "SCTP_NODELAY",		0,			0,				NULL },
#endif
	{ NULL,					0,			0,				NULL }
};


int
main(int argc, char **argv)
{
	int			fd;
	socklen_t		len;
	struct sock_opts	*ptr;

	for (ptr = sock_opts; ptr->opt_str != NULL; ptr++)
	{
		printf("%s: ", ptr->opt_str);
		if (ptr->opt_val_str == NULL)
			printf("(undefined)\n");
		else
		{
			switch(ptr->opt_level)
			{
				case SOL_SOCKET:
				case IPPROTO_IP:
				case IPPROTO_TCP:
					fd = Socket(AF_INET, SOCK_STREAM, 0);
					break;
#ifdef	IPPROTO_SCTP
				case IPPROTO_SCTP:
					fd = Socket(AF_INET, SOCK_SEQPACKET, IPPROTO_SCTP);
					break;
#endif
				default:
					printf("Can't create fd for level %d\n", ptr->opt_level);
					exit(1);
			}

			len = sizeof(val);
			if (getsockopt(fd, ptr->opt_level, ptr->opt_name,&val, &len) == -1){
				printf("getsockopt error\n");
			}else{
				printf("default = %s\n", (*ptr->opt_val_str)(&val, len));
			}
			close(fd);
		}
	}
	exit(0);
}


static char	strres[128];

static char	*
sock_str_flag(union val *ptr, int len)
{
	if (len != sizeof(int))
		snprintf(strres, sizeof(strres), "size (%d) not sizeof(int)", len);
	else
		snprintf(strres, sizeof(strres),
				 "%s", (ptr->i_val == 0) ? "off" : "on");
	return(strres);
}

static char	*
sock_str_int(union val *ptr, int len)
{
	if (len != sizeof(int))
		snprintf(strres, sizeof(strres), "size (%d) not sizeof(int)", len);
	else
		snprintf(strres, sizeof(strres), "%d", ptr->i_val);
	return(strres);
}

static char	*
sock_str_linger(union val *ptr, int len)
{
	struct linger	*lptr = &ptr->linger_val;

	if (len != sizeof(struct linger))
		snprintf(strres, sizeof(strres),
				 "size (%d) not sizeof(struct linger)", len);
	else
		snprintf(strres, sizeof(strres), "l_onoff = %d, l_linger = %d",
				 lptr->l_onoff, lptr->l_linger);
	return(strres);
}

static char	*
sock_str_timeval(union val *ptr, int len)
{
	struct timeval	*tvptr = &ptr->timeval_val;

	if (len != sizeof(struct timeval))
		snprintf(strres, sizeof(strres),
				 "size (%d) not sizeof(struct timeval)", len);
	else
		snprintf(strres, sizeof(strres), "%d sec, %d usec",
				 tvptr->tv_sec, tvptr->tv_usec);
	return(strres);
}

判断linux服务器的网络字节序

将低位字节存储在起始地址,称为小端(little-endian)字节序;将高位字节存储在起始地址,称为大端(big-endian)字节序
网络字节序是大端(big-endian)字节序

#include 
int main(int argc,char* argv[])
{
        union{
                short s;
                char c[sizeof(short)];
        }un;

        un.s    = 0x0102;

        if(sizeof(short)==2)
        {
                if(un.c[0]==1 && un.c[1]==2)
                        printf("big-endian\n");
                else if(un.c[0]==2 && un.c[1]==1)
                        printf("little-endian\n");
                else
                        printf("unknown\n");
        }
        else
                printf("sizeof(short) = %d\n",sizeof(short));

        return 0;
}

详细解说 STL 排序(Sort)

http://www.cppblog.com/mzty/archive/2009/11/17/1770.html

作者Winter

一切复杂的排序操作,都可以通过STL方便实现 !

0 前言: STL,为什么你必须掌握


对 于程序员来说,数据结构是必修的一门课。从查找到排序,从链表到二叉树,几乎所有的算法和原理都需要理解,理解不了也要死记硬背下来。幸运的是这些理论都 已经比较成熟,算法也基本固定下来,不需要你再去花费心思去考虑其算法原理,也不用再去验证其准确性。不过,等你开始应用计算机语言来工作的时候,你会发 现,面对不同的需求你需要一次又一次去用代码重复实现这些已经成熟的算法,而且会一次又一次陷入一些由于自己疏忽而产生的bug中。这时,你想找一种工 具,已经帮你实现这些功能,你想怎么用就怎么用,同时不影响性能。你需要的就是STL, 标准模板库!

西方有句谚语:不要重复发明轮子!

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除……可以说,如果你理解了STL,你会发现你已不用拘泥于算法本身,从而站在巨人的肩膀上去考虑更高级的应用。

排序是最广泛的算法之一,本文详细介绍了STL中不同排序算法的用法和区别。

1 STL提供的Sort 算法


C++之所以得到这么多人的喜欢,是因为它既具有面向对象的概念,又保持了C语言高效的特点。STL 排序算法同样需要保持高效。因此,对于不同的需求,STL提供的不同的函数,不同的函数,实现的算法又不尽相同。

1.1 所有sort算法介绍

所 有的sort算法的参数都需要输入一个范围,[begin, end)。这里使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator), 也就是说可以随机访问的迭代器,如:it+n什么的。(partition 和stable_partition 除外)

如果你需要自己定义比较函数,你可以把你定义好的仿函数(functor)作为参数传入。每种算法都支持传入比较函数。以下是所有STL sort算法函数的名字列表:

函数名 功能描述
sort 对给定区间所有元素进行排序
stable_sort 对给定区间所有元素进行稳定排序
partial_sort 对给定区间所有元素部分排序
partial_sort_copy 对给定区间复制并排序
nth_element 找出给定区间的某个位置对应的元素
is_sorted 判断一个区间是否已经排好序
partition 使得符合某个条件的元素放在前面
stable_partition 相对稳定的使得符合某个条件的元素放在前面

其中nth_element 是最不易理解的,实际上,这个函数是用来找出第几个。例如:找出包含7个元素的数组中排在中间那个数的值,此时,我可能不关心前面,也不关心后面,我只关心排在第四位的元素值是多少。

1.2 sort 中的比较函数

当你需要按照某种特定方式进行排序时,你需要给sort指定比较函数,否则程序会自动提供给你一个比较函数。

vector < int > vect;
//...
sort(vect.begin(), vect.end());
//此时相当于调用
sort(vect.begin(), vect.end(), less<int>() );

上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数,以下是仿函数列表:

名称 功能描述
equal_to 相等
not_equal_to 不相等
less 小于
greater 大于
less_equal 小于等于
greater_equal 大于等于

需要注意的是,这些函数不是都能适用于你的sort算法,如何选择,决定于你的应用。另外,不能直接写入仿函数的名字,而是要写其重载的()函数:

less<int>()
greater<int>()

当你的容器中元素时一些标准类型(int float char)或者string时,你可以直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序,你可以有两种方法来达到效果:一种是自己写比较函数。另一种是重载类型的'<‘操作赋。

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

class myclass {
        public:
        myclass(int a, int b):first(a), second(b){}
        int first;
        int second;
        bool operator < (const myclass &m)const {
                return first < m.first;
        }
};

bool less_second(const myclass & m1, const myclass & m2) {
        return m1.second < m2.second;
}

int main() {

        vector< myclass > vect;
        for(int i = 0 ; i < 10 ; i ++){
                myclass my(10-i, i*3);
                vect.push_back(my);
        }
        for(int i = 0 ; i < vect.size(); i ++) 
        cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
        sort(vect.begin(), vect.end());
        cout<<"after sorted by first:"<<endl;
        for(int i = 0 ; i < vect.size(); i ++) 
        cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
        cout<<"after sorted by second:"<<endl;
        sort(vect.begin(), vect.end(), less_second);
        for(int i = 0 ; i < vect.size(); i ++) 
        cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";

        return 0 ;
}

知道其输出结果是什么了吧:

(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
after sorted by first:
(1,27)
(2,24)
(3,21)
(4,18)
(5,15)
(6,12)
(7,9)
(8,6)
(9,3)
(10,0)
after sorted by second:
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)

1.3 sort 的稳定性

你 发现有sort和stable_sort,还有 partition 和stable_partition, 感到奇怪吧。其中的区别是,带有stable的函数可保证相等元素的原本相对次序在排序后保持不变。或许你会问,既然相等,你还管他相对位置呢,也分不清 楚谁是谁了?这里需要弄清楚一个问题,这里的相等,是指你提供的函数表示两个元素相等,并不一定是一摸一样的元素。

例如,如果你写一个比较函数:

bool less_len(const string &str1, const string &str2)
{
        return str1.length() < str2.length();
}

此 时,”apple” 和 “winter” 就是相等的,如果在”apple” 出现在”winter”前面,用带stable的函数排序后,他们的次序一定不变,如果你使用的是不带”stable”的函数排序,那么排序完 后,”Winter”有可能在”apple”的前面。

1.4 全排序

全排序即把所给定范围所有的元素按照大小关系顺序排列。用于全排序的函数有

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);

template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, 
StrictWeakOrdering comp);

在 第1,3种形式中,sort 和 stable_sort都没有指定比较函数,系统会默认使用operator< 对区间[first,last)内的所有元素进行排序, 因此,如果你使用的类型义军已经重载了operator<函数,那么你可以省心了。第2, 4种形式,你可以随意指定比较函数,应用更为灵活一些。来看看实际应用:

班上有10个学生,我想知道他们的成绩排名。

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
using namespace std;

class student{
        public:
        student(const string &a, int b):name(a), score(b){}
        string name;
        int score;
        bool operator < (const student &m)const {
                return score< m.score;
        }
};

int main() {
        vector< student> vect;
        student st1("Tom", 74);
        vect.push_back(st1);
        st1.name="Jimy";
        st1.score=56;
        vect.push_back(st1);
        st1.name="Mary";
        st1.score=92;
        vect.push_back(st1);
        st1.name="Jessy";
        st1.score=85;
        vect.push_back(st1);
        st1.name="Jone";
        st1.score=56;
        vect.push_back(st1);
        st1.name="Bush";
        st1.score=52;
        vect.push_back(st1);
        st1.name="Winter";
        st1.score=77;
        vect.push_back(st1);
        st1.name="Andyer";
        st1.score=63;
        vect.push_back(st1);
        st1.name="Lily";
        st1.score=76;
        vect.push_back(st1);
        st1.name="Maryia";
        st1.score=89;
        vect.push_back(st1);
        cout<<"------before sort..."<<endl;
        for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
        stable_sort(vect.begin(), vect.end(),less<student>());
        cout <<"-----after sort ...."<<endl;
        for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
        return 0 ;
}

其输出是:

------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Bush:   52
Jimy:   56
Jone:   56
Andyer: 63
Tom:    74
Lily:   76
Winter: 77
Jessy:  85
Maryia: 89
Mary:   92

sort采用的是成熟的”快速排序算法”(目前大部分STL版本已经不是采用简单的快速排序,而是结合内插排序算法)。注1, 可以保证很好的平均性能、复杂度为n*log(n),由于单纯的快速排序在理论上有最差的情况,性能很低,其算法复杂度为n*n,但目前大部分的STL版 本都已经在这方面做了优化,因此你可以放心使用。stable_sort采用的是”归并排序”,分派足够内存是,其算法复杂度为n*log(n), 否则其复杂度为n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。

1.5 局部排序

局部排序其实是为了减少不必要的操作而提供的排序方式。其函数原型为:

template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, 
RandomAccessIterator middle,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, 
StrictWeakOrdering comp);

template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator, 
class StrictWeakOrdering>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);

理 解了sort 和stable_sort后,再来理解partial_sort 就比较容易了。先看看其用途: 班上有10个学生,我想知道分数最低的5名是哪些人。如果没有partial_sort,你就需要用sort把所有人排好序,然后再取前5个。现在你只需 要对分数最低5名排序,把上面的程序做如下修改:

stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());

输出结果为:

------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Bush:   52
Jimy:   56
Jone:   56
Andyer: 63
Tom:    74
Mary:   92
Jessy:  85
Winter: 77
Lily:   76
Maryia: 89

这样的好处知道了吗?当数据量小的时候可能看不出优势,如果是100万学生,我想找分数最少的5个人……

partial_sort采用的堆排序(heapsort),它在任何情况下的复杂度都是n*log(n). 如果你希望用partial_sort来实现全排序,你只要让middle=last就可以了。

partial_sort_copy 其实是copy和partial_sort的组合。被排序(被复制)的数量是[first, last)和[result_first, result_last)中区间较小的那个。如果[result_first, result_last)区间大于[first, last)区间,那么partial_sort相当于copy和sort的组合。

1.6 nth_element 指定元素排序

nth_element一个容易看懂但解释比较麻烦的排序。用例子说会更方便:
班上有10个学生,我想知道分数排在倒数第4名的学生。
如果要满足上述需求,可以用sort排好序,然后取第4位(因为是由小到大排), 更聪明的朋友会用partial_sort, 只排前4位,然后得到第4位。其实这是你还是浪费,因为前两位你根本没有必要排序,此时,你就需要nth_element:

template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, StrictWeakOrdering comp);

对于上述实例需求,你只需要按下面要求修改1.4中的程序:

stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

运行结果为:

------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Jone:   56
Bush:   52
Jimy:   56
Andyer: 63
Jessy:  85
Mary:   92
Winter: 77
Tom:    74
Lily:   76
Maryia: 89

第四个是谁?Andyer,这个倒霉的家伙。为什么是begin()+3而不是+4? 我开始写这篇文章的时候也没有在意,后来在ilovevc 的提醒下,发现了这个问题。begin()是第一个,begin()+1是第二个,… begin()+3当然就是第四个了。

1.7 partition 和stable_partition

好像这两个函数并不是用来排序的,’分类’算法,会更加贴切一些。partition就是把一个区间中的元素按照某个条件分成两类。其函数原型为:

template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first,
ForwardIterator last, Predicate pred)
template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, 
Predicate pred);

看看应用吧:班上10个学生,计算所有没有及格(低于60分)的学生。你只需要按照下面格式替换1.4中的程序:

stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

其输出结果为:

------before sort...
Tom:    74
Jimy:   56
Mary:   92
Jessy:  85
Jone:   56
Bush:   52
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89
-----after sort ....
Jimy:   56
Jone:   56
Bush:   52
Tom:    74
Mary:   92
Jessy:  85
Winter: 77
Andyer: 63
Lily:   76
Maryia: 89

看见了吗,Jimy,Jone, Bush(难怪说美国总统比较笨 smile )都没有及格。而且使用的是stable_partition, 元素之间的相对次序是没有变.

2 Sort 和容器


STL中标准容器主要vector, list, deque, string, set, multiset, map, multimay, 其中set, multiset, map, multimap都是以树结构的方式存储其元素详细内容请参看:学习STL map, STL set之数据结构基础. 因此在这些容器中,元素一直是有序的。

这些容器的迭代器类型并不是随机型迭代器,因此,上述的那些排序函数,对于这些容器是不可用的。上述sort函数对于下列容器是可用的:

  • vector
  • string
  • deque

如果你自己定义的容器也支持随机型迭代器,那么使用排序算法是没有任何问题的。

对 于list容器,list自带一个sort成员函数list::sort(). 它和算法函数中的sort差不多,但是list::sort是基于指针的方式排序,也就是说,所有的数据移动和比较都是此用指针的方式实现,因此排序后的 迭代器一直保持有效(vector中sort后的迭代器会失效).

3 选择合适的排序函数


为什么要选择合适的排序函数?可能你并不关心效率(这里的效率指的是程序运行时间), 或者说你的数据量很小, 因此你觉得随便用哪个函数都无关紧要。

其实不然,即使你不关心效率,如果你选择合适的排序函数,你会让你的代码更容易让人明白,你会让你的代码更有扩充性,逐渐养成一个良好的习惯,很重要吧 smile

如果你以前有用过C语言中的qsort, 想知道qsort和他们的比较,那我告诉你,qsort和sort是一样的,因为他们采用的都是快速排序。从效率上看,以下几种sort算法的是一个排序,效率由高到低(耗时由小变大):

  1. partion
  2. stable_partition
  3. nth_element
  4. partial_sort
  5. sort
  6. stable_sort

记得,以前翻译过Effective STL的文章,其中对如何选择排序函数总结的很好:

  • 若需对vector, string, deque, 或 array容器进行全排序,你可选择sort或stable_sort;
  • 若只需对vector, string, deque, 或 array容器中取得top n的元素,部分排序partial_sort是首选.
  • 若对于vector, string, deque, 或array容器,你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序,nth_element是最理想的;
  • 若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开,你最好使用partition或stable_partition;
  • 若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代 替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果,你必须间接使用。正如上面介绍的有 几种方式可以选择。

总之记住一句话: 如果你想节约时间,不要走弯路, 也不要走多余的路!

4 小结


讨 论技术就像个无底洞,经常容易由一点可以引申另外无数个技术点。因此需要从全局的角度来观察问题,就像观察STL中的sort算法一样。其实在STL还有 make_heap, sort_heap等排序算法。本文章没有提到。本文以实例的方式,解释了STL中排序算法的特性,并总结了在实际情况下应如何选择合适的算法。

5 参考文档

条款31:如何选择排序函数
The Standard Librarian: Sorting in the Standard Library
Effective STL中文版
Standard Template Library Programmer’s Guide vvvv

c++中sort用法 algorithm

http://hi.baidu.com/hxk622/blog/item/eb9301c1be617858b219a862.html

学习网站:http://www.stlchina.org/twiki/bin/view.pl/Main/STLTechArticles

http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms

排序(sort):所有sort算法介绍:使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator)

1.      所有STL sort算法函数的名字列表:

函数名 功能描述
sort 对给定区间所有 元素进行排序
stable_sort 对给定区间所有 元素进行稳定排序
partial_sort 对给定区间所有 元素部分排序
partial_sort_copy 对给定区间复制 并排序
nth_element 找出给定区间的 某个位置对应的元素
is_sorted 判断一个区间是 否已经排好序
partition 使得符合某个条 件的元素放在前面
stable_partition 相对稳定的使得 符合某个条件的元素放在前面

2.      比较函数:当你需要按照某种特定方式进行排序时,你需要给sort指定比较函数,否则程序会自动提供给你一个比较函数。

vector < int > vect;

//…

sort(vect.begin(), vect.end());

//此时相当于调用

sort(vect.begin(), vect.end(), less<int>() );

sort 中的其他比较函 数

equal_to 相等
not_equal_to 不相等
less 小于
greater 大于
less_equal 小于等于
greater_equal 大于等于

上述例子中系统 自己为sort提供了less仿函数。在STL中还提供了其他仿函 数,以下是仿函数列表:

不能直接写入仿 函数的名字,而是要写其重载的()函数: less<int>();

当你的容器中元 素时一些标准类型(int float char)或者string时,你可以直 接使用这些函数模板。但如果你

时自己定义的类 型或者你需要按照其他方式排序,你可以有两种方法来达到效果:一种是自己写比较函数。另一种是重载类型的'<‘操作赋。如:

bool less_second(const myclass & m1, const myclass & m2) {

return m1.second < m2.second;

}

3.      全排序:全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的”快速排序算法”(目前大部分STL版本已经不是采用简单 的快速排序,而是结合内插排序算法)。复杂度为n*log(n).stable_sort采用的是”归并排序”,分派足够内存是,其算法复杂度为n*log(n), 否则 其复杂度为n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。

用于全排序的函 数有:

void sort(RandomAccessIterator first, RandomAccessIterator last);

void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);

void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

4.      局部排序:partial_sort采 用的堆排序(heapsort),它在任 何情况下的复杂度都是n*log(n).

局部排序其实是 为了减少不必要的操作而提供的排序方式。

其函数原型为:

1)      void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);

2)      void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,
RandomAccessIterator last, StrictWeakOrdering comp);

3)      RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,RandomAccessIterator result_last);

4)      RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,RandomAccessIterator result_last, Compare comp);

用法使用情况: 班上有1000个学生,我想知道分数最低的5名是哪些人。

partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());

5.      nth_element 指定元素排序

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last,

StrictWeakOrdering comp);

使用情况:班上 有1000个学生,我想知道分数排在倒数第4名的学生。

nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

6.          partition 和stable_partition :partition就是把一个区间中的元素按照某个条件分成两类,并没有排序。

其函数原型为:

ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)

ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);

用法如:班上10个学生,计算所有没有及格(低于60分)的学生:

student exam(“pass”, 60);

stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

7.      效率由高到低(耗时由小变大):

partion

stable_partition

nth_element

partial_sort

sort

stable_sort

8.      Effective STL对如何选择排序函数总结的很好:

1)      若需对vector, string, deque, 或 array容器进行全排 序,你可选择sort或stable_sort;

若只需对vector, string, deque, 或 array容器中取得top n的元素,部分排序partial_sort是首选.

若对于vector, string, deque, 或array容器,你需要找到第n个位置的元素或者你需要得 到top n且不关系top

2)      n中的内部 顺序,nth_element是最 理想的;

3)      若你需要从 标准序列容器或者array中把满足某个条件 或者不满足某个条件的元素分开,你最好使用partition或stable_partition;

4)      若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代替sort和stable_sort排 序。若你需要得到partial_sort或nth_element的排序效果,你必须间接使用。

list vector sort 排序就这么简单

http://blog.csdn.net/marising/archive/2009/09/18/4567531.aspx

网上江湖郎中和蒙古大夫很多,因此,此类帖子也很多。关于排序,我还真没研究过,看了江湖郎中和蒙古大夫的帖子,搞了半天不行,所以,自己研究了一 下,如下:三种方式都可以,如重写<,()和写比较函数compare_index。但是要注意对象和对象指针的排序区别。

容器中是对象时,用<排序。

容器中是对象指针时,用()和比较函数排序都可以。

list用成员方法sort

vector用sort函数

  1. class TestIndex{
  2. public:
  3. int index;
  4. TestIndex(){
  5. }
  6. TestIndex(int _index):index(_index){
  7. }
  8. bool operator()(const TestIndex* t1,const TestIndex* t2){
  9. printf(“Operator():%d,%d\n”,t1->index,t2->index);
  10. return t1->index < t2->index;
  11. }
  12. bool operator < (const TestIndex& ti) const {
  13. printf(“Operator<:%d\n”,ti.index);
  14. return index < ti.index;
  15. }
  16. };
  17. bool compare_index(const TestIndex* t1,const TestIndex* t2){
  18. printf(“CompareIndex:%d,%d\n”,t1->index,t2->index);
  19. return t1->index < t2->index;
  20. }
  21. int main(int argc, char** argv) {
  22. list<TestIndex*> tiList1;
  23. list<TestIndex> tiList2;
  24. vector<TestIndex*> tiVec1;
  25. vector<TestIndex> tiVec2;
  26. TestIndex* t1 = new TestIndex(2);
  27. TestIndex* t2 = new TestIndex(1);
  28. TestIndex* t3 = new TestIndex(3);
  29. tiList1.push_back(t1);
  30. tiList1.push_back(t2);
  31. tiList1.push_back(t3);
  32. tiList2.push_back(*t1);
  33. tiList2.push_back(*t2);
  34. tiList2.push_back(*t3);
  35. tiVec1.push_back(t1);
  36. tiVec1.push_back(t2);
  37. tiVec1.push_back(t3);
  38. tiVec2.push_back(*t1);
  39. tiVec2.push_back(*t2);
  40. tiVec2.push_back(*t3);
  41. printf(“tiList1.sort()\n”);
  42. tiList1.sort();//无法正确排序
  43. printf(“tiList2.sort()\n”);
  44. tiList2.sort();//用<比较
  45. printf(“tiList1.sort(TestIndex())\n”);
  46. tiList1.sort(TestIndex());//用()比较
  47. printf(“sort(tiVec1.begin(),tiVec1.end())\n”);
  48. sort(tiVec1.begin(),tiVec1.end());//无法正确排序
  49. printf(“sort(tiVec2.begin(),tiVec2.end())\n”);
  50. sort(tiVec2.begin(),tiVec2.end());//用<比较
  51. printf(“sort(tiVec1.begin(),tiVec1.end(),TestIndex())\n”);
  52. sort(tiVec1.begin(),tiVec1.end(),TestIndex());//用()比较
  53. printf(“sort(tiVec1.begin(),tiVec1.end(),compare_index)\n”);
  54. sort(tiVec1.begin(),tiVec1.end(),compare_index);//用compare_index比较
  55. return 0;

STL vector 容器介绍

http://blog.csdn.net/masterlee/archive/2004/11/09/174129.aspx

STL vector 容器介绍

A Presentation of the STL Vector Container (By Nitron)

翻译 masterlee

介绍std::vector,并且讨论它在STL中的算法和条件函数remove_if()。

Download Console Demo – 6.19 Kb

Download MFC Demo – 14.6 Kb

介绍

这篇文章的目的是为了介绍std::vector,如何恰当地使用它们的成员函数等操作。本文中还讨论了条件函数和函数指针在迭代算法中使用,如在remove_if()和for_each()中的使用。通过阅读这篇文章读者应该能够有效地使用vector容器,而且应该不会再去使用C类型的动态数组了。

Vector总览

vector是C++标准模板库中的部分内容,它是一个多功能的,能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器,是因为它能够像容器一样存放各种类型的对象,简单地说,vector是一个能够存放任意类型的动态数组,能够增加和压缩数据。

为了可以使用vector,必须在你的头文件中包含下面的代码:

#include <vector>

vector属于std命名域的,因此需要通过命名限定,如下完成你的代码:

using std::vector;

vector<int> vInts;

或者连在一起,使用全名:

std::vector<int> vInts;

建议使用全局的命名域方式:

using namespace std;

在后面的操作中全局的命名域方式会造成一些问题。vector容器提供了很多接口,在下面的表中列出vector的成员函数和操作。

Vector成员函数

函数 表述
c.assign(beg,end)

c.assign(n,elem)

将[beg; end)区间中的数据赋值给c。

将n个elem的拷贝赋值给c。

c.at(idx) 传回索引idx所指的数据,如果idx越界,抛出out_of_range。
c.back() 传回最后一个数据,不检查这个数据是否存在。
c.begin() 传回迭代器重的可一个数据。
c.capacity() 返回容器中数据个数。
c.clear() 移除容器中所有数据。
c.empty() 判断容器是否为空。
c.end() 指向迭代器中的最后一个数据地址。
c.erase(pos)

c.erase(beg,end)

删除pos位置的数据,传回下一个数据的位置。

删除[beg,end)区间的数据,传回下一个数据的位置。

c.front() 传回地一个数据。
get_allocator 使用构造函数返回一个拷贝。
c.insert(pos,elem)

c.insert(pos,n,elem)

c.insert(pos,beg,end)

在pos位置插入一个elem拷贝,传回新数据位置。

在pos位置插入n个elem数据。无返回值。

在pos位置插入在[beg,end)区间的数据。无返回值。

c.max_size() 返回容器中最大数据的数量。
c.pop_back() 删除最后一个数据。
c.push_back(elem) 在尾部加入一个数据。
c.rbegin() 传回一个逆向队列的第一个数据。
c.rend() 传回一个逆向队列的最后一个数据的下一个位置。
c.resize(num) 重新指定队列的长度。
c.reserve() 保留适当的容量。
c.size() 返回容器中实际数据的个数。
c1.swap(c2)

swap(c1,c2)

将c1和c2元素互换。

同上操作。

vector<Elem> c

vector <Elem> c1(c2)

vector <Elem> c(n)

vector <Elem> c(n, elem)

vector <Elem> c(beg,end)

c.~ vector <Elem>()

创建一个空的vector。

复制一个vector。

创建一个vector,含有n个数据,数据均已缺省构造产生。

创建一个含有n个elem拷贝的vector。

创建一个以[beg;end)区间的vector。

销毁所有数据,释放内存。

Vector操作

函数 描述
operator[] 返回容器中指定位置的一个引用。

创建一个vector

vector容器提供了多种创建方法,下面介绍几种常用的。

创建一个Widget类型的空的vector对象:

vector<Widget> vWidgets;

//     ——

//      |

//      |- Since vector is a container, its member functions

//         operate on iterators and the container itself so

//         it can hold objects of any type.

创建一个包含500个Widget类型数据的vector:

vector<Widget> vWidgets(500);

创建一个包含500个Widget类型数据的vector,并且都初始化为0:

vector<Widget> vWidgets(500, Widget(0));

创建一个Widget的拷贝:

vector<Widget> vWidgetsFromAnother(vWidgets);

向vector添加一个数据

vector添加数据的缺省方法是push_back()。push_back()函数表示将数据添加到vector的尾部,并按需要来分配内存。例如:向vector<Widget>中添加10个数据,需要如下编写代码:

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

vWidgets.push_back(Widget(i));

获取vector中制定位置的数据

很多时候我们不必要知道vector里面有多少数据,vector里面的数据是动态分配的,使用push_back()的一系列分配空间常常决定于文件或一些数据源。如果你想知道vector存放了多少数据,你可以使用empty()。获取vector的大小,可以使用size()。例如,如果你想获取一个vector v的大小,但不知道它是否为空,或者已经包含了数据,如果为空想设置为-1,你可以使用下面的代码实现:

int nSize = v.empty() ? -1 : static_cast<int>(v.size());

访问vector中的数据

使用两种方法来访问vector。

1、   vector::at()

2、   vector::operator[]

operator[]主要是为了与C语言进行兼容。它可以像C语言数组一样操作。但at()是我们的首选,因为at()进行了边界检查,如果访问超过了vector的范围,将抛出一个例外。由于operator[]容易造成一些错误,所有我们很少用它,下面进行验证一下:

分析下面的代码:

vector<int> v;

v.reserve(10);

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

v.push_back(i);

try

{

int iVal1 = v[7];  // not bounds checked – will not throw

int iVal2 = v.at(7); // bounds checked – will throw if out of range

}

catch(const exception& e)

{

cout << e.what();

}

我们使用reserve()分配了10个int型的空间,但并不没有初始化。如下图所示:

你可以在这个代码中尝试不同条件,观察它的结果,但是无论何时使用at(),都是正确的。

删除vector中的数据

vector能够非常容易地添加数据,也能很方便地取出数据,同样vector提供了erase(),pop_back(),clear()来删除数据,当你删除数据的时候,你应该知道要删除尾部的数据,或者是删除所有数据,还是个别的数据。在考虑删除等操作之前让我们静下来考虑一下在STL中的一些应用。

Remove_if()算法

现在我们考虑操作里面的数据。如果要使用remove_if(),我们需要在头文件中包含如下代码::

#include <algorithm>

Remove_if()有三个参数:

1、   iterator _First:指向第一个数据的迭代指针。

2、   iterator _Last:指向最后一个数据的迭代指针。

3、   predicate _Pred:一个可以对迭代操作的条件函数。

条件函数

条件函数是一个按照用户定义的条件返回是或否的结果,是最基本的函数指针,或者是一个函数对象。这个函数对象需要支持所有的函数调用操作,重载operator()()操作。remove_if()是通过unary_function继承下来的,允许传递数据作为条件。

例如,假如你想从一个vector<CString>中删除匹配的数据,如果字串中包含了一个值,从这个值开始,从这个值结束。首先你应该建立一个数据结构来包含这些数据,类似代码如下:

#include <functional>

enum findmodes

{

FM_INVALID = 0,

FM_IS,

FM_STARTSWITH,

FM_ENDSWITH,

FM_CONTAINS

};

typedef struct tagFindStr

{

UINT iMode;

CString szMatchStr;

} FindStr;

typedef FindStr* LPFINDSTR;

然后处理条件判断:

class FindMatchingString

: public std::unary_function<CString, bool>

{

public:

FindMatchingString(const LPFINDSTR lpFS) : m_lpFS(lpFS) {}

bool operator()(CString& szStringToCompare) const

{

bool retVal = false;

switch(m_lpFS->iMode)

{

case FM_IS:

{

retVal = (szStringToCompare == m_lpFDD->szMatchStr);

break;

}

case FM_STARTSWITH:

{

retVal = (szStringToCompare.Left(m_lpFDD->szMatchStr.GetLength())

== m_lpFDD->szWindowTitle);

break;

}

case FM_ENDSWITH:

{

retVal = (szStringToCompare.Right(m_lpFDD->szMatchStr.GetLength())

== m_lpFDD->szMatchStr);

break;

}

case FM_CONTAINS:

{

retVal = (szStringToCompare.Find(m_lpFDD->szMatchStr) != -1);

break;

}

}

return retVal;

}

private:

LPFINDSTR m_lpFS;

};

通过这个操作你可以从vector中有效地删除数据:

// remove all strings containing the value of

// szRemove from vector<CString> vs.

FindStr fs;

fs.iMode = FM_CONTAINS;

fs.szMatchStr = szRemove;

vs.erase(std::remove_if(vs.begin(), vs.end(), FindMatchingString(&fs)), vs.end());

Remove_if()能做什么?

你可能会疑惑,对于上面那个例子在调用remove_if()的时候还要使用erase()呢?这是因为大家并不熟悉STL中的算法。Remove(),remove_if()等所有的移出操作都是建立在一个迭代范围上的,那么不能操作容器中的数据。所以在使用remove_if(),实际上操作的时容器里数据的上面的。思考上面的例子:

1、   szRemove = “o”.

2、   vs见下面图表中的显示。

观察这个结果,我们可以看到remove_if()实际上是根据条件对迭代地址进行了修改,在数据的后面存在一些残余的数据,那些需要删除的数据。剩下的数据的位置可能不是原来的数据,但他们是不知道的。

调用erase()来删除那些残余的数据。注意上面例子中通过erase()删除remove_if()的结果和vs.enc()范围的数据。

压缩一个臃肿的vector

很多时候大量的删除数据,或者通过使用reserve(),结果vector的空间远远大于实际需要的。所有需要压缩vector到它实际的大小。resize()能够增加vector的大小。Clear()仅仅能够改变缓存的大小,所有的这些对于vector释放内存等九非常重要了。如何来解决这些问题呢,让我们来操作一下。

我们可以通过一个vector创建另一个vector。让我们看看这将发生什么。假定我们已经有一个vector v,它的内存大小为1000,当我们调用size()的时候,它的大小仅为7。我们浪费了大量的内存。让我们在它的基础上创建一个vector。

std::vector<CString> vNew(v);

cout << vNew.capacity();

vNew.capacity()返回的是7。这说明新创建的只是根据实际大小来分配的空间。现在我们不想释放v,因为我们要在其它地方用到它,我们可以使用swap()将v和vNew互相交换一下?

vNew.swap(v);

cout << vNew.capacity();

cout << v.capacity();

有趣的是:vNew.capacity()是1000,而v.capacity()是7。

现在是达到我的目的了,但是并不是很好的解决方法,我们可以像下面这么写:

std::vector<CString>(v).swap(v);

你可以看到我们做了什么?我们创建了一个临时变量代替那个命名的,然后使用swap(),这样我们就去掉了不必要的空间,得到实际大小的v。

结论

我希望这个文档可以给那些使用STL vector容器的开发者很有价值的参考。我也希望通过阅读这篇文章你可以放心地使用vector来代替C语言中的数据了。

参考

Plauger, P.J. Standard C++ Library Reference. February, 2003. MSDN.

Schildt, Herbert. C++ from the Ground Up, Second Edition. Berkeley: 1998.

Sutter, Herb. More Exceptional C++. Indianapolis: 2002.

郑重声明:
允许复制、修改、传递或其它行为
但不准用于任何商业用途.
写于  2004/11/9  masterlee

深入研究 STL Deque 容器

STL中map用法详解

http://blog.csdn.net/bat603/archive/2006/12/23/1456141.aspx

Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力,由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道。这里说下map内部数据的组织,map内部自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的,后边我们会见识到有序的好处。

下面举例说明什么是一对一的数据映射。比如一个班级中,每个学生的学号跟他的姓名就存在着一一映射的关系,这个模型用map可能轻易描述,很明显学号用int描述,姓名用字符串描述(本篇文章中不用char *来描述字符串,而是采用STL中string来描述),下面给出map描述代码:

Map<int, string> mapStudent;

1.       map的构造函数

map共提供了6个构造函数,这块涉及到内存分配器这些东西,略过不表,在下面我们将接触到一些map的构造方法,这里要说下的就是,我们通常用如下方法构造一个map:

Map<int, string> mapStudent;

2.       数据的插入

在构造map容器后,我们就可以往里面插入数据了。这里讲三种插入数据的方法:

第一种:用insert函数插入pair数据,下面举例说明(以下代码虽然是随手写的,应该可以在VC和GCC下编译通过,大家可以运行下看什么效果,在VC下请加入这条语句,屏蔽4786警告  #pragma warning (disable:4786) )

#include <map>

#include <string>

#include <iostream>

Using namespace std;

Int main()

{

Map<int, string> mapStudent;

mapStudent.insert(pair<int, string>(1, “student_one”));

mapStudent.insert(pair<int, string>(2, “student_two”));

mapStudent.insert(pair<int, string>(3, “student_three”));

map<int, string>::iterator  iter;

for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)

{

Cout<<iter->first<<”   ”<<iter->second<<end;

}

}

第二种:用insert函数插入value_type数据,下面举例说明

#include <map>

#include <string>

#include <iostream>

Using namespace std;

Int main()

{

Map<int, string> mapStudent;

mapStudent.insert(map<int, string>::value_type (1, “student_one”));

mapStudent.insert(map<int, string>::value_type (2, “student_two”));

mapStudent.insert(map<int, string>::value_type (3, “student_three”));

map<int, string>::iterator  iter;

for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)

{

Cout<<iter->first<<”   ”<<iter->second<<end;

}

}

第三种:用数组方式插入数据,下面举例说明

#include <map>

#include <string>

#include <iostream>

Using namespace std;

Int main()

{

Map<int, string> mapStudent;

mapStudent[1] =  “student_one”;

mapStudent[2] =  “student_two”;

mapStudent[3] =  “student_three”;

map<int, string>::iterator  iter;

for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)

{

Cout<<iter->first<<”   ”<<iter->second<<end;

}

}

以上三种用法,虽然都可以实现数据的插入,但是它们是有区别的,当然了第一种和第二种在效果上是完成一样的,用insert函数插入数据,在数据的插入上涉及到集合的唯一性这个概念,即当map中有这个关键字时,insert操作是插入数据不了的,但是用数组方式就不同了,它可以覆盖以前该关键字对应的值,用程序说明

mapStudent.insert(map<int, string>::value_type (1, “student_one”));

mapStudent.insert(map<int, string>::value_type (1, “student_two”));

上面这两条语句执行后,map中1这个关键字对应的值是“student_one”,第二条语句并没有生效,那么这就涉及到我们怎么知道insert语句是否插入成功的问题了,可以用pair来获得是否插入成功,程序如下

Pair<map<int, string>::iterator, bool> Insert_Pair;

Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, “student_one”));

我们通过pair的第二个变量来知道是否插入成功,它的第一个变量返回的是一个map的迭代器,如果插入成功的话Insert_Pair.second应该是true的,否则为false。

下面给出完成代码,演示插入成功与否问题

#include <map>

#include <string>

#include <iostream>

Using namespace std;

Int main()

{

Map<int, string> mapStudent;

Pair<map<int, string>::iterator, bool> Insert_Pair;

Insert_Pair = mapStudent.insert(pair<int, string>(1, “student_one”));

If(Insert_Pair.second == true)

{

Cout<<”Insert Successfully”<<endl;

}

Else

{

Cout<<”Insert Failure”<<endl;

}

Insert_Pair = mapStudent.insert(pair<int, string>(1, “student_two”));

If(Insert_Pair.second == true)

{

Cout<<”Insert Successfully”<<endl;

}

Else

{

Cout<<”Insert Failure”<<endl;

}

map<int, string>::iterator  iter;

for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)

{

Cout<<iter->first<<”   ”<<iter->second<<end;

}

}

大家可以用如下程序,看下用数组插入在数据覆盖上的效果

#include <map>

#include <string>

#include <iostream>

Using namespace std;

Int main()

{

Map<int, string> mapStudent;

mapStudent[1] =  “student_one”;

mapStudent[1] =  “student_two”;

mapStudent[2] =  “student_three”;

map<int, string>::iterator  iter;

for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)

{

Cout<<iter->first<<”   ”<<iter->second<<end;

}

}

3.       map的大小

在往map里面插入了数据,我们怎么知道当前已经插入了多少数据呢,可以用size函数,用法如下:

Int nSize = mapStudent.size();

4.       数据的遍历

这里也提供三种方法,对map进行遍历

第一种:应用前向迭代器,上面举例程序中到处都是了,略过不表

第二种:应用反相迭代器,下面举例说明,要体会效果,请自个动手运行程序

#include <map>

#include <string>

#include <iostream>

Using namespace std;

Int main()

{

Map<int, string> mapStudent;

mapStudent.insert(pair<int, string>(1, “student_one”));

mapStudent.insert(pair<int, string>(2, “student_two”));

mapStudent.insert(pair<int, string>(3, “student_three”));

map<int, string>::reverse_iterator  iter;

for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)

{

Cout<<iter->first<<”   ”<<iter->second<<end;

}

}

第三种:用数组方式,程序说明如下

#include <map>

#include <string>

#include <iostream>

Using namespace std;

Int main()

{

Map<int, string> mapStudent;

mapStudent.insert(pair<int, string>(1, “student_one”));

mapStudent.insert(pair<int, string>(2, “student_two”));

mapStudent.insert(pair<int, string>(3, “student_three”));

int nSize = mapStudent.size()

//此处有误,应该是 for(int nIndex = 1; nIndex <= nSize; nIndex++)

//by rainfish

for(int nIndex = 0; nIndex < nSize; nIndex++)

{

Cout<<mapStudent[nIndex]<<end;

}

}

5.       数据的查找(包括判定这个关键字是否在map中出现)

在这里我们将体会,map在数据插入时保证有序的好处。

要判定一个数据(关键字)是否在map中出现的方法比较多,这里标题虽然是数据的查找,在这里将穿插着大量的map基本用法。

这里给出三种数据查找方法

第一种:用count函数来判定关键字是否出现,其缺点是无法定位数据出现位置,由于map的特性,一对一的映射关系,就决定了count函数的返回值只有两个,要么是0,要么是1,出现的情况,当然是返回1了

第二种:用find函数来定位数据出现位置,它返回的一个迭代器,当数据出现时,它返回数据所在位置的迭代器,如果map中没有要查找的数据,它返回的迭代器等于end函数返回的迭代器,程序说明

#include <map>

#include <string>

#include <iostream>

Using namespace std;

Int main()

{

Map<int, string> mapStudent;

mapStudent.insert(pair<int, string>(1, “student_one”));

mapStudent.insert(pair<int, string>(2, “student_two”));

mapStudent.insert(pair<int, string>(3, “student_three”));

map<int, string>::iterator iter;

iter = mapStudent.find(1);

if(iter != mapStudent.end())

{

Cout<<”Find, the value is ”<<iter->second<<endl;

}

Else

{

Cout<<”Do not Find”<<endl;

}

}

第三种:这个方法用来判定数据是否出现,是显得笨了点,但是,我打算在这里讲解

Lower_bound函数用法,这个函数用来返回要查找关键字的下界(是一个迭代器)

Upper_bound函数用法,这个函数用来返回要查找关键字的上界(是一个迭代器)

例如:map中已经插入了1,2,3,4的话,如果lower_bound(2)的话,返回的2,而upper-bound(2)的话,返回的就是3

Equal_range函数返回一个pair,pair里面第一个变量是Lower_bound返回的迭代器,pair里面第二个迭代器是Upper_bound返回的迭代器,如果这两个迭代器相等的话,则说明map中不出现这个关键字,程序说明

#include <map>

#include <string>

#include <iostream>

Using namespace std;

Int main()

{

Map<int, string> mapStudent;

mapStudent[1] =  “student_one”;

mapStudent[3] =  “student_three”;

mapStudent[5] =  “student_five”;

map<int, string>::iterator  iter;

iter = mapStudent.lower_bound(2);

{

//返回的是下界3的迭代器

Cout<<iter->second<<endl;

}

iter = mapStudent.lower_bound(3);

{

//返回的是下界3的迭代器

Cout<<iter->second<<endl;

}

iter = mapStudent.upper_bound(2);

{

//返回的是上界3的迭代器

Cout<<iter->second<<endl;

}

iter = mapStudent.upper_bound(3);

{

//返回的是上界5的迭代器

Cout<<iter->second<<endl;

}

Pair<map<int, string>::iterator, map<int, string>::iterator> mapPair;

mapPair = mapStudent.equal_range(2);

if(mapPair.first == mapPair.second)
{

cout<<”Do not Find”<<endl;

}

Else

{

Cout<<”Find”<<endl;
}

mapPair = mapStudent.equal_range(3);

if(mapPair.first == mapPair.second)
{

cout<<”Do not Find”<<endl;

}

Else

{

Cout<<”Find”<<endl;
}

}

6.       数据的清空与判空

清空map中的数据可以用clear()函数,判定map中是否有数据可以用empty()函数,它返回true则说明是空map

7.       数据的删除

这里要用到erase函数,它有三个重载了的函数,下面在例子中详细说明它们的用法

#include <map>

#include <string>

#include <iostream>

Using namespace std;

Int main()

{

Map<int, string> mapStudent;

mapStudent.insert(pair<int, string>(1, “student_one”));

mapStudent.insert(pair<int, string>(2, “student_two”));

mapStudent.insert(pair<int, string>(3, “student_three”));

//如果你要演示输出效果,请选择以下的一种,你看到的效果会比较好

//如果要删除1,用迭代器删除

map<int, string>::iterator iter;

iter = mapStudent.find(1);

mapStudent.erase(iter);

//如果要删除1,用关键字删除

Int n = mapStudent.erase(1);//如果删除了会返回1,否则返回0

//用迭代器,成片的删除

//一下代码把整个map清空

mapStudent.earse(mapStudent.begin(), mapStudent.end());

//成片删除要注意的是,也是STL的特性,删除区间是一个前闭后开的集合

//自个加上遍历代码,打印输出吧

}

8.       其他一些函数用法

这里有swap,key_comp,value_comp,get_allocator等函数,感觉到这些函数在编程用的不是很多,略过不表,有兴趣的话可以自个研究

9.       排序

这里要讲的是一点比较高深的用法了,排序问题,STL中默认是采用小于号来排序的,以上代码在排序上是不存在任何问题的,因为上面的关键字是int型,它本身支持小于号运算,在一些特殊情况,比如关键字是一个结构体,涉及到排序就会出现问题,因为它没有小于号操作,insert等函数在编译的时候过不去,下面给出两个方法解决这个问题

第一种:小于号重载,程序举例

#include <map>

#include <string>

Using namespace std;

Typedef struct tagStudentInfo

{

Int      nID;

String   strName;

}StudentInfo, *PStudentInfo;  //学生信息

Int main()

{

int nSize;

//用学生信息映射分数

map<StudentInfo, int>mapStudent;

map<StudentInfo, int>::iterator iter;

StudentInfo studentInfo;

studentInfo.nID = 1;

studentInfo.strName = “student_one”;

mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));

studentInfo.nID = 2;

studentInfo.strName = “student_two”;

mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));

for (iter=mapStudent.begin(); iter!=mapStudent.end(); iter++)

cout<<iter->first.nID<<endl<<iter->first.strName<<endl<<iter->second<<endl;

}

以上程序是无法编译通过的,只要重载小于号,就OK了,如下:

Typedef struct tagStudentInfo

{

Int      nID;

String   strName;

Bool operator < (tagStudentInfo const& _A) const

{

//这个函数指定排序策略,按nID排序,如果nID相等的话,按strName排序

If(nID < _A.nID)  return true;

If(nID == _A.nID) return strName.compare(_A.strName) < 0;

Return false;

}

}StudentInfo, *PStudentInfo;  //学生信息

第二种:仿函数的应用,这个时候结构体中没有直接的小于号重载,程序说明

#include <map>

#include <string>

Using namespace std;

Typedef struct tagStudentInfo

{

Int      nID;

String   strName;

}StudentInfo, *PStudentInfo;  //学生信息

Classs sort

{

Public:

Bool operator() (StudentInfo const &_A, StudentInfo const &_B) const

{

If(_A.nID < _B.nID) return true;

If(_A.nID == _B.nID) return _A.strName.compare(_B.strName) < 0;

Return false;

}

};

Int main()

{

//用学生信息映射分数

Map<StudentInfo, int, sort>mapStudent;

StudentInfo studentInfo;

studentInfo.nID = 1;

studentInfo.strName = “student_one”;

mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));

studentInfo.nID = 2;

studentInfo.strName = “student_two”;

mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));

}

10.   另外

由于STL是一个统一的整体,map的很多用法都和STL中其它的东西结合在一起,比如在排序上,这里默认用的是小于号,即less<>,如果要从大到小排序呢,这里涉及到的东西很多,在此无法一一加以说明。

还要说明的是,map中由于它内部有序,由红黑树保证,因此很多函数执行的时间复杂度都是log2N的,如果用map函数可以实现的功能,而STL  Algorithm也可以完成该功能,建议用map自带函数,效率高一些。

下面说下,map在空间上的特性,否则,估计你用起来会有时候表现的比较郁闷,由于map的每个数据对应红黑树上的一个节点,这个节点在不保存你的数据时,是占用16个字节的,一个父节点指针,左右孩子指针,还有一个枚举值(标示红黑的,相当于平衡二叉树中的平衡因子),我想大家应该知道,这些地方很费内存了吧,不说了……