c++ lambda表达式详解

lambda表达式是c++11标准新加特性,学过python的一定不会陌生了,或者类似javascript的闭包。cppreference中的定义是:Constructs a closure: an unnamed function object capable of capturing variables in scope. 简单地说就是定义一个临时局部匿名函数。语法为:

[ capture ] ( params ) mutable exception attribute -> ret { body }

其中capture为定义外部变量是否可见(捕获),(这里的外部变量是指与定义这个lambda处于同一个作用域的变量)。

若为空,则表示不捕获所有外部变量,即所有外部变量均不可访问,= 表示所有外部变量均以值的形式捕获,在body中访问外部变量时,访问的是外部变量的一个副本,类似函数的值传递,因此在body中对外部变量的修改均不影响外部变量原来的值。& 表示以引用的形式捕获,后面加上需要捕获的变量名,没有变量名,则表示以引用形式捕获所有变量,类似函数的引用传递,body操作的是外部变量的引用,因此body中修改外部变量的值会影响原来的值。例如:[ ]表示不捕获任何外部变量, [a, b]以值的形式捕获a,b, [=]以值的形式捕获所有外部变量,[&a, b]a以引用的形式捕获,而b以值的形式捕获,[&, a],除了a以值的形似捕获,其他均以引用的形式捕获,[this]以值的形式捕获this指针!

params就是函数的形参,和普通函数类似,不过若没有形参,这个部分可以省略。

mutalbe表示运行body修改通过拷贝捕获的参数,exception声明可能抛出的异常,attribute 修饰符,参考:http://en.cppreference.com/w/cpp/language/attributes ->ret ret表示返回类型,如果能够根据返回语句自动推导,则可以省略,body即函数体。

注意:除了capture和body是必需的,其他均可以省略,即

int main(int argc, char **argv)
{
	[]{}();
	return 0;
}

定义了一个空lambda表达式,并执行(实际上它什么都没有做)。

int main(int argc, char **argv)
{
	int i = 0;
	[]{cout << i << endl;}(); /* 'i' is not captured */ 
	return 0;
}

声明这段代码不能编译通过,因为[ ] 没有捕获任何外部变量,因此i是不可见的,lambda不能访问i。

int main(int argc, char **argv)
{
	int i = 0;
	cout << i << endl;
	[=]()mutable{cout << ++i << endl;}();
	cout << i << endl;
	return 0;
}

上面的代码输出为0, 1, 0,注意mutable是必需的,因为body中修改了捕获的i,由于i是以值传递的,因此并没有修改i原来的值,而是i的一个副本。

int main(int argc, char **argv)
{
	int i = 0;
	cout << i << endl;
	[&](){cout << ++i << endl;}();
	cout << i << endl;
	return 0;
}

上面代码输出0, 1, 1,因为i是以引用传递的,而body中修改了i的值。

lambda表达式有什么用呢? lambda的作用就是创建一个临时匿名函数,想想有STL算法中很多需要传递谓词函数,比如count_if。假如我有一个字符串容器,我需要统计长度大于3的个数,则可以这样:

int main(int argc, char **argv)
{
	vector<string> s = {"1", "12", "123", "1234", "12345", "123456", "1234567"};
	cout << count_if(begin(s), end(s), [](string s){return s.size() > 3;});
	return 0;
}

这样就不必要再声明一个函数了,代码比较简洁。

还有一个问题就是,我可能需要统计字符串长度大于4,或者5,或者6,显然不能通过传递一个形参来实现,因为谓词函数限定只能传递一个形参,这里我们传递的是string,而不能再传递一个表示长度的数。 如果定义全局函数实现,则我们有两种方式:

一是声明一个全局变量,通过和这个全局变量作比较。二是分别声明大于4或者5的函数。显然两个办法都不太好。全局变量污染一直是很危险的,而声明多个函数显然不科学,如果有更多的需求,则需声明gt2, gt3, gt4 ...。 这个用lambda表达式似乎更好,如:

int main(int argc, char **argv)
{
	vector<string> s = {"1", "12", "123", "1234", "12345", "123456", "1234567"};
	string::size_type n = 3;
	cout << count_if(begin(s), end(s), [n](string s){return s.size() > n;});
	return 0;
}

注意这里的n并不是全局变量,所以不存在全局变量污染的问题。当然还有更好的办法,那就是利用函数对象,如:

using namespace std;
class Gt
{
	public:
		typedef string::size_type size_type;
		Gt(size_type i):n(i){};
		Gt():n(0){};
		void setN(const size_type& i) {
			n = i;
		}
		size_type getN() const{return n;}
		bool operator () (const string &s) const {return s.size() > n;}
		operator int() const { return n;}
	private:
		string::size_type n = 0;
};
inline Gt operator + (const Gt &s1, const Gt &s2)
{
	return Gt(s1.getN() + s2.getN());
}
int main(int argc, char **argv)
{
	vector<string> s = {"1", "12", "123", "1234", "12345", "123456", "1234567"};
	cout << count_if(begin(s), end(s), Gt(1)) << endl; /* > 1 */
	cout << count_if(begin(s), end(s), Gt(2)) << endl; /* > 2 */
	cout << count_if(begin(s), end(s), Gt(2) + Gt(3)) << endl; /* > 5 */
	return 0;
}

