Categories
不学无术

C++ Template: Handle mutual (circular) dependencies

Sometimes we have two classes that need to call each other’s somewhat function, for example

template <typename A>
struct B
{
    A* p_a_ = nullptr;
};
template <typename B>
struct A
{
    B* p_b_ = nullptr;
};

but as you can see A depends on B’s type to initialize and vise versa. If we declare the types as above we’ll not get a chance to create any instance.
There are at least two ways to resolve the issue.

I.Template template

A quick introduction about template template can be found here.
Declare either of {A, B} with template of template which accepts the other’s template argument.

template <template<typename> typename A_t>
struct B
{
    using A = A_t<B>;
    A* p_a_ = nullptr;
};
template <typename B>
struct A
{
    B* p_b_ = nullptr;
};
//and declare like this
using B_t = B<A>;
B_t b_instance;
A<B_t> A_instance;

II.Type traits

The other resolution is create a type trait struct which acts like a bridge that links the type of each other.

template <typename foobar_tratis>
struct foobar_notifier
{
	using inst_t = typename foobar_tratis::foobar_inst_t;
	inst_t* inst_ = nullptr;
	void foobar()
	{
		std::cout << "foobar_notifier" << std::endl;
	}
};
template <typename foobar_tratis>
struct foobar_inst
{
	using notifier_t = typename foobar_tratis::foobar_notifier_t;
	notifier_t* notifier_ = nullptr;
	void foobar()
	{
		std::cout << "foobar_inst" << std::endl;
	}
};
struct foobar_tratis
{
	using foobar_notifier_t = foobar_notifier<md_inst_traits>;
	using foobar_inst_t = foobar_inst<md_inst_traits>;
};
/// and declare like this
foobar_inst<foobar_tratis> inst2;
foobar_notifier<foobar_tratis> notifier2;

 

Categories
不学无术

C++堆内存相关问题小结

C++中遇到的堆内存相关问题,基本可以归为下述三类:

  • 野指针
    • 一些内存单元已被释放,之前指向它的指针还在被使用。这会导致无法预测的运行时错误。
  • 重复释放
    • 试图释放已经被释放过的内存单元,或者释放已被重新分配的内存单元。这会导致运行时错误。
  • 内存泄漏
    • 不再需要的内存单元一直驻留没有释放。这会导致内存占用剧增,直至堆内存无法分配,运行时错误。

 
 
摘自《深入理解C++11》

Categories
不学无术

C++11 继承构造函数、委派构造函数

C++11标准中引入了两种构造函数的活用方法,可以适当地减轻一些情景下的码字负担。

1.继承构造函数

以往情况下,在派生类中调用基类的构造函数,一般需要在派生类中显式调用:

struct A
{
    A(int i) {}
};
struct B
{
    B(int i) : A(i) {}
};

当构造函数的花式(签名)很多的时候,继承类写起来就比较辛苦了。
在C++11标准中,可以通过using声明来简化这种操作(using声明在以前的标准中已经可以用在非构造函数里)

struct A
{
    A(int i) {}
    A(double d, int i) {}
    A(float f, double d, int i) {}
    //...
};
struct B
{
    using A::A;    //继承构造函数
    //...
};

需要注意的是,采用这种using声明有两个规矩:

  • 如果基类的构造函数是private或是派生类是从基类中虚继承的,不能用这种方法;
  • 一旦用了继承构造函数,编译器就不会为派生类生成默认构造函数(Visual Studio报error C2280),除非基类自己没有定义任何构造函数而触发了默认构造函数生成;

2.委派构造函数

委派构造函数常用在减少初始化过程的代码冗余问题,比如下面这个经典例子(我就这么干过):

class Info
{
public:
    Info() { InitRest(); }
    Info(int i) : type(i) { InitRest(); }
    Info(char c) : name(c) { InitRest();}
private:
    void InitRest ()
    {
        // 初始化其他东西
    }
    int type {1};
    char name {'a'};
    //...
};

使用一般方法,我们无法在自己构造函数里又调用自己的构造函数(突然想起了python的import this,哈哈),纵使函数签名不同也会报编译错误。
C++11中,可以这么写:

