怎样区分 const char* 和字符串文字量

作者: csdn-whinah 发表日期: 2011年06月04日分类: C++ 评论: 3 条阅读次数: 4,688 次

在一个面试中，猛然间一闪念，问到了 candidate 这个问题。无解……

stl 中使用到了很多 traits 技术，只要懂得 traits ，这个问题就太简单了！以下是代码示例：

软件工程中很多地方，如果采用直接的办法不能解决问题，增加一个间接层，问题即迎刃而解，type_traits 就是这样一种技术，这个代码示例是自包含的，除了 printf ，没有任何其它外部依赖。

#include <stdio.h>
struct true_{};
struct false_{};
template<class T> struct isarray;
template<class T, int N>
struct isarray<T[N]> { typedef  true_ type; };
template<class T>
struct isarray<T*  > { typedef false_ type; };
void f(const char* s, false_) {
    printf("const char*/n");
}
template<int N>
void f(char const (&s)[N], true_) {
    printf("const char[N=%d]/n", N);
}
template<class T>
void f(const T& x) {
    f(x, typename isarray<T>::type());
}
int main() {
    const char* pc = "abc";
    const char s[] = "1234";
    f("123");
    f(s);
    f(pc);
    return 0;
}

#include <stdio.h>

struct true_{};

struct false_{};

template<class T> struct isarray;

template<class T, int N>

struct isarray<T[N]> { typedef true_ type; };

template<class T>

struct isarray<T* > { typedef false_ type; };

void f(const char* s, false_) {

printf("const char*/n");

}

template<int N>

void f(char const (&s)[N], true_) {

printf("const char[N=%d]/n", N);

}

template<class T>

void f(const T& x) {

f(x, typename isarray<T>::type());

}

int main() {

const char* pc = "abc";

const char s[] = "1234";

f("123");

f(s);

f(pc);

return 0;

}

为什么下面这样的代码不能work？

void f(const char* s) {
    printf("const char*/n");
}
template<int N>
void f(char const (&s)[N]) {
    printf("const char[N=%d]/n", N);
}

void f(const char* s) {

printf("const char*/n");

}

template<int N>

void f(char const (&s)[N]) {

printf("const char[N=%d]/n", N);

}

答案：C++的重载匹配规则：如果在非模板的候选中能找到一个”精确”匹配，就不会去找模板。”精确”的精确定义包含3大类，5种具体情况，按顺序如下：

Identity Conversion —- 不需要任何转化，最精确，级别 1

Lvalue to Rvalue Conversion — 左值到右值转化，级别 2

Array to Pointer Conversion — 数组到指针转化，级别 3

Function to Pointer — 函数名到函数指针，级别 4，这就是为什么很多时候我们不需要使用 &func_name 而直接使用 func_name

Quolification Conversion — cv qualify 少的可以转化到 cv qualify 多的，级别 5

这也就是为什么下面的代码可以 work：

template<class T>
void f(T x) { printf("f(T)/n"); }
void f(int x) { printf("f(int)/n"); }
.....
f(1); // call f(int)
f(1L); // call f(T)
f('c'); // call f(T)

template<class T>

void f(T x) { printf("f(T)/n"); }

void f(int x) { printf("f(int)/n"); }

.....

f(1); // call f(int)

f(1L); // call f(T)

f('c'); // call f(T)

char -> int 不是 exact match, 是 integeral promotion.

long -> int 不是 exact match, 是 integeral conversion.

将递归转化成迭代的通用技术

作者: csdn-whinah 发表日期: 2011年05月14日分类: 算法评论: 0 条阅读次数: 2,400 次

从理论上讲，只要允许使用栈，所有的递归程序都可以转化成迭代。

但是并非所有递归都必须用栈，不用堆栈也可以转化成迭代的，大致有两类

尾递归：可以通过简单的变换，让递归作为最后一条语句，并且仅此一个递归调用。

// recursive
int fac1(int n) {
    if (n <= 0) return 1;
    return n * fac1(n-1);
}
// iterative
int fac2(int n) {
    int i = 1, y = 1;
    for (; i <= n; ++i) y *= i;
    return y;
}

// recursive

int fac1(int n) {

if (n <= 0) return 1;

return n * fac1(n-1);

}

// iterative

int fac2(int n) {

int i = 1, y = 1;

for (; i <= n; ++i) y *= i;

return y;

}

自顶向下->自底向上：对程序的结构有深刻理解后，自底向上计算，比如 fibnacci 数列的递归->迭代转化。

// recursive, top-down
int fib1(int n) {
    if (n <= 1) return 1;
    return fib1(n-1) + fib1(n-2);
}
// iterative, down-top
int fib2(int n) {
    int f0 = 1, f1 = 1, i;
    for (i = 2; i <= n; ++i) {
        int f2 = f1 + f0;
        f0 = f1; f1 = f2;
    }
    return f1;
}

// recursive, top-down

int fib1(int n) {

if (n <= 1) return 1;

return fib1(n-1) + fib1(n-2);

}

// iterative, down-top

int fib2(int n) {

int f0 = 1, f1 = 1, i;

for (i = 2; i <= n; ++i) {

int f2 = f1 + f0;

f0 = f1; f1 = f2;

}

return f1;

}

对于非尾递归，就必须使用堆栈。可以简单生硬地使用堆栈进行转化：把函数调用和返回的地方翻译成汇编代码，然后把对硬件 stack 的 push, pop 操作转化成对私有 stack 的 push, pop ，这其中需要特别注意的是对返回地址的 push/pop，对应的硬件指令一般是 call/ret。使用私有 stack 有两个好处：