上面分别统计长度大于1,大于2,大于5的字符串数量(重载+运算符,纯属娱乐!)。

lambda表达式另外一个功能是声明局部函数。我们知道c++中是不允许在函数中嵌套定义函数的,如果要声明一个局部函数,即只能在函数内部调用,则可以用lambda实现,如声明一个min函数,返回a,b中较小值。则

#include <iostream>
using namespace std;
int main(int argc, char **argv)
{
	auto min = [](int a, int b) -> int{
		return a < b ? a : b;
	};
	cout << min(1, 2) << endl;
	cout << min(8, 2) << endl;
	return 0;
}

 

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

c/c++ const 关键字详解

首先讲讲c语言中const关键字的作用,很多书把const修饰的关键字叫做常量,但我认为还是叫做只读变量恰当点,毕竟它和真正的右值常量还是有区别的,除了只读(即只能定义时初始化,其他任何时候不能再修改)这个限制外,和普通变量没有什么区别。

基本使用方法,就是在变量声明的加上const修饰即可。如const int N = 0;即声明了一个只读变量N。这个N是不允许修改的。

关键在于涉及指针时需要弄清楚const修饰的是指针本身还是修饰指针指向的对象,这点很重要!

可以这样简单记忆,如果const在 * 前面则const修饰的是指针指向的对象,即指向的对象是只读的。如果const 在 *后面则修饰的是指针本身,即该指针变量不可指向其他对象,而指向的对象并不受const约束。如

	int x = 5, y = 6;
	const int *p = &x;
	int * const q = &x;
	// q = &y;
	// *p = 6;
	p = &y;
	*q = 7;

p指针不能修改指向对象的值(注意:只能说不能通过p来修改所指向对象的值,不能说指向的内容不能修改,完全可以通过其他方式修改其值,比如q指针),而q指针可以修改指向对象的值,但本身是一个只读变量,即不能再指向其他对象。另外,注意一点的是,const变量必须在声明时初始化,这和java中的final修饰符不同,final可以声明不进行初始化,可以在任何时候进行初始化。

c++的引用类型也基本类似,看 & 位置决定const修饰的内容。另外注意以下代码:

typedef int* Pointer;
int x = 5;
const Pointer p =  &x;

很容易把const Pointer p = &x, 展开为 const int *p = &x,引起错误! 注意typedef并不是简单的展开,它和宏有本质的区别。上面定义的p应该相对于int * const p = &x; 即p本身是可读变量,而不是其指向的对象不可修改。