class Info
{
public:
    Info() { InitRest(); }
    Info(int i) : Info() { type = i; }
    Info(char c) : Info() { name = c; }
private:
    void InitRest ()
    {
        // 初始化其他东西
    }
    int type {1};
    char name {'a'};
    //...
};

但是要注意,委派构造函数不能和初始化列表并用,不然依旧编译错误。
比如我们不能搞Info(int i) : Info(), type(i) { } 。
不过有解决办法,比如可以声明一个私有的构造函数,它包括“完整”的参数输入,然后公有的其他构造函数调用它:

class Info
{
public:
    Info() : Info(1, 'a') { } // 或采用链状委派: Info(1) 或 Info('a')
    Info(int i) : Info(i, 'a') { }
    Info(char c) : Info(1, c) { }
private:
    Info(int i, char e) : type(i), name(c) { }
    int type {1};
    char name {'a'};
    //...
};

关于函数执行顺序,目标函数执行总是先于委派构造函数的。

参考文献

《深入理解C++11 (C++11新特性解析与应用)》

Categories
不学无术

C++模板元编程 习题: add_const_ref

要学的东西还有很多啊…
习题2-0. 编写一个一元元函数add_const_ref<T>,如果T是一个引用类型,就返回T,否则返回T const&.

#include "add_const_ref.h"
int main()
{
	int a = 5;
	add_const_ref<int>::type c = a;
	add_const_ref<int&>::type d = a;
	return 0;
}

 

#ifndef ADD_CONST_REF
#define ADD_CONST_REF
template <class T>
struct add_const_ref;
template<class T>
struct add_const_ref
{
	typedef T const& type;
};
template<class T>
struct add_const_ref<T&>
{
	typedef T type;
};
#endif

 

Categories
不学无术

C++11里头的thread初探

C++11标准给了很多“终于等到了”的功能,其中一项就是线程类<thread> ,有朝一日终于可以减少操作系统相关了,隔壁J家笑而不语。
 
用法真是简单多了,最简单的一种如下:

#include <thread>
#include <iostream>
using namespace std;
void pause_thread(int n) {
	this_thread::sleep_for(chrono::seconds(2));
	cout << "thread of " << n << " ended\n";
}
int main() {
	int N = 0;
	cin >> N;
	thread* ths = new thread[N];
	for (int i = 0; i < N; i++) {
		ths[i] = thread(pause_thread, i);
	}
	cout << "Finished spawning threads." << endl;
	for (int i = 0; i < N; i++) {
		ths[i].join();
	}
	cout << "All threads joined!" << endl;
	delete[]ths;
	return 0;
}

上面程序的输出:
cpp11_thread
当然由于我的函数里定义的不是原子操作,所以cout的时候就混杂了~
所以可以用到<mutex> 类里面的互斥量来解决一下,比如这样

#include <thread>
#include <mutex>
#include <iostream>
using namespace std;
void pause_thread(int n, mutex* mtx) {
	this_thread::sleep_for(chrono::seconds(2));
	(*mtx).lock();
	cout << "thread of " << n << " ended\n";
	(*mtx).unlock();
}
int main() {
	int N = 0;
	cin >> N;
	thread* ths = new thread[N];
	mutex mtx;
	for (int i = 0; i < N; i++) {
		ths[i] = thread(pause_thread, i, &mtx);
	}
	cout << "Finished spawning threads." << endl;
	for (int i = 0; i < N; i++) {
		ths[i].join();
	}
	cout << "All threads joined!" << endl;
	delete[]ths;
	return 0;
}

然后我们可以看到,输出不会绕在一起了~当然还是无序的,哈哈
cpp11_mutex
 
查文档的时候注意到,竟然还有死锁检测相关的exception可能会抛出,有点良心的…这几天好好研究一下~
 

Categories
不学无术

C++ STL容器能力一览表

摘自《C++标准程序库 (The Standard C++ Library)》pp.227
未摘齐,需要详细可参考6.9节:各种容器的运用时机
STL_container_compare

Categories
不学无术

C++类型转换符 static_cast, dynamic_cast, const_cast