可以省去公用局部变量，也就是在任何一次递归调用中都完全相同的函数参数，再加上从这些参数计算出来的局部变量。
如果需要得到当前的递归深度，可以从私有 stack 直接拿到，而用递归一般需要一个单独的 depth 变量，然后每次递归调用加 1。

我们把私有 stack 元素称为 Frame，那么 Frame 中必须包含以下信息：

返回地址（对应于每个递归调用的下一条语句的地址）
对每次递归调用都不同的参数

通过实际操作，我发现，有一类递归的 Frame 可以省去返回地址！所以，这里又分为两种情况：

Frame 中可以省去返回地址的递归：仅有两个递归调用，并且其中有一个是尾递归。

// here used a function 'partition', but don't implement it
tempalte<class RandIter>
void QuickSort1(RandIter beg, RandIter end) {
    if (end - beg <= 1) return;
    RandIter pos = partition(beg, end);
    QuickSort1(beg, pos);
    QuickSort1(pos + 1, end);
}
tempalte<class RandIter>
void QuickSort2(RandIter beg, RandIter end) {
    std::stack<std::pair<RandIter> > stk;
    stk.push({beg, end});
    while (!stk.empty()) {
        std::pair<RandIter, RandIter> ii = stk.top(); stk.pop();
        if (ii.second - ii.first) > 1) {
            RandIter pos = partition(beg, end);
            stk.push({ii.first, pos});
            stk.push({pos + 1, ii.second});
        }
    }
}

// here used a function 'partition', but don't implement it

tempalte<class RandIter>

void QuickSort1(RandIter beg, RandIter end) {

if (end - beg <= 1) return;

RandIter pos = partition(beg, end);

QuickSort1(beg, pos);

QuickSort1(pos + 1, end);

}

tempalte<class RandIter>