const修饰符有什么作用,也许第一反应就是声明一个常量(为什么要声明常量?与宏#define的区别?)。其实更确切地说,const修饰符的功能是为了保护数据安全。

这在函数传参中更容易理解,假如我有一个char *s 字符串, 我要一个查找某个字符的位置的函数find,返回第一次出现该字符的索引,但我不希望由于传入参数后意外的被修改了原来的字符串,关键是这个函数还不一定是我自己写的,有可能是其他人写的。我们可以声明一个函数为 int find(const char *s)来达到这样的目的。 这样我就不用担心我的字符串被恶意修改了。因此:只要是不需要修改原来的内容,则尽量声明为const参数,减少出错率。比如在写qsort的cmp函数时,应该写成int cmp(const void *a, const void *b),因为不希望在比较的时候就把原来的值篡改了。不过一般情况下,const只对指针或者引用参数有效,int foo(const int n)纯属胡闹,因此该函数是传值,每次调用函数时,都会重新创建该函数所有的形参,此时所传递的实参将会初始化对应的形参,普通的非引用类型的参数通过复制对应的实参实现初始化,函数并没有访问调用所传递的实参本身,因此不会修改实参的值,而只是操作实参的一个副本。因此foo函数形参n没有必要const。当然也有时这样使用,比如int op(const int *a, const int n),a表示一个动态数组,n表示数组大小,我不希望在函数体内意外的修改了n的值,因此声明n为const形参是有用的。另外需要注意:如果是在c++中,应该尽量将不需要修改的参数定义为const引用而不应该使用传值的方法!这样能够避免复制实参,减少开销。虽然op(string s1) 和 op(const string &s1)都不会修改s1,但前者需要复制s1,而后者不需要,如果一个类型的复制代价很大时,这效率更明显!

另外需要注意的是const 指针和非const指针、const引用和非const引用是可以重载的,即int foo(const int *x) 和 int foo(int *x)可以重载,int foo(const int &x) 和 foo(int &x)可以重载,所以说重载与否只看参数类型和个数是不确切的,还需要考虑是否const指针或者引用。int foo(const int &x)可以传入右值, 而foo(int &x)不可以传入右值,因为右值是不可修改的。(注意c++11标准中右值引用 && 可以修改右值,因此int foo(int &&x)可以传入右值). 在决定调用哪个版本时,由传入的参数是否const决定!

在c++类中可以声明const成员函数,即 int foo() const {} ,这样声明说明这个函数不能修改对象成员,即this指针是const的,但注意,const成员函数仍然可以修改mutable修饰的数据成员!

总结一下:const的最主要功能是保护数据, 另外使用const引用还能提高函数运行效率,减少复制实参开销!

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

c/c++ sizeof运算符详解以及对象大小

学过c的都知道sizeof运算符。不过还是需要注意以下几点。先从c的sizeof说起:

1. sizeof 是运算符,而不是函数。虽然我们习惯sizeof(...),但( )并不是必需的,它只是表示优先级。我们把sizeof后面的目标叫对象或者操作数。本文约定就叫sizeof对象。

2. 当sizeof 的对象是表达式时,求的大小是表达式返回值的类型大小,但并不计算表达式的值,比如

	char c = 1;
	int i = 2;
	cout << sizeof(c + i) << endl;
	cout << sizeof(c = c + i) << endl;

前者c + i会隐式类型转化为int类型(类型提升),因此返回4(32位系统), 而后者虽然运算时也是转化为int,但赋值给c时又会转化为char,因此返回的是1。同样如果对象是函数,则返回函数返回值类型大小,如:

long long foo()
{
	printf("'%s' has been called.\n", __func__);
	return 0;
}
int main(int argc, char **argv)
{
	
	cout << sizeof(foo()) << endl;
	return 0;
}

执行后输出8, 不会输出 'foo' has been called.说明函数没有真正执行,而只是判断了下返回类型。

3.注意sizeof 对象是指针和数组的区别。

当sizeof的对象是数组时,返回数组总大小,而当对象是指针时,返回指针本身的大小,而不是指示内存空间的大小。因为指针本身就是一个无符号整型数,因此int *p ,sizeof(p)返回的大小是sizeof(void *), 32 位系统返回4,即32位。但注意当数组名作为实参传入函数时,会自动转化为指针类型,如下:

void foo(int a[])
{
	cout << sizeof(a) << endl; /* 4 */
}
int main(int argc, char **argv)
{
	int a[] = {1, 2, 3, 4};
	int *p = a;
	cout << sizeof(a) << endl; /* 16 */
	cout << sizeof(p) << endl; /* 4 */
	foo(a);
	return 0;
}

4. sizeof 无法获取动态分配的内存大小,即使用malloc动态的分配内存,无法使用sizeof获取其大小。

5. 注意c_style字符串末尾有一个\0结束符,也需要占一个char空间,因此sizeof("1") 返回2。而strlen返回的是字符数,不包括\0结束符。

6.关于结构体类型。

理论上一个结构体所占空间是所有成员的大小总和,但由于考虑到对齐问题,会有填充字节。

struct node
{
	int a;
	char c;
};

大小为8字节而不是5字节,填充了3字节。

注意:c语言中空struct大小为0, 而c++中空struct 大小为1, 具体看后面关于空类的讨论。另外,c99中结构体后面的动态数组,即不指定大小的数组,sizeof 时不包括动态数组的大小,即

 

struct node
{
	int a;
	char c;
	int d[];
};

返回依然是8。

下面关于c++类的讨论。除了struct ,以上讨论关于c的sizeof同样适合于c++。首先说说c++ 中的struct类型,注意和c中的struct是不一样的,c中的struct只是一种把各种基本数据类型包装的组合类型,而c++的struct本质上是类,即类有的东西,struct基本都有,即struct也有构造函数、析构函数、成员函数等等,不过它的默认成员是public的,而class定义的类成员默认是private的。另外,struct继承默认也是public,而class定义的类默认是private。另外注意:class可以定义模板参数,但struct不可以!因此,struct本质就是类。

下面主要讨论类的大小:

1. 空类的大小。空类型实例中不包含任何信息,应该大小为0. 但是当我们声明该类型的实例的时候,它必须在内存中占有一定的空间,否则无法使用这些实例。至于占用多少内存,由编译器决定。g++中每个空类型的实例占1字节空间。注意空struct即空类,这就是为什么c++的空struct占一个字节的原因。

2. 构造函数、析构函数、成员函数调用时只需知道函数地址即可,而这些函数的地址之与类型相关,而与具体的实例无关,因此不会在实例中额外添加任何信息。

3. 静态数据成员放在全局数据成员中,它不占类实例大小,多个类实例只有一个实体。可以看作是一种特殊的全局变量。

综上1,2,3:

class A
{
	public:
		static int a;
		static char c;
		A(){};
		~A(){};
		void foo(){};
};

类A的大小为1字节,等于空类大小,因此静态数据成员a,c和成员函数都不占类的大小。

4. 类的非静态数据成员和c语言中的struct类似,也需要对齐,可能需要字节填充。

class A
{
	public:
		int a;
		char c;
		A(){};
		~A(){};
		void foo(){};
};

类A的大小为8字节,a占4B,c占1B,填充3B。

5. 如果一个类中有虚函数,则该类型会生成一个虚函数表,并在该类型的每一个实例中添加一个指向虚函数表的指针,因此类大小必须加上一个指针所占的空间。如果是普通继承,子类和基类共享这个指针。

class A
{
	public:
		int a;
		char c;
		A(){};
		~A(){};
		void foo(){};
		void virtual bar(){};
};

类A的大小为12B。数据成员8B,加上指向虚拟函数表的指针。注意,是在32位系统上。如果是64位机器,一个指针占8B。

6.虚继承时,派生类会生成一个指向虚基类表的指针,占一个指针大小空间。如果还有虚函数,不增加额外指针大小空间,原因不太清楚,如果谁知道,请一定要告诉我!如下:

class A
{
	int a;
};
class B: public virtual A
{
	int b;
	virtual void foo(){};
};

类B的大小为12B,数据成员b占4B,从A中继承a也占4B,另外一个由于virtual存在,额外加一个指针大小4B,共12B。所以:只要有virtual,无论是在成员函数,还是在继承上,都额外加一个指针大小空间。

基本就这些了,如果有纰漏,请指出,谢谢!

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

c99中自我感觉一些有用的新特性

1,支持不定长数组,即使用变量定义数组大小,之前定义数组大小必须是常量类型。比如int  a[5], 但 int a[n]就不行。

2,新的数组初始化方式,即可以指定元素赋予初值,试想如果有一个int数组a,大小为100, 即int a[100], 需要把a[50]赋值为5, a[70]赋值为7,其他为0, 则可以这样 int a[100] = {[50] = 5, [70] = 7}; 这对于初始化稀疏数组非常方便。

3,新的结构体初始化方式,具体看下面的例子。

4. 增加内联函数的支持,不过一般要写到头文件中去,或者声明为static类型。

5. 增加__func__宏,用于打印当前函数名,这对于调试非常有用。

6.结构体可以声明动态数组成员,即不指定数组长度,由使用时视分配内存大小决定数组长度。注意动态数组成员必须在声明最后,且前面必须有其他成员,至多只有一个动态数组,并且使用sizeof或许结构体大小时,将不包括动态数组大小。使用时必须由malloc分配内存,并且应该比原结构体分配内存要大。具体看下面的例子。

例子:

#include <stdio.h>
#include <stdlib.h>
static inline void foo() /* inline函数必须声明为static或者放到头文件中 */
{
	/* 新增__func__宏,打印当前函数名 */
	printf("function '%s' finished.\n", __func__);
}
typedef struct 
{
	int a;
	char c;
	int d[]; /* 增加动态数组支持,必须放到最后,且前面必须有一个成员 */
}data, *Data;
int main(int argc, char **argv)
{
	int a[] = {[10] = 2, [5] = 5}; /* 数组初始化 */
	int len = sizeof(a) / sizeof(int);
	printf("a: ");
	for (int i = 0; i < len; i++) /* 变量声明不必在语句开头 */
		printf("%d ", a[i]);
	printf("\n");
	int n = 4;
	int b[n]; /* 数组长度可以是变量 */
	printf("sizeof(b) = %u\n", sizeof(b));
	data data1 = {1,'c'}; /* 初始化结构体方法一 */
	printf("data1.c = %c\n", data1.c);
	data data2 = {.c='c'}; /* 初始化结构体方法二 */
	printf("data2.a = %d, data2.c = %c\n", data2.a, data2.c);
	Data data3 = malloc(sizeof(data) + sizeof(int) * 10);
	printf("sizeof(data3) = %u\n", sizeof(*data3));
       /* 内存不包括动态数组d的大小,返回8, 
        * int a占4B , char c占1B, 为了对齐,所以返回8 */
	data3 -> d[0] = 1, data3 -> d[1] = 1;
	printf("data3->d[1] = %d\n", data3->d[1]);
	free(data3);
	foo(1);
	return 0;
}

另外还有其他特性,比如新增数据类型long long , long double, _Bool,复数等。摘自维基百科,如下

在C99中包括的特性有:
增加了对编译器的限制,比如源程序每行要求至少支持到 4095 字节,变量名函数名的要求支持到 63 字节(extern 要求支持到 31)。
增强了预处理功能。例如:
巨集支持取可变参数 #define Macro(...) __VA_ARGS__
使用巨集的时候,允许省略参数,被省略的参数会被扩展成空串。
支持 // 开头的单行注释(这个特性实际上在C89的很多编译器上已经被支持了)
增加了新关键字 restrict, inline, _Complex, _Imaginary, _Bool
支持 long long, long double _Complex, float _Complex 等类型
支持不定长的数组,即数组长度可以在运行时决定,比如利用变量作为数组长度。声明时使用 int a[var] 的形式。不过考虑到效率和实现,不定长数组不能用在全局,或 struct 与 union 里。
变量声明不必放在语句块的开头,for 语句提倡写成 for(int i=0;i<100;++i) 的形式,即i 只在 for 语句块内部有效。
允许采用(type_name){xx,xx,xx} 类似于 C++ 的构造函数的形式构造匿名的结构体。
初始化结构的时候允许对特定的元素赋值,形式为:
struct test{int a[3],b;} foo[] =  { [0].a = {1}, [1].a = 2 };
struct test{int a, b, c, d;} foo =  { .a = 1, .c = 3, 4, .b = 5}  // 3,4 是对 .c,.d 赋值的
格式化字符串中,利用 \u 支持 unicode 的字符。
支持 16 进制的浮点数的描述。
printf scanf 的格式化串增加了对 long long int 类型的支持。
浮点数的内部数据描述支持了新标准,可以使用 #pragma 编译器指令指定。
除了已有的 __line__ __file__ 以外,增加了 __func__ 得到当前的函数名。
允许编译器化简非常数的表达式。
修改了 / % 处理负数时的定义,这样可以给出明确的结果,例如在C89中-22 / 7 = -3, -22 % 7 = -1,也可以-22 / 7= -4, -22 % 7 = 6。 而C99中明确为 -22 / 7 = -3, -22 % 7 = -1,只有一种结果。
取消了函数返回类型默认为 int 的规定。
允许 struct 定义的最后一个数组不指定其长度,写做 [](flexible array member)。
const const int i 将被当作 const int i 处理。
增加和修改了一些标准头文件,比如定义 bool 的 <stdbool.h> ,定义一些标准长度的 int 的 <inttypes.h> ,定义复数的 <complex.h> ,定义宽字符的 <wctype.h> ,类似于泛型的数学函数 <tgmath.h>, 浮点数相关的 <fenv.h>。 在<stdarg.h> 增加了 va_copy 用于复制 ... 的参数。 里增加了 struct tmx ,对 struct tm 做了扩展。
输入输出对宽字符以及长整数等做了相应的支持。
另外多说一句:c99新增的许多特性,c++中并不支持,因此不能说c++可以完全兼容c,就算以前可以,c99不一定。
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

c++11中几个有用的新特性

1、foreach语法

java python 等都有foreach语法用于遍历容器(数组也可以看成是一种容器), java 中只要对象是数组或者实现了Iterable接口就能使用foreach语法。在c++11标准中也增加了这个特性。如下:

	vector<int> v = {1, 2,3,4};
	set<int> s = {1,2,3,1,2,3};
	int a[] = {1,2,3};
	for (auto i : v)
		cout << i;
	cout << endl;
	for (auto i : a)
		cout << i;
	cout << endl;
	for (auto i : s)
		cout << i;
	cout << endl;

2、auto类型推导

在c语言中auto关键字表示声明为自动变量,这个auto关键字可有可无,因为默认就是自动变量。在c++11标准后去掉自动变量显式声明方法。而auto关键字依然使用,但意思不再表示自动变量,而表示类型推导,或者说类型占位符。它会由初始化代码推断真实变量类型,这主要的用处是减少程序员的负担,

	vector<int> v = {1, 2, 3, 4};
	for (std::vector<int>::const_iterator i = v.begin(); i != v.end(); i++)
		cout << *i << endl;
	

而c++11标准可以方便的写成:

        vector<int> v = {1, 2, 3, 4};
	for (auto i = v.begin(); i != v.end(); i++)
		cout << *i << endl;
	

3、空指针类型。

在c中用NULL表示空指针,它表示不指示任何对象。而NULL实际上就是0, 有时为了表明是指针类型,可以这样:

#define NULL ((void *)0)

在c++11标准中增加新的关键字nullptr表示空指针,这个可以避免被隐式转化为整型0.

4、容器初始化。

之前vector<int> v需要初始化1,2,3,4,5,需要逐一push_back,c++11标准可以直接这样:

	vector<int> v = {1, 2, 3, 4, 5};
	for (auto i : v)
		cout << i << endl;

当然其他容器也可以这样。

5、lambda表达式。

学过python的一定不陌生了,具体语法参见:http://en.cppreference.com/w/cpp/language/lambda 。如下一个例子:

	auto p = [&count](set<int> v) {
		for (auto i : v) {
			cout << i << ' ';
			count++;
		}
		cout << endl << "count:" << count << endl;;
	};

	vector<int> v = {1, 2, 3, 4, 5};
	set<int> s = {1,1,1,2,2,2};
	int count = 0;
	p(s);
	count = 0;
	p({1, 1, 2,3,3, 4, 5, 6, 6}); /* 会自动转化为set<int>类型 */
	count = 0;
	p({1, 1,1,1, 1, 1, 1});

6、全局begin()、end()方法。

非成员方法begin() 和 end()方法加入到STL中,提高了代码一致性,并利于GP化。而且可以使用数组。如下:

int a[] = {1, 2, 3, 4, 5};
	set<int> s = {1,1,2,2,3,3};
	for (auto i = begin(a); i != end(a); i++)
		cout << *i << ' ';
	cout << endl;
	for (auto i = begin(s); i != end(s); i++)
		cout << *i << ' ';
	cout << endl;

7、右值引用。先看以下代码:

int bar(int &x)
{
	x++;
	printf("%d\n", x);
	return x;
}
int main(int argc, char **argv)
{
	bar(5);
	return 0;
}

    有什么语法错误呢?对的,上面的bar(5)传入的是一个常数,即试图右值引用,而右值是不允许修改的,所以bar必须声明为int bar(const int &x)才能传入常数字面值。左值是一个有名子的对象,而右值是一个没有名字的临时对象。c++11标准加入右值引用的语法,主要为了实现move语义,实现内存优化管理,减少不必要的深度拷贝开销。

    深度拷贝会发生在当对象是以传值的方式传递。举例而言,std::vector<T> 是内部保存了 C-style 数组的一个包装,如果一个std::vector<T>的临时对象被建构或是从 函数返回,要将其存储只能通过生成新的std::vector<T>并且把该临时对象所有的数据复制进去。该临时对象和其拥有的内存会被摧毁。在 C++11,一个std::vector的 "move 构造函数" 对某个vector的右值引用可 以单纯地从右值复制其内部 C-style 数组的指针到新的 vector,然后留下空的右值。这个操作不需要数组的复制,而且空的临时对象的析构也不会摧毁内存。传回vector临时对象的函数不需要显式地传回std::vector<T>&&。如果vector没有 move 构造函数,那么复制构造函数将被调用,以const std::vector<T> &的正常形式。 如果它确实有 move 构造函数, 那么就会调用 move 构造函数,这能够免除大幅的内存配置。

 基于安全的理由,具名的参数将永远不被认定为右值,即使它是被如此声明的 ;为了获得右值必须使用 std::move<T>()。
 

右值引用主要使用 && 标记:

int foo(int &&x)
{
	x ++;
	printf("%d\n", x);
	return x;
}
int main(int argc, char **argv)
{
	foo(5);
	return 0;
}

另外还有更多的c++11标准,参见维基百科:C++11

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

奇妙的位运算

位运算包括与运算(and &),或运算(or |), 取反运算(~),左移运算(<<),右移运算(>>)。运算规则不多说,主要看看位运算的应用。

1. 乘除法运算。

利用左移可以实现2次幂乘法运算,比如比如n * 8, 则 n << 3,而n * 9 ,可以写成 n + (n << 3);除法运算同理。

2、加减法运算。

先做无进位加法,即1 + 1 = [1]0, 进位去丢掉,即异或运算。然后加上进位,显然只有1 + 1才会产生进位10, 我们可以写成 (1 & 1 ) << 1即进位可以先做与运算再左移以为得到,根据这样的思路,c代码为:

int add(int a, int b)
{
	if (a == 0)
		return b;
	if (b == 0)
		return a;
	int t = a ^ b;
	int c = (a & b) << 1;
	return add(t, c);
}
int sub(int a, int b)
{
	return add(a, add(~b, 1));
}

3、交换两个数。

我们知道x ^ x == 0, a ^ x ^ x == a;根据这个思路交换两个数为:

void swap(int &a, int &b)
{
	a ^= b; /* 此时a = a ^ b */
	b ^= a; /* b = b ^ a ^ b , 相当于 b = a; */
	a ^= b; /* a = a ^ a ^ b ,此时a = b */
}

4、把一个数的最低位1置0.

即1110变为1100, 1111变为1110,1000变为0000等。常规做法是找到最低位1,即不断用1左移做位与运算看看是否等于1,然后再设置该位为0。更简单的方法是直接与n-1做位与运算,即

n &= n - 1

5、计算一个数1的个数。

根据4,每次把最低位1设为0, 直到等于0.即

int count(int n)
{
	int c = 0;
	while (n) {
		c++;
		n &= (n - 1);
	}
	return c;
}

6、 判断奇偶性。

bool is_odd(int n)
{
	return n & 0x1;
}

7、奇偶校验。

8、若一个数组中除了一个重复奇数次外,其他数字均重复偶数次,求那个重复奇数次数的数。

如1, 1, 2, 2, 3则返回3。思路还是x ^x ^ x ... ^x,当有偶数个x时,结果为0, 奇数次数则为x,因此把数组所有元素异或起来,偶数次的必然抵掉掉,剩下一个奇数次的。

int oddNumber(int *a, int n)
{
	assert(a != NULL);
	assert(n > 0);
	int t = 0, i;
	for (i = 0; i < n; i++)
		t ^= a[i];
	return t;
}

9、获取整型最大值

#define INT_MAX (((unsigned int) -1) >> 1)
#define LONG_MAX (((unsigned long) -1) >> 1)
#define LLONG_MAX (((unsigned long long) -1) >> 1)

10、判断一个数是否2的幂,只要是2的幂,则这个数至多只有一个1。

bool is_pow_2(int n)
{
	return (n & (n - 1)) == 0;
}

11、另外还有设置某位,获取某位等,根据常识,不多解释。

还有更多关于位运算的应用技巧,以后想到或者看到,再补充。

 

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

STL顺序容器详解

STL中定义了三种顺序容器类型,分别是vector, list, deque(双向队列),它们都是线性表,区别在于操作和作用于各种操作的开销上。另外STL还提供了三种容器适配器,分别是stack,queue,priority_queue,它们都是deque的重新封装。下面将分别介绍三种顺序容器,包括它们的性能分析和实现方式。注意本文不是讲解容器的使用方法,具体使用方法可以,可以google或者查看文档。

首先是vector,vector的实现方式是动态数组。显然既然是数组,那所有元素必然是连续存储的。vector主要靠不断维护三个指针(迭代器,vector中的迭代器本质就是指针,参考我的另一篇博客:浅谈cpp中vector中的迭代器来工作的,它们分别是:_M_start, _M_finish, _M_end_of_storage 。_M_start指向第一个元素,_M_finish指向最后一个元素的下一个位置,即哨兵。_M_end_of_storage指向当前已分配地址的最后一个单元。其他两个都容易理解,主要看看_M_end_of_storage,为什么会有这个指针呢?这是因为vector为了减少分配内存的次数,会预先分配比已容纳元素更大的空间。在插入元素时,如果当前不够空间,则会重新分配内存,一般为原来空间的2倍关系分配。注意由于vector必须是连续存储,当重新分配内存时,就会破坏原来的连续性(谁能够保证一定在原来的位置的末端分配呢?),因此重新分配内存时开销是巨大的,首先需要分配足够的内存,然后要把原来的元素逐一拷贝到新分配的内存上,然后还需要释放掉原来已经不需要的内存。如果存储的元素都是基本数据类型还好点,如果是类,则无论是类的拷贝还是调用析构函数释放内存,开销都可能很大。因此为了提高性能,vector总是尽一切可能减少内存分配次数,而同时又要兼顾不能过多分配内存造成空间浪费。注意这三个指针均是动态变化的,会随着容器的变化而自动更新,当调用begin()方法时,其实返回的正是_M_start,而end()方法返回的是_M_finish,当计算capacity时,就需要用到_M_end_of_storage。

    下面讨论vector的性能。首先访问,由于本质是数组,而数组本身是支持随机访问的,因此访问元素开销很小,O(1)的时间完成,比如返回v[n],则只需要返回 *(begin() + n)即可。再看看插入元素,如果在尾部追加元素,如果已分配的内存还足够大,则只需在尾部追加即可,即*_M_finish++ = new_item; 如果_M_finish已移到_M_end_of_storage,则表示已分配内存不足,需要重新分配,这个开销很大,前面已经解释。注意,虽然在尾部追加元素时遇到分配内存时开销巨大,但这种情况往往很少发生,因为大多数情况,内存都是足够的。如果需要在最前面添加元素,则不仅需要考虑内存问题,还需要移动元素,这个开销更大,因此vector不直接提供push_front方法,如果确实需要这样的操作,可以使用insert方法实现。但使用之前,一定要想想,真的有这个必要吗?你考虑了其中的开销吗?如果有100W个元素,需要移动100W次,你考虑过这样的成本吗?有没有其他的容器可供选择呢?删除元素和插入元素类似,只是不用考虑内存问题,当移除最后一个元素时,只需移动_M_finish指针并释放掉删除的元素即可(调用元素的析构函数),而移除中间元素,需要移动元素,O(n)的时间复杂度)。

    因此总结下,vector是连续存储的,适合随机访问,适合在尾部增删操作元素(这种情况,性能甚至优于list,因为list追加元素每次都需要分配一个元素节点的内存,而vector预先分配好了),但不适合在中间进行增删操作。

接下来讨论list,list实现方式是环形双向链表,学过数据结构的一定非常熟悉了,每个节点不仅保存着元素(data),还分别有两个指针(prev,next)分别指向前一个节点和后一个节点,而最后一个节点的next指向第一个节点,第一个节点的prev指向最后一个节点。节点每次都是动态分配的,即每增加一个节点,需要new一个。存储方式显然不是连续的。节点定义如下:

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};