“cast”一词在英文里有“浇铸”的意思,还是挺形象的。

1.static_cast

可以看做是利用一个原始值构建一个临时对象,并再设定初始值的时候使用类型转换。
例如:

float x;
...
cout << static_cast<int>(x); //float to int
...
cout << static_cast<string>("hello")); //char* to string

2.dynamic_cast

将多态类型(polymorphic type)成员向下转换为其对应的静态类型成员。这个cast是在运行时实时检验的,因此可以用来检测某个指针指向的对象到底是不是XXX类的。

class Car; //abstract class
class Cabriolet : public Car {...};
class Limousine : public Car {...};
void f(Car* cp){
    Cabriolet* p = dynamic_cast<Cabriolet*>(cp);
    if(p == NULL) {
        //cp is not referred to an object of Cabriolet
    }
}

当参数是个引用,并且类别转换失败的时候,会抛出bad_cast异常哦。

3.const_cast

去除某个对象的const修饰作用,也可以拿来去除volatile修饰作用。
 

Categories
不学无术

C++异常处理,stack unwinding

这篇文章的内容摘自《C++标准程序库》2.2.3节
C++标准程序库可以在不污染函数接口的情况下处理异常。如果你遇到一个意外情况,可以跑出异常来停止后续流程,例如:

class Error;
void f()
{
    ...
    if(exception-condition)
        throw Error();
    }
    ...
}

其中throw开始了stack unwinding过程,也就是说,他将使得退离任何函数区段时的行为像以return语句返回一样,然而程序却不会跳转到任何地点。对于所有被声明与某区段——而该区段却因程序异常而退离——的局部对象而言,会调用它的析构函数stack unwinding的动作会持续到退出main()或被某个catch子句捕捉并处理了异常为止。
异常对象(exception objects)其实就是一般类或基本类的对象,可以是int,string类型的对象,也可以是某个模板类对象。
 

Categories
不学无术 木有技术

1065. A+B and C (64bit) (20)

http://www.patest.cn/contests/pat-a-practise/1065


 

原题如下

Given three integers A, B and C in [-263, 263], you are supposed to tell whether A+B > C.
Input Specification:
The first line of the input gives the positive number of test cases, T (<=10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.
Output Specification:
For each test case, output in one line “Case #X: true” if A+B>C, or “Case #X: false” otherwise, where X is the case number (starting from 1).
Sample Input:

3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0

Sample Output:

Case #1: false
Case #2: true
Case #3: false

 
分析,其实就是自己做加减法进位的问题,需要考虑正负号的细节。
正负数加减法的规则可以参考百度文库,一大堆小学生教材,哈哈~
大概是这样,比较两个数a和b:

  • 最终结果符号的判定:如果|a|>=|b|那么结果的符号与a相同,反之符号与b相同;
  • 数值计算,不管正负号,用绝对值大的那个做操作数1,绝对值小的做操作数2,如果a,b同号做操作数1+操作数2,异号做操作数1操作数2

 
我的代码(好久没写c++,各种复杂,见谅)
其中isBiggerAbs是判断a与b的绝对值大小的,isBigger是判断实际值大小的,swapss是交换元素。
另外0x30是字符’0’的ASCII码来着~输入的时候是按照字符流看待的,计算的时候转换成了数字,然后比较的时候为了和c比方便又转换回去了。
另外给的Sample Input里面那个一长串的就是上限和下限了,加上符号20位足够放。

#include <iostream>
#include <string.h>
using namespace std;
void swapss(char*a, char* b)
{
	char t[20];
	strcpy(t, a);
	strcpy(a, b);
	strcpy(b, t);
}
bool isBiggerAbs(char* a, char* b)
{
	int len_a, len_b;
	len_a = strlen(a);
	len_b = strlen(b);
	if (len_a > len_b)
		return true;
	else if (len_a < len_b)
		return false;
	//只需比较位数一样的
	for (int i = 0; i < len_a; i++)
	{
		if (a[i] > b[i])
			return true;
		else if (a[i] < b[i])
			return false;
	}
	//完全相等
	return false;
}
bool isBigger(char* a, char* b)
{
	//Judge if a > b
	bool neg_a = (a[0] == '-');
	bool neg_b = (b[0] == '-');
	if (neg_a && !neg_b)
		return false;
	else if (!neg_a && neg_b)
		return true;
	if (!neg_a)
		return isBiggerAbs(a, b);
	else
	{
		a = strtok(a, "-");
		b = strtok(b, "-");
		return !isBiggerAbs(a, b);
	}
}
void bigPlus(char* a, char* b, char* r)
{
	// c = a + b
	int len_a, len_b;
	bool isNeg_a = false;
	bool isNeg_b = false;
	bool isNeg_r = false;
	if (a[0] == '-')
	{
		char* pch = strtok(a, "-");
		a = pch;
		isNeg_a = true;
	}
	if (b[0] == '-')
	{
		char* pch = strtok(b, "-");
		b = pch;
		isNeg_b = true;
	}
	if (!isBiggerAbs(a, b))
	{
		//Swap a and b
		swapss(a, b);
		isNeg_r = isNeg_b;
	}
	else
		isNeg_r = isNeg_a;
	if (isNeg_a)
	{
		bool t = isNeg_a;
		isNeg_a = isNeg_b;
		isNeg_b = t;
	}
	len_a = strlen(a);
	len_b = strlen(b);
	int index_a = len_a - 1;
	int index_b = len_b - 1;
	int remainder = 0;
	int count = 0;
	while (index_a >= 0 || index_b >= 0)
	{
		int op0 = 0;
		if (index_a >=0 )
			op0 = (int)a[index_a] - 0x30;
		if (isNeg_a)
			op0 = -op0;
		int op1 = 0;
		if (index_b >= 0)
			op1 = (int)b[index_b] - 0x30;
		if (isNeg_b)
			op1 = -op1;
		int result = op0 + op1 + remainder;
		if (result < 0)
		{
			remainder = -1; //negative raminder (<'0')
			result += 10;
		}
		else if (result > 9)
		{
			remainder = 1; //positive remainder (>'9')
			result -= 10;
		}
		else
			remainder = 0;
		r[count++] = (char)(result + 0x30);
		index_a--;
		index_b--;
	}
	//Deal with the last remainder
	if (remainder > 0)
	{
		r[count++] = (char)(remainder+0x30);
	}
	else if (remainder < 0)
	{
		r[count++] = (char)(remainder + 0x30);
	}
	if (isNeg_r)
		r[count++] = '-';
	char temp[21];
	int t = 0;
	while ((--count) >= 0)
	{
		temp[t++] = r[count];
	}
	temp[t] = '\0';
	strcpy(r, temp);
}
int main()
{
	//Read huge integer as charset
	int T; //Nubmer of test cases
	cin >> T;
	char a[20];
	char b[20];
	char c[20];
	char result[21];
	for (int i = 0; i < T; i++)
	{
		//Deal with test cases
		cin >> a >> b >> c;
		bigPlus(a, b, result);
		bool is_bigger = isBigger(result, c);
		cout << "Case #" << i + 1 << ": ";
		if (is_bigger)
			cout << "true";
		else
			cout << "false";
		if (i < T - 1)
			cout << endl;
	}
	return 0;
}

 


结果

评测结果

时间 结果 得分 题目 语言 用时(ms) 内存(kB) 用户
2月22日 20:46 答案正确 20 1065 C++ (g++ 4.7.2) 1 360

测试点

测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 360 12/12
1 答案正确 1 360 4/4
2 答案正确 1 360 4/4

 

Categories
不学无术

wcstombs转换中文的问题

http://blog.chinaunix.net/uid-1878979-id-2817097.html

在应用中碰到中文的字符串用wcstombs转换后,就成了NULL。查了一些一资料后,发现需要调用setlocale函数。这个是针对Unicode来说的,对于使用多国语言的时候需要使用该函数来定义语种
     setlocale(LC_ALL,””);     //设置本地默认Locale. 或者是setlocale(LC_ALL, “chs”)
wcstombs(dest, source, length);
setlocale(LC_ALL,”C”);     //默认