void QuickSort2(RandIter beg, RandIter end) {

std::stack<std::pair<RandIter> > stk;

stk.push({beg, end});

while (!stk.empty()) {

std::pair<RandIter, RandIter> ii = stk.top(); stk.pop();

if (ii.second - ii.first) > 1) {

RandIter pos = partition(beg, end);

stk.push({ii.first, pos});

stk.push({pos + 1, ii.second});

}

Frame 中必须包含返回地址的递归，这个比较复杂，所以我写了个完整的示例：

以MergeSort为例，因为 MergeSort 是个后序过程，两个递归调用中没有任何一个是尾递归
MergeSort3 使用了 GCC 的 Label As Value 特性，只能在 GCC 兼容的编译器中使用
单纯对于这个实例来说，返回地址其实只有两种，返回地址为 0 的情况可以通过判断私有栈(varname=stk)是否为空，stk为空时等效于 retaddr == 0。如果要精益求精，一般情况下指针的最低位总是0，可以把这个标志保存在指针的最低位，当然，如此的话就无法对 sizeof(T)==1 的对象如 char 进行排序了。

#include <stdio.h>
#include <string.h>
# if 1
#include <stack>
#include <vector>
template<class T>
class MyStack : public std::stack<T, std::vector<T> >
{
};
#else
template<class T>
class MyStack {
	union {
		char*  a;
	   	T* p;
   	};
	int n, t;
public:
	explicit MyStack(int n=128) {
		this->n = n;
		this->t = 0;
		a = new char[n*sizeof(T)];
	}
	~MyStack() {
		while (t > 0)
			pop();
		delete[] a;
	}
	void swap(MyStack<T>& y) {
		char* q = y.a; y.a = a; a = q;
		int z;
		z = y.n; y.n = n; n = z;
		z = y.t; y.t = t; t = z;
	}
	T& top() const { 
		return p[t-1];
   	}
	void pop() {
		--t;
		p[t].~T();
	}
	void push(const T& x) {
		x.print(); // debug
		p[t] = x;
		++t;
	}
	int size() const { return t; }
	bool empty() const { return 0 == t; }
	bool full() const { return n == t; }
};
#endif
template<class T>
struct Frame {
	static T* base;
	T *beg, *tmp;
	int len;
	int retaddr;
	Frame(T* beg, T* tmp, int len, int retaddr)
		: beg(beg), tmp(tmp), len(len), retaddr(retaddr)
	{}
	void print() const { // for debug
		printf("%4d %4d %d/n", int(beg-base), len, retaddr);
	}
};
template<class T> T* Frame<T>::base;
#define TOP(field) stk.top().field
template<class T>
bool issorted(const T* a, int n)
{
	for (int i = 1; i < n; ++i) {
		if (a[i-1] > a[i]) return false;
	}
	return true;
}
template<class T>
void mymerge(const T* a, int la, const T* b, int lb, T* c) {
	int i = 0, j = 0, k = 0;
	for (; i < la && j < lb; ++k) {
		if (b[j] < a[i])
			c[k] = b[j], ++j;
		else
			c[k] = a[i], ++i;
	}
	for (; i < la; ++i, ++k) c[k] = a[i];
	for (; j < lb; ++j, ++k) c[k] = b[j];
}
template<class T>
void MergeSort1(T* beg, T* tmp, int len) {
	if (len > 1) {
		int mid = len / 2;
		MergeSort1(beg    , tmp    , mid);
		MergeSort1(beg+mid, tmp+mid, len-mid);
		mymerge(tmp, mid, tmp+mid, len-mid, beg);
		memcpy(tmp, beg, sizeof(T)*len);
	}
	else
		*tmp = *beg;
}
template<class T>
void MergeSort2(T* beg0, T* tmp0, int len0) {
	int mid;
	int cnt = 0;
	Frame<T>::base = beg0;
	MyStack<Frame<T> > stk;
	stk.push(Frame<T>(beg0, tmp0, len0, 0));
	while (true) {
		++cnt;
		if (TOP(len) > 1) {
			mid = TOP(len) / 2;
			stk.push(Frame<T>(TOP(beg), TOP(tmp), mid, 1));
			continue;
L1:
			mid = TOP(len) / 2;
			stk.push(Frame<T>(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid, 2));
			continue;
L2:
			mid = TOP(len) / 2;
			mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));
			memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));
		} else
			*TOP(tmp) = *TOP(beg); 
		int retaddr0 = TOP(retaddr);
		stk.pop();
		switch (retaddr0) {
		case 0: return;
		case 1: goto L1;
		case 2: goto L2;
		}
	}
}
// This Implementation Use GCC's goto saved label value
// Very similiar with recursive version
template<class T>
void MergeSort3(T* beg0, T* tmp0, int len0) {
MyEntry:
	int mid;
	int retaddr;
	Frame<T>::base = beg0;
	MyStack<Frame<T> > stk;
	stk.push(Frame<T>(beg0, tmp0, len0, 0));
#define Cat1(a,b) a##b
#define Cat(a,b) Cat1(a,b)
#define HereLabel() Cat(HereLable_, __LINE__)
#define RecursiveCall(beg, tmp, len) /
	stk.push(Frame<T>(beg, tmp, len, (char*)&&HereLabel() - (char*)&&MyEntry)); /
	continue; /
	HereLabel():;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// retaddr == 0 是最外层的递归调用，
// 只要到达这一层时 retaddr 才为 0,
// 此时就可以返回了
#define MyReturn /
	retaddr = TOP(retaddr); /
	stk.pop(); /
	if (0 == retaddr) { /
		return; /
   	} /
	goto *((char*)&&MyEntry + retaddr);
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	while (true) {
		if (TOP(len) > 1) {
			mid = TOP(len) / 2;
			RecursiveCall(TOP(beg), TOP(tmp), mid);
			mid = TOP(len) / 2;
			RecursiveCall(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid);
			mid = TOP(len) / 2;
			mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));
			memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));
		} else
			*TOP(tmp) = *TOP(beg); 
		MyReturn;
	}
}
template<class T>
void MergeSortDriver(T* beg, int len, void (*mf)(T* beg_, T* tmp_, int len_))
{
	T* tmp = new T[len];
	(*mf)(beg, tmp, len);
	delete[] tmp;
}
#define test(a,n,mf) /
	memcpy(a, b, sizeof(a[0])*n); /
	MergeSortDriver(a, n, &mf); /
	printf("sort by %s:", #mf); /
	for (i = 0; i < n; ++i) printf("% ld", a[i]); /
	printf("/n");
int main(int argc, char* argv[])
{
	int n = argc - 1;
	int i;
	long* a = new long[n];
	long* b = new long[n];
	for (i = 0; i < n; ++i)
		b[i] = strtol(argv[i+1], NULL, 10);
	test(a, n, MergeSort1);
	test(a, n, MergeSort2);
	test(a, n, MergeSort3);
	printf("All Successed/n");
	delete[] a;
	delete[] b;
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

#include <stdio.h>

#include <string.h>

# if 1

#include <stack>

#include <vector>

template<class T>

class MyStack : public std::stack<T, std::vector<T> >

{

};

#else

template<class T>

class MyStack {

union {

char* a;

T* p;

};

int n, t;

public:

explicit MyStack(int n=128) {

this->n = n;

this->t = 0;

a = new char[n*sizeof(T)];

}

~MyStack() {

while (t > 0)

pop();

delete[] a;

}

void swap(MyStack<T>& y) {

char* q = y.a; y.a = a; a = q;

int z;

z = y.n; y.n = n; n = z;

z = y.t; y.t = t; t = z;

}

T& top() const {

return p[t-1];

}

void pop() {

--t;

p[t].~T();

}

void push(const T& x) {

x.print(); // debug

p[t] = x;

++t;

}

int size() const { return t; }

bool empty() const { return 0 == t; }

bool full() const { return n == t; }

};

#endif

template<class T>

struct Frame {

static T* base;

T *beg, *tmp;

int len;

int retaddr;

Frame(T* beg, T* tmp, int len, int retaddr)

: beg(beg), tmp(tmp), len(len), retaddr(retaddr)

{}

void print() const { // for debug

printf("%4d %4d %d/n", int(beg-base), len, retaddr);

}

};

template<class T> T* Frame<T>::base;

#define TOP(field) stk.top().field

template<class T>

bool issorted(const T* a, int n)

{

for (int i = 1; i < n; ++i) {

if (a[i-1] > a[i]) return false;

}

return true;

}

template<class T>

void mymerge(const T* a, int la, const T* b, int lb, T* c) {

int i = 0, j = 0, k = 0;

for (; i < la && j < lb; ++k) {

if (b[j] < a[i])

c[k] = b[j], ++j;

else

c[k] = a[i], ++i;

}

for (; i < la; ++i, ++k) c[k] = a[i];

for (; j < lb; ++j, ++k) c[k] = b[j];

}

template<class T>

void MergeSort1(T* beg, T* tmp, int len) {

if (len > 1) {

int mid = len / 2;

MergeSort1(beg , tmp , mid);

MergeSort1(beg+mid, tmp+mid, len-mid);

mymerge(tmp, mid, tmp+mid, len-mid, beg);

memcpy(tmp, beg, sizeof(T)*len);

}

else

*tmp = *beg;

}

template<class T>

void MergeSort2(T* beg0, T* tmp0, int len0) {

int mid;

int cnt = 0;

Frame<T>::base = beg0;

MyStack<Frame<T> > stk;

stk.push(Frame<T>(beg0, tmp0, len0, 0));

while (true) {

++cnt;

if (TOP(len) > 1) {

mid = TOP(len) / 2;

stk.push(Frame<T>(TOP(beg), TOP(tmp), mid, 1));

continue;

L1:

mid = TOP(len) / 2;

stk.push(Frame<T>(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid, 2));

continue;

L2:

mid = TOP(len) / 2;

mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));

memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));

} else

*TOP(tmp) = *TOP(beg);

int retaddr0 = TOP(retaddr);

stk.pop();

switch (retaddr0) {

case 0: return;

case 1: goto L1;

case 2: goto L2;

}

// This Implementation Use GCC's goto saved label value

// Very similiar with recursive version

template<class T>

void MergeSort3(T* beg0, T* tmp0, int len0) {

MyEntry:

int mid;

int retaddr;

Frame<T>::base = beg0;

MyStack<Frame<T> > stk;

stk.push(Frame<T>(beg0, tmp0, len0, 0));

#define Cat1(a,b) a##b

#define Cat(a,b) Cat1(a,b)

#define HereLabel() Cat(HereLable_, __LINE__)

#define RecursiveCall(beg, tmp, len) /

stk.push(Frame<T>(beg, tmp, len, (char*)&&HereLabel() - (char*)&&MyEntry)); /

continue; /

HereLabel():;

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// retaddr == 0 是最外层的递归调用，

// 只要到达这一层时 retaddr 才为 0,

// 此时就可以返回了

#define MyReturn /

retaddr = TOP(retaddr); /

stk.pop(); /

if (0 == retaddr) { /

return; /

} /

goto *((char*)&&MyEntry + retaddr);

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

while (true) {

if (TOP(len) > 1) {

mid = TOP(len) / 2;

RecursiveCall(TOP(beg), TOP(tmp), mid);

mid = TOP(len) / 2;

RecursiveCall(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid);

mid = TOP(len) / 2;

mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));

memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));

} else

*TOP(tmp) = *TOP(beg);

MyReturn;

}

template<class T>

void MergeSortDriver(T* beg, int len, void (*mf)(T* beg_, T* tmp_, int len_))

{

T* tmp = new T[len];

(*mf)(beg, tmp, len);

delete[] tmp;

}

#define test(a,n,mf) /

memcpy(a, b, sizeof(a[0])*n); /

MergeSortDriver(a, n, &mf); /