template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data;
};

 

不难看出,节点和我们数据结构上的节点定义类似,只不过_List_node_base没有data,然后_List_node继承并添加了data,这样的目的是为了使移动和迭代器分离。迭代器不再是vector中简单的指针,而是一个相对复杂的struct,不过我们仍然可以看作是指向节点指针的指针。由于本质是一个双向链表,因此只需要一个指针就可以访问所有元素,list中是_M_node,它指向最后一个节点。那第一个节点就是_M_node->_M_next。因此begin()方法返回_M_node->_M_next, end()方法返回_M_node,当_M_node->_M_next == _M_node时,即_M_node指向自己时,说明链表为空。list正是通过不断维护_M_node这个节点指针来进行各种操作的。另外还有两个指针,分别是_M_put_node 和_M_put_get,这两个指针是临时指针,主要用于新建指针或删除指针时使用。原理就是这样,下面讨论性能:

首先是访问节点,访问最后一个节点或者第一个节点不需要移动指针,即最后一个节点返回_M_node -> _M_data即可,而第一个节点,只需要返回_M_node_->_M_next->_M_data,因此开销很小。但要访问中间节点时就必须通过移动节点了,至于向前还是向后移动,取决于节点的位置。因此list访问节点的时间复杂度是O(n),相对于vector来说性能下降,因此list没有实现[ ]运算符重载。而插入和删除指定位置的节点,只需要修改指针,而不需要移动指针,性能比vector大大提高。

总结一下,list本质就是双向环形链表,不支持随机访问,插入删除操作开销小。另外,由于每次加入新节点时都需要分配内存,然后拷贝元素,如果是在尾部操作元素,则性能反而比vector要低。

最后剩下deque了,deque可以大致认为是vector和list的混合体。如果学过操作系统内存管理,那么就很容易理解了。vector类似于分区存储管理方式,list类似链式存储方式,而deque则类似于分页式存储管理方式(当然由于deque是整用整取,因此不存在内部碎片问题)。deque就像是分页式存储,首先需要一个map表(相当于页表),存储各个node的指针,每个node都是一个连续的缓冲区,用于实际保存元素,并且还有一些预留空间。需要查找某一个元素时,首先需要计算这个元素处于哪个node缓冲区,然后计算offset从该缓冲区中定位。逻辑上看起来deque也是连续存储的,但事实是由一段段连续的空间组合起来的。deque上的迭代器主要依靠_M_cur,_M_first,_M_last,_M_node四个指针来操作,_M_cur指向当前元素,_M_first指向缓冲区头,_M_last指向缓冲区尾,_M_node指向map表,为了逻辑上看起来是连续的,deque迭代器实现了各种运算符重载, 比如++ / + / --/ -等,虽然++看起来简单,实际需要一些计算,如果_M_cur所在缓冲区还有元素,则直接移动_M_cur即可,若移到该缓冲区尾部,则需要找到下一个缓冲区,然后指向第一个元素。其他操作类似。而要访问任意一个位置的元素时,需要先计算该元素在哪个缓冲区,然后计算offset偏移量找到该元素。由于已经实现了+ -操作,则只需要简单调用*(begin() + n)即可。这就非常类似vector了。因此deque逻辑上实现了和vetor一样的随机访问,时间复杂度也是O(1),不过相对于vector,由于需要一些计算,效率上有点损失,不过这可以忽略不计。下面看看性能方面。

首先访问,上面已经说了,逻辑上支持随机访问。插入元素到指定位置,所在缓冲区还有预留空间,直接插入,并且该缓冲区需要移动元素,这比vector效率大大提高,因为不需要移动整个列表,而只是所在的缓冲区node。而如果所有缓冲区都满了,需要重新分配一个缓冲区,并把新元素放到新的缓冲区中,不需要额外的拷贝操作,只需修改map即可。如果只需要在头尾新增元素,尾部类似vector,看看还有没有预留空间,首部的话也类似,看看前面有没有预留空间,没有再分配一个缓冲区。因此deque在首部增删操作优于vector。

总结一下,deque可以看作是vector和list的折中方案,逻辑上实现了随机访问,在首尾操作开销很小。因此如果既要随机访问,又要各种插入删除操作,deque是一种不错的选择。

注意所有容器存储的都是原来元素的副本,而不是本身,因此不支持复制和赋值的元素类型不能放入容器中,比如IO类型对象就不能放入容器中,数组也不应该放入数组中,因此数组不支持直接赋值运算,即int a[5];int b[5] = a是非法的如果容器放入的元素类型拷贝和析构开销都比较大,则应该考虑下放入元素的指针或许更好。

只有知道容器的内部实现原理,才能真正明智的选择容器的类型。

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!