HashMap<string, …> 能有多快
看到很多使用 map<string, ….> 的代码, 也有一些使用了 unordered_map<string, …> 或者 hash_map<string, …>, 当然, hash_map 不是标准的, unordered_map 也只在 boost, tr1 和 c++0x 中可用. 从代码的简洁性和可移植性上讲, 标准的 std::map 是首选. 继续阅读
怎样让C++函数重载时连返回值类型也加入重载决议?
众所周知,C++函数重载时返回值是不参与重载决议的, 也就是说: 继续阅读
Large Number of Coroutine is possible: Split Stacks in GCC
本文来源：http://gcc.gnu.org/wiki/SplitStacks
注：GCC4.6 已经支持 -split-stack 选项。Why Fiber/Coroutine? 可参考我的相关文章：异步通讯中使用纤程（Fiber/UserSpaceThread） 继续阅读
排列的分解
离散数学里面大家都学过群，群里面有种很基本并且很重要的叫做置换群，置换群的元素本质上就是一个排列（英文 permutation group, 直译过来应该是排列群）。大家应该都学过当初要把 (4 1 5 2 3) 分解成 (1 4 2)(3 5)，这个叫做群的 k-cycle 分解，也就是说，一个排列（置换群的一个元素）可以 继续阅读
穷举搜索
对于一些困难的问题，我们只能穷举(brut force)搜索，是的，我们知道“穷举搜索”这个词，可是，具体怎么穷举呢？
很多问题可以归结到图的搜索，对于图的搜索，大家应该都知道 DFS 和 BFS， 继续阅读
非对称类型的 Comparator
结构体数组，按字段查找
我有一个按字段 name 排好序的结构体数组，怎样使用 stl 来查找？
|
1 2 3 4 5 6 7 8 9 |
struct User { std::string name; std::string address; //more fields... }; //.... std::vector<User> v; // expected searching code auto i = std::lower_bound(v.begin(), v.end(), "whinah", CompareName()); |
怎样定义 CompareName ？
|
1 2 3 4 5 6 7 8 |
struct CompareName { bool operator()(const User& x, const std::string& y) const { return x.name < y; } bool operator()(const std::string& x, const User& y) const { return x < y.name; } }; |
一般的 Compare 这样定义：
|
1 2 3 4 5 |
struct CompareName { bool operator()(const User& x, const User& y) const { return x.name < y.name; } }; |
这样的 Compare 只能用于排序，如果要用于查找，我们必须先构造一个 User 对象，再把想查找的name assign 这个 User::name, ….
怎样区分 const char* 和字符串文字量
在一个面试中，猛然间一闪念，问到了 candidate 这个问题。无解……
stl 中使用到了很多 traits 技术，只要懂得 traits ，这个问题就太简单了！以下是代码示例：
软件工程中很多地方，如果采用直接的办法不能解决问题，增加一个间接层，问题即迎刃而解，type_traits 就是这样一种技术，这个代码示例是自包含的，除了 printf ，没有任何其它外部依赖。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#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？
|
1 2 3 4 5 6 7 |
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：
|
1 2 3 4 5 6 7 |
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.
C++ 如何动态库实现接口兼容
看了一篇文章：避免使用虚函数作为库的接口
其中提到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，这样的东西应该是必不可少的。
简单的代码生成器创建领域语言
有一类问题，代码模板相同，但有少部分地方不同，一般可以写一个复杂的程序，使用不同的选项，完成不同的任务。或者，把公共的部分抽象成一个代码库，然后在不同程序中引用。但是，如果公共的部分很少，并且比较“专用”，或者因为其它原因，比较难以部署。怎么办？
实际上，有另一种完全不同的编程模式来实现：代码生成器。unix世界中最知名的代码生成器莫过于lex和yacc了。但是，不比每个代码生成器都那么复杂，比如这个代码生成器就非常简单，它只是简单地转换行记录：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#! /bin/sh field_seperator="||" output=b while getopts :F:vo: arg do case $arg in F ) field_seperator=$OPTARG;; v ) ;; o ) output=$OPTARG;; : ) echo "$0: missing arg for -$OPTARG " >&2 exit;; /?) echo "Invalid option -$OPTARG ignored." >&2 exit;; esac done if [ $OPTIND -gt $# ] then # echo OPTIND=$OPTIND argc=$# >&2 echo "no program" >&2 exit fi program=${!#} echo field_seperator=$field_seperator cat > a.cpp <<+TemplateCFile #include <vector> #include <string.h> #include <stdio.h> const char field_seperator[]="||"; void split_row(char* line, std::vector<char*>& F, const char* fs) { char* col = line; F.resize(0); size_t fslen = strlen(fs); if (fslen == 1) { for (;;) { F.push_back(col); col = strchr(col, fs[0]); if (col) { col[0] = '/0'; col += 1; } else break; } } else { for (;;) { F.push_back(col); col = strstr(col, fs); if (col) { col[0] = '/0'; col += fslen; } else break; } } } int main(int argc, char* argv[]) { size_t len1 = 0; ssize_t len2; char* line = NULL; std::vector<char*> F; while ((len2 = getline(&line, &len1, stdin)) != -1) { split_row(line, F, field_seperator); int NF = F.size(); //--- begin user program +TemplateCFile echo $program >> a.cpp cat >> a.cpp <<+TemplateCFile //--- end user program ; // avoid user program missing ; printf("/n"); } if (line) free(line); if (ferror(stdin)) { perror("ferror(stdin)"); return 1; } return 0; } +TemplateCFile sed -i 's//(field_seperator/[/]=/).*";//1"'$field_seperator'";/g' a.cpp gcc -O2 a.cpp -lstdc++ -o $output exit $? |
可以象awk一样写程序：
|
1 2 3 |
# 相当于 awk -F, '{printf("%s/t%s/n", $1, $5)}' # 使用 ',' 做列分隔符，输出第 1 和第 5 个字段，生成二进制可执行程序 myprog ./gencode.sh -F , -o myprog 'printf("%s/t%s/n", F[0], F[4])' |
|
1 2 3 |
# 相当于 awk -F, '{printf("%s/t%s/n", $1, $5)}' # 使用 ',' 做列分隔符，输出第 1 和第 5 个字段，生成二进制可执行程序 myprog ./gencode.sh -F , -o myprog 'printf("%s/t%s/n", F[0], F[4])' |
我当初写这个生成器的原因是发现非常简单的 awk 程序也比 C 慢 40 倍，以为这是本质上的性能差距，后来才发现不是。
对这个简单的程序，使用awk更方便更安全，也不比C慢，但是一旦碰到其它类似问题而 awk 解决不了，这种模式就可以派上用场了。