printf("sort by %s:", #mf); /

for (i = 0; i < n; ++i) printf("% ld", a[i]); /

printf("/n");

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

{

int n = argc - 1;

int i;

long* a = new long[n];

long* b = new long[n];

for (i = 0; i < n; ++i)

b[i] = strtol(argv[i+1], NULL, 10);

test(a, n, MergeSort1);

test(a, n, MergeSort2);

test(a, n, MergeSort3);

printf("All Successed/n");

delete[] a;

delete[] b;

return 0;

}

怎么减少错误的发生

作者: csdn-whinah 发表日期: 2011年04月03日分类: 杂谈评论: 11 条阅读次数: 6,529 次

错误，我们暂且仅对软件开发而言。

错误的类别，暂且仅考虑接口错误和实现错误。

接口错误
- 一般可以分为误解和失配
- 误解

比如在一段公路入口有巨大的标识牌，上面写着：前方道路，靠左行，红灯行，绿灯停。这个大家可能觉得很荒谬，然而类似的事情在软件开发里面却层出不穷，生产方认为自己已经在文档中清楚地说明了用法和用途，然而他却没有意识到这与使用方的常识和惯例背道而驰。举个简单的例子，C 标准库里面的两个函数：

#include <stdio.h>
size_t fwrite(const void * ptr, size_t size, size_t count, FILE * stream);
#include <stdlib.h>
void qsort(void * base, size_t num, size_t size, int (* comparator)(const void *, const void *) );

#include <stdio.h>

size_t fwrite(const void * ptr, size_t size, size_t count, FILE * stream);

#include <stdlib.h>

void qsort(void * base, size_t num, size_t size, int (* comparator)(const void *, const void *) );

我不知道有多少人用过这两个函数，但是，大体上，应该是用 fwrite 的人多，而用 qsort 的人少。而用 fwrite 的人，大多数情况下，传递的 size 都等于 1，并且，一般情况下，size 和 count 搞反了也不会有啥大问题，除非判断了返回值。然而，一旦用多了 fwrite，并且吧 ObjectSize, ObjectCount 这个顺序当成了一个常识，再使用 qsort 的时候，就悲剧了！

还有一个例子：stl 的 range，一般表示为前闭后开的 [begin, end) 区间，如果你要搞一个前开后闭的 (begin, end] 区间，大家都会疯掉不可。我确实曾经被这样的 (begin, end] 疯掉过。

- 失配

一般情况下，发生在版本兼容问题上。我仅举一个简单例子：在Bash3.x中，[[]] 中的正则表达式会按Bash的quoting removal 规则进行处理，也就是说对于一般的正则表达式，加单引号，双引号，和不加引号，都没有区别，然而到了Bash4.x，如果加了引号，就悲剧了！Bash4.x会把引号当成正则表达式的一部分！

- 另一种接口错误

最近我在挤地铁时发现了另一类错误，看上去似乎不属于这两种：人很挤的时候，在地铁楼梯上，经常发现，人们走的是左边，而不是右边，稍微用心一下，就会发现这是什么原因——人们总是按贪心算法走最短路径，刚下地铁的人，会走挨地铁（车厢）的楼梯一侧，而这一侧正好是左边，上面往下走的人，却是走右边。在人流量不大的时候，这不是什么问题，然而，当人流汹涌时，造成的拥堵让大家都很郁闷。

怎么解决这个问题呢？——那就是在设计地铁站时，让贪心算法的最短路径是右边，而不是左边。再General一点，就是：设计要遵守人们的思维习惯。

在程序设计上，如果我们设计的接口符合人的思维习惯，可以大大减少错误的发生。在 C 里面，至少有两处设计违反人的直觉，不过还好，这两处早被 deprecate 了：

1. 1. 函数的默认返回值为 int，而非 void
  2. f() 表示可接受任意个参数，返回值为 int 的函数。

实现错误

一般情况下，就是指我们程序的逻辑错误

C++ 如何动态库实现接口兼容

作者: csdn-whinah 发表日期: 2011年04月03日分类: C++ 评论: 0 条阅读次数: 1,921 次

看了一篇文章：避免使用虚函数作为库的接口

其中提到C++虚表的僵硬，导致版本更新时二进制兼容性的问题。

其实这个问题不是C++的问题，而是C++实现的问题。如果接口的二进制兼容性是一个强制需求，在不影响运行效率的情况下，C++是完全可以实现的，不过需要多一点的空间开销和初始化开销。

具体的方法可以参考 PE 文件中的 Import Table 和 Export Table。

简单地讲，就是 App 和 DLL 各自维护一个 name->func_address 的映射数组，当然，这个 name 应该是名字碾碎后的 name 。加载 DLL 时，将 DLL 中 Export Table 中相应项填到 App 中相应的 Import Table 中，App 中的虚函数调用仍然到那个地方去取函数指针，但是对不同版本的 DLL，甚至是不同实现的 DLL，那个值是不同的，这没有任何问题。

具体的算法，在 PE 文件中，Import Table 中的项一般比相应 DLL 的 Export Table 项少得多，所以，它使用二分查找（当然，它还有很多优化，如 hint, by ordinal，bound import 等等）。对于虚函数的情形，因为 Import 和 Export 的项数差不多，使用 Merge 算法会更快一点。

以前在做嵌入式系统的时候，会把绝大部分函数都放到查找表中，也是类似的道理，因为 ROM 最便宜，然而 ROM 是 Read Only Memory，release 之后，客户买到产品，要修改怎么办？还好，系统中不是光有ROM，还要少量 EEPROM，于是，事情就好办了，查找表和 Fix 的新代码，都可以放到 EEPROM 中，只需要在更新系统时将 Fix 的新函数地址填入查找表中相应的位置。

如果C++哪天要统一abi，这样的东西应该是必不可少的。

靠谱的程序员太少了

作者: csdn-whinah 发表日期: 2011年04月02日分类: 杂谈评论: 21 条阅读次数: 9,136 次

最近几个月，面试了不少的程序员，更好听的名字叫做软件工程师，甚至高级软件工程师。

我一般会针对面试者的特长，问一些相关的问题。有说擅长算法的，图像处理的，图形学的，数学的，C++的，Java，Perl 的，Shell 的，Linux内核的……

到目前为止，面试的人不算太多，但少说也过100了，基本上，语言方面和其它特长兼有的，一个也还没碰到过。

靠谱的C++程序员，所谓的靠谱，其实也就是：

了解 STL 的常用组件，能正确使用 STL
知道 type_traits ，以及如何使用 type_traits
对虚函数、重载、虚表有一定了解
能正确认识C++的异常
了解 Pure C 和 C++ 的 C 子集中比较常见的、明显的区别

基本上，就这 5 点，能有两点比较突出的，也就那么两三个人，而这两三个人里面，C++差不多就是他们唯一的特长了。

Java 上，我问的问题比较少，远不如 C++ 多，并且更简单，也就是：

int/long 的二进制位数，jvm 是否在不同平台 int/long 的二进制位数是否相同
对于 StringBuilder，每次追加一个字符，当其长度长到 n 时，时间复杂度是多少
能否把一个 String 对象，添加到一个 List<Integer> 中
Comparable 和 Comparator 有何区别，如何把非 Comparable 的对象作为 TreeMap 的 Key
GC 的基本原理（大部分人的回答是调节 gc 参数）

目前还没碰到一个人能回答第 4 个问题！呜呼！

算法+Coding：

90%以上的人不知道 make_heap 的时间复杂度，知道的人，也都是背的答案。
完全无 bug 的 binary_search ，只有 3% 。
std::lower_bound 类似功能的函数，目前还没一个人写得出来。
从一组 IP range –> value 的数据中查找单个 IP，允许使用 C++ stl 或 java 基础类，还没一个能给出解决办法。
QuickSort 的最好情况，和 MergeSort 的最好情况，哪个的 KeyCompare 次数更少，目前只有一个人答出。

如果在这些之外，还熟悉 perl, bash, python 等脚本语言的，更是凤毛麟角。

要知道，这些职位可都是年薪20w以上的！

欢迎同道之士加盟，可以站内联系我，有内部推荐机会。

是个软件都想强奸用户

作者: csdn-whinah 发表日期: 2011年01月29日分类: 杂谈评论: 2 条阅读次数: 3,092 次

Windows 7 资源管理器反应超慢已经很久了，刚刚这个问题被我彻底解决。使用 Autoruns 查看 Explorer 页，删掉所有可疑的王八蛋：继续阅读 →

地下军工厂大造“山寨”武器

作者: csdn-whinah 发表日期: 2010年01月27日分类: 杂谈评论: 0 条阅读次数: 2,560 次

很多所谓互联网高科技，与这山寨军工厂有何异？

本报特约记者章鲁生《青年参考》（ 2011年05月20日 21 版）

一家地下军工厂

一名反对派人员身背改造后的AK-47冲锋枪，在米苏拉塔市街头巡逻。

利比亚反对派和政府军的武装冲突已持续了两个多月，据美国《纽约时报》报道，反对派武装的武器装备可谓五花八门，拆卸下来的机载机关枪、世界大战时期的“古董枪”甚至牛排刀等，均被派上用场。但即使如此，武器依然短缺。

为了让更多的志愿者拥有武器，在反对派武装控制的利比亚西部城市米苏拉塔，一些地下军工厂（或许叫“地下作坊”更合适）开足马力，因陋就简地为反对派制造各种“山寨”武器。

“古董枪”没子弹，不如一块石头

迄今为止，利比亚政府军已围攻西部城市米苏拉塔长达8个星期。对反对派来说，米苏拉塔具有重大的战略意义——这是他们在利比亚西部占领的惟一一座城市。为了保住这块根据地，反对派动用了一切可以动用的“资源”。单从装备上讲，在米苏拉塔街头见到的武器，足以让人眼花缭乱。

最显眼的当属PKT机关枪。这种安装在苏联坦克上的重型机关枪没有枪托，没有准星，也没有手动扳机，全靠坦克车内的人遥控操纵。米苏拉塔的反对派成员只好扛着这种笨重的机关枪。

还有意大利的卡尔卡诺卡宾枪，这种枪或许是两次世界大战期间意大利对利比亚实行殖民统治时期留下的老古董，由于太过老旧，甚至没有配套的子弹可供使用。即使如此，《纽约时报》的记者奇弗斯仍在米苏拉塔街头见到4个反对派成员端着这种枪。

反对派手中的“古董枪”还有法国军队几十年前装备的MAT-49冲锋枪。和卡尔卡诺卡宾枪的情况一样，这种枪也没有配套的子弹。记者奇弗斯因此戏称，拿着一把MAT-49，还不如拿一块石头。

武器杂乱、“古董枪”多的现象，说明反对派武装武器匮乏。

31岁的菲克里·伊塔尤里曾在一辆配备了机关枪的卡车上战斗，后来机关枪和卡车一起被炸毁，他的武器只剩下一把很大的牛排刀，但伊塔尤里信心十足。“好在我还有这个……”他挥舞着那把有锯齿状刀锋的牛排刀，“我想用这把刀扎进卡扎菲的心脏！”

反对派表示，很多人志愿加入他们的组织，但枪支短缺影响了战斗力。

也有一些志愿者带着武器加入。在利比亚东部，一些志愿者花至少2000美元购买AK-47冲锋枪。这些人因此受到关注——等他们在战斗中倒下，就去捡他们的枪。

开足马力制造“山寨”武器

因为武器短缺，政府军围城后不久，米苏拉塔一些由反对派控制的地下工厂便开足马力，因陋就简地制造各种“山寨”武器。

米苏拉塔前线最常见的是加装了钢板装甲、车后载着机关枪的四门民用卡车。这些枪——如前文提到的PKT机关枪——多为冷战时期生产，本来安装在飞机或坦克上，现在反对派把它们安装在民用卡车上。很显然，这些因地制宜的武器都是地下工厂的“作品”。

为防止政府军的奸细搞破坏，反对派把这些地下工厂视为机密，甚少向外界透露。记者奇弗斯软磨硬泡了3天，才于5月2日获准到其中的两家工厂采访，条件是不得向外透露它们的具体地点，也不准拍工厂门口的照片，以免政府军“按图索骥”。

在奇弗斯看来，地下工厂制造的一些“山寨”武器很耗资源，但实用价值“存在疑问”。不过反对派对此不以为然，在他们看来，“只要能把卡扎菲的军队击退，任何花费都是值得的”。

总体来说，地下工厂加强了反对派的力量。此前，一些加入反对派武装的人只能拿着刀甚至石块走上前线，现在他们可以在后方的工厂里挥舞着榔头、举着电焊枪、操纵着车床，让更多反对派战士拥有“货真价实”的武器。

“如果我们一开始就有足够的武器，我也不会在这里了，我会和两个儿子一起在前线战斗，把卡扎菲的人赶跑。”在奇弗斯采访的一家地下工厂里，电焊工艾哈姆德·舍基说。

说话间，外面有炮声传来，震耳欲聋，但艾哈姆德仍动作熟练地把一块装甲钢板焊在一辆卡车上，仿佛没有听到爆炸声。

根本没工夫统计产量

记者奇弗斯看到，艾哈姆德身边堆放着他当天要完成的任务：4辆民用皮卡、产自不同国家的机关枪，还有一堆钢板。他得把这些机关枪安装到皮卡上，并把钢板在车上加固。机关枪太大太长？没关系，用钢锯锯掉多余的部分即可。

在工厂的另一个角落，30岁的奥马尔·艾尔·萨基尔正对着一挺.50口径（12.7毫米）的机关枪发呆，因为这挺机关枪没有扳机。

枪身上的标志显示，这是一挺比利时生产的M3M机载重型机关枪，但萨基尔并不清楚这些。沉思了一会儿，萨基尔终于想出该在哪里给这挺机关枪安装扳机。他制造出一个粗糙的扳机装了上去，一挺机关枪就这样“复活”了。它将被固定在皮卡上，成为夺命利器。

在这家工厂里，除了艾哈姆德和萨基尔，还有两组工人。一组正在锻造武器的旋转座，另一组在把钢板焊到皮卡上。工人们说，在天黑之前，这些皮卡将摇身变为他们的“装甲车队”。

这些即将变身为“装甲车”的皮卡，通常被从头到尾漆成黑色，车尾灯和方向灯也被摘掉。这样一来，政府军很难发现它们的行踪。

当被问及生产了多少辆此类“装甲车”时，这家工厂的车间主管巴希尔·扎尔加尼表示，“不太清楚”。

“太忙了，我们根本没工夫统计产量。”扎尔加尼说。

记者奇弗斯根据在米苏拉塔街头以及前线的所见所闻，认为此类“山寨装甲车”的数量“至少有100辆，很可能在200辆以上”。

生产军火的工人“自学成才”

“山寨装甲车”是反对派地下工厂的“主打产品”之一。奇弗斯曾在利比亚首都的黎波里街道上看到一种被称为“henzab”的武器，也出自反对派的地下军工厂。“henzab”是当地人的俗称，指的是一种铁器。这种铁家伙的大小跟一个棒球差不多，有五六厘米长的刺，若不小心踩上去，鞋底将被轻松刺穿。

与政府军在的黎波里激战时，反对派武装在政府军必经的道路上放了很多“henzab”，迫使他们缩在包围圈里被动挨打，许多政府军士兵被这种铁家伙扎伤了脚，政府军许多车辆的轮胎也被扎破。

在另一家地下工厂里，奇弗斯看到一名工人正在往RPG-7单兵火箭筒的火箭弹里装填炸药。RPG-7是利比亚反对派武装主要的“重武器”之一，能穿透坦克装甲。为了打击躲在建筑物中的政府军，反对派军械师阿里·拉马丹·埃尔加拉贝对这种武器进行了改造。他在火箭弹上加装了较厚的铝套筒，火箭弹击中混凝土墙壁爆炸后，会产生很多碎片，从而杀伤建筑物中的政府军。

“这种火箭弹，我每天能生产30到40枚。”埃尔加拉贝告诉奇弗斯。

和这家工厂的其他工人一样，埃尔加拉贝之前并无生产军火的任何经验，属于“自学成才”。

埃尔加拉贝改造的这种火箭弹，装填的炸药大部分来自军火零售商。为了获取更多炸药，他把缴获的一些炸弹拆开，取出炸药，装填到RPG-7的火箭弹中。让奇弗斯心悸的是，埃尔加拉贝用一个金属工具，而非木勺或木片，从炸弹中舀出炸药。试想一下，如果金属工具与炸弹壳摩擦产生火花……

反对派呼吁北约提供武器援助

美国有武器专家认为，增加弹体的长度与重量将降低RPG-7火箭弹攻击的准确性，尤其是在没有光学瞄准镜的情况下。

记者奇弗斯把这种改造后的弹体照片发给美国一名武器专家，专家看后回信说：“虽然（加装厚铝套筒的想法）很有创新精神，但我认为这样会使火箭弹前部变重，在飞行过程中急速下坠，无法击中目标。”看到工人用金属工具舀出炸药的照片后，这位武器专家告诫奇弗斯：“任何参观者都要避开这种场面。”

这些地下工厂的工人清楚，在不具备任何武器知识的情况下做这些事情是很危险的，但他们“别无选择”，因为每天都会有大量信息从前线传来，要求他们改进某些武器，“时间不等人”。

工人们表示，在“边摸索边实践”的过程中，他们学到了不少武器知识，“每周都有提高”。

一家地下工厂的车间主管巴希尔·扎尔加尼说：“每个人晚上回家都会苦苦思索，怎样才能做得更好？我们必须既快又好地完成工作，因为我们的城市正在遭受攻击，没有太多时间让我们慢慢研究。”

不过，即使开足马力，这些地下工厂的军火产量也无法满足巨大的战场消耗。5月9日，反对派呼吁北约尽快提供先进武器，以扭转不利局面。

5月11日，反对派控制了米苏拉塔的机场，美国国防部援助反对派的首批物资于当日“空降”，包括1万份即食口粮、医疗器械、帐篷、制服、靴子和防弹衣，但没有美制军火。看来，反对派的地下工厂还得努力提高产量。

rdtsc 备忘

作者: csdn-whinah 发表日期: 2010年01月09日分类: C++ 评论: 0 条阅读次数: 2,255 次

继续阅读 →

febird.dataio vs boost.serialization 运行性能对比

作者: csdn-whinah 发表日期: 2009年04月06日分类: C++序列化评论: 4 条阅读次数: 10,746 次

代码表示的是数据格式，DATA_IO_LOAD_SAVE 在 <febird/io/DataIO.h> 中定义

对于 boost.serialization， DATA_IO_LOAD_SAVE 的定义相当于：继续阅读 →

在 C 语言中实现模板函数的方法

作者: csdn-whinah 发表日期: 2004年06月07日分类: C++ 评论: 8 条阅读次数: 4,339 次

现以一个求和函数 Sum 为例，用 C++ Template 可写如下：

template<class T, class R>
R Sum(const T *array, int n) {
    R sum = 0;
    for (int i = 0; i < n; ++i) sum += i;
    return sum;
}

template<class T, class R>

R Sum(const T *array, int n) {

R sum = 0;

for (int i = 0; i < n; ++i) sum += i;

return sum;

}

如果不是内置类型，该模板隐式地需要有R R::operator+=(T)运算符可用。

三种使用 C 语言模拟C++的模板的方法

1. 使用函数指针作为 Functor 替换者

struct AddClass {
    Void (*add)(char* r1, const char* r2);
    Int elemSize;
    Char  sum[MAX_ELEM_SIZE];
};
void Sum(struct AddClass* self, const char* array, int n) {
     int i;
     for (i = 0; i < n; ++i)
         self->add(self->sum, array + i*self->elemSize);
}
 
// 使用时：
// …..
 
Void AddInt(char* r1, const char* r2) {
    *(long*)r1 += *(int*)r2;
}
AddClass addClass = {AddInt, 2, 0 };
Int array[100];
Read(array);
Sum(&addClass, array, 100);
// …..

struct AddClass {

Void (*add)(char* r1, const char* r2);

Int elemSize;

Char sum[MAX_ELEM_SIZE];

};

void Sum(struct AddClass* self, const char* array, int n) {

int i;

for (i = 0; i < n; ++i)

self->add(self->sum, array + i*self->elemSize);

}

// 使用时：

// …..

Void AddInt(char* r1, const char* r2) {

*(long*)r1 += *(int*)r2;

}

AddClass addClass = {AddInt, 2, 0 };

Int array[100];

Read(array);

Sum(&addClass, array, 100);

// …..

2. 用宏作为Functor的替换者

#define GenSumFun(SumFunName, Add, RetType, ElemType) \
RetType SumFunName (const ElemType *array, int n) {   \
    RetType sum = 0; int i;                           \
    for (i = 0 ; i < n ; ++i) Add(sum, i);            \
    return sum;                                       \
}
// 使用时：
#define AddInt(x, y)  ((x) += (y))
GenSumFun(SumInt, AddInt, long, int)
// …..
int array[100];
Read(array);
long sum = SumInt(array, 100);
// …..

#define GenSumFun(SumFunName, Add, RetType, ElemType) \

RetType SumFunName (const ElemType *array, int n) { \

RetType sum = 0; int i; \

for (i = 0 ; i < n ; ++i) Add(sum, i); \

return sum; \

}

// 使用时：

#define AddInt(x, y) ((x) += (y))

GenSumFun(SumInt, AddInt, long, int)

// …..

int array[100];

Read(array);

long sum = SumInt(array, 100);

// …..

3. 所有可替换参数均为宏

至少需要一个额外的文件(实现文件)为 impsum.c

/* impsum.c */
RetType FunName(const ElemType *array, int n) {                                                                     
    RetType sum = 0;
    int i;
    for (i = 0 ; i < n ; ++i) Add(sum, i);                            
    return sum;                                          
}
 
// 使用时：
#undef  RetType
#undef  FunName
#undef  ElemType
#undef  Add
#define AddInt(x, y)  ((x) += (y))
#define RetType long
#define FunName SumInt
#define ElemType int
#define Add  AddInt
 
#include impsum.c
 
…..
int array[100];
Read(array);
long sum = SumInt(array, 100);
…..

/* impsum.c */

RetType FunName(const ElemType *array, int n) {

RetType sum = 0;

int i;

for (i = 0 ; i < n ; ++i) Add(sum, i);

return sum;

}

// 使用时：

#undef RetType

#undef FunName

#undef ElemType

#undef Add

#define AddInt(x, y) ((x) += (y))

#define RetType long

#define FunName SumInt

#define ElemType int

#define Add AddInt

#include impsum.c

…..

int array[100];

Read(array);

long sum = SumInt(array, 100);

…..

总结：

第一种方法，易于跟踪调试，但是效率低下，适用于对可变函数（函数指针）的效率要求不高，但程序出错的可能性较大（复杂），模板函数（Sum）本身很复杂，模板参数也比较复杂（add）的场合。

第二种方法，效率高，但很难跟踪调试，在模板函数和模板参数本身都很复杂的时候更是如此。

第三种方法，是我最近几天才想出的，我认为是最好的，在模板参数（Add）比较复杂时可以用函数（第二种也可以如此），简单时可以用宏，并且，易于调试。在模板函数本身很复杂，而模板参数比较简单时更为优越。但是，可能有点繁琐。

一般情况下，没有必要做如此劳心的工作，一切交给编译器去做就行了。但是本人在开发一个文件系统时，由于是基于一种少见的平台，没有可用的C++编译器，有几个函数，除了其中的类型不同（uint16和uint32），和几个可参数化的宏不同，其它地方完全相同，而函数本身很复杂（两百多行代码）。Copy出几个完全类似的函数副本，维护起来特别烦人。非常需要如此的编程模式，故此，分享出来，大家共同探讨。

怎样区分 const char* 和字符串文字量

将递归转化成迭代的通用技术

怎么减少错误的发生

C++ 如何动态库实现接口兼容

靠谱的程序员太少了

是个软件都想强奸用户

地下军工厂大造“山寨”武器

rdtsc 备忘

febird.dataio vs boost.serialization 运行性能对比

在 C 语言中实现模板函数的方法

现以一个求和函数 Sum 为例，用 C++ Template 可写如下：

三种使用 C 语言模拟C++的模板的方法

1. 使用函数指针作为 Functor 替换者

2. 用宏作为Functor的替换者

3. 所有可替换参数均为宏

总结：

近期文章

近期评论

文章归档

分类目录

功能