|
在 C++ 模板类体中将类名仍视为模板
用 Clang++ 编译下面的源代码 (已测试 ArchLinux clang 3.2-3) template <template <class> class T>
class A {};
template <typename T>
class B {
A<B> member;
};
int main()
{
B<int> b;
return 0;
}
会得到如下错误信息 error: template argument for template template parameter must be a class template
A<B> member;
^
也就是说, clang++ 会认为出现在模板类 B 的类体中的符号 B 是一个已经实例化过的类型, 不能够被传递给模板类 A 用于实例化. 而 g++ 4.7 可以正确编译通过, 说明 g++ 肯定内置了某种脑补机制, 能灵活处理这样的情况, 它甚至可以编译如下分裂的代码 template <template <class> class T>
class A {};
template <class T>
class C {};
template <typename T>
class B {
A<B> member;
C<B> another;
};
int main()
{
B<int> b;
return 0;
}
当然在 clang++ 下也不是没办法解决了, 方案是, 在类体中如果要将类名当作模板来使用, 则在名字前加上名字空间声明. 如上面 B 定义在全局名字空间中, 所以代码应该这样修改 template <template <class> class T>
class A {};
template <typename T>
class B {
A< ::B> member;
};
int main()
{
B<int> b;
return 0;
}
话说小于号跟双冒号之间有个空格 < ::, 这绝不是我手残了抖上去的, 而是这地方必须要一个空格. C++ 程序设计领域流行着各种都市传说, 其中有模板套模板结束时的两个大于号之间要加个空格什么的, 类似, 小于号跟冒号之间也要加个空格, 否则 <: 会被认为是 [. 相应地, 如果 B 定义于某个有名字的名字空间 (这话说得...) 中那么上面代码应作相应修改 template <template <class> class T>
class A {};
namespace ns {
template <typename T>
class B {
A<ns::B> member;
};
}
int main()
{
ns::B<int> b;
return 0;
}
Posted at Jan 14 2013 - 03:26:03
Permanent Link:
/p/503
Load full text
|
Post tags:
C++
Template
|
|
模板之工 - Mako 上手篇
简介Mako 是一个 Python 模板程序. 用于给定一个字符串, 或给定一个文件, 使用 Python 对象值动态地替换其中的一部分内容. 可是使用 pip 或 easy_install 安装 Mako 库. # pip install Mako
# easy_install Mako
使用基本文本替换安装完成后, 在交互环境中可以通过下面的代码来测试 Mako >>> import mako.template
>>> print mako.template.Template('Hello, ${ what }!').render(what='Mako')
Hello, Mako!
上述代码中, 引入 Mako 模板模块, 并使用模板对字符串 Hello, ${ what }! 中的动态内容进行替换. 动态内容是形如 ${ what } 这样的 Mako 标记, 它表示将传递给 render 函数的字典中, what 对应的项的值替换这个标记. 因此上面的 render 结果便是 Hello, Mako!. 替换文件中的动态内容更多的应用场景是将需要生成的内容写成一个文件模板 (如 HTML 页面), 读取这个页面并生成结果内容. 在当前目录下创建 hello-mako.html 文件, 内容如下 <html>
<body>
Dear ${ username }, welcome back!
并使用如下的 Python 代码 import mako.template
templ = mako.template.Template(filename='hello-mako.html')
print templ.render(username='Mako')
就能看到输出的结果 HTML 代码了. 使用中文及指定编码上面的页面模板代码中如果包含中文或其它非 ASCII 字符, 如 <html>
<body>
你好, ${ username }, 欢迎回来!
那么这一段程序在构造 mako.template.Template 对象时多半会挂掉. 要为 Mako 模板指定输入编码方式才行 import mako.template
templ = mako.template.Template(filename='hello-mako.html', input_encoding='utf-8')
print templ.render(username=u'柑奈')
分支接下来, 如果这个用户是个管理员用户, 那么希望为这个用户呈现一个后台管理的入口 (当然其它用户就没这个福利了), 那么可以用 Mako 提供的分支来实现 你好, ${ username }, 欢迎回来!
%if is_admin:
<a href='/admin'>管理页面</a>
%endif
并使用如下语句分别测试 templ = mako.template.Template(filename='hello-mako.html', input_encoding='utf-8')
print templ.render(username=u'柑奈', is_admin=False)
print templ.render(username=u'柑奈', is_admin=True)
%if %endif 之间表示一段分支. 如果确实需要书写一个百分号, 而不是作为 Mako 的指令符号, 那么此处须连续两个百分号 %% 来转义, 通常页面上似乎也不会出现那么多百分号, 所以这个应该还是可以接受的吧. 关于分支, 更详细的例子是 %if condition_a:
do_a
%elif condition_b:
do_b
%else:
do_c
%endif
对象式引用
Posted at Jul 30 2012 - 03:37:19
Permanent Link:
/p/491
Load full text
|
Post tags:
Python
Tutorial
Template
Mako
|
|
万能巧械 - 二叉检索树 [壹]
二叉检索树的查询与检索操作看这里 从二叉检索树中删除一个元素分多个步骤: 找到节点与查询操作非常类似, 只不过, 正如插入元素过程中需要将路径上所有节点负载加上 1, 删除过程中, 也需要将节点路径上所有节点负载都减去 1. 下面是这一部分的实现 void remove_by(key_type const& key)
{
remove_by_from(key, &root);
}
void remove_at(int position)
{
remove_at_from(position, &root);
}
static void remove_by_from(key_type const& key, node** parent)
{
--((*parent)->load);
if (key < (*parent)->t.key()) {
remove_by_from(key, &((*parent)->left));
return;
}
if ((*parent)->t.key() < key) {
remove_by_from(key, &((*parent)->right));
return;
}
remove(parent);
}
static void remove_at_from(int position, node** parent)
{
--((*parent)->load);
int left_load = (NULL == (*parent)->left) ? 0 : (*parent)->left->load;
if (position < left_load) {
remove_at_from(position, &((*parent)->left));
return;
}
if (left_load < position) {
position = position - left_load - 1;
remove_at_from(position, &((*parent)->right));
return;
}
remove(parent);
}
static void remove(node** n);
这些函数都是 class binary_search_tree 旗下的. 与插入操作类似地, 这里需要的同样是节点的二级指针, 因为当节点从树中被移除时, 必然伴随着对其父节点对应的子树指针修改. 找到了节点之后将会有下面 3 种情况 前两种情况好办, 找到为空的一侧子树, 将另一侧子树接到父节点上, 然后删除当前节点即可. 也就是说当前已经处在容易删除的位置, 可以跳过一个中间步骤. (P 表示待删除节点的父节点)
Posted at Jan 24 2012 - 05:42:01
Permanent Link:
/p/481
Load full text
|
Post tags:
Algorithm
Generic Programming
Order Statistic
B-tree
Data Structure
Template
C++
Binary Search Tree
|
|
万能巧械 - 二叉检索树 [零]
堆在维护固定的顺序统计量有先天优势, 但在面对如下需求的时候又极其手短 - 按键索引 - 给定一个元素的键, 在数据集合中找到与该键相同 (或较小, 较大) 的元素
- 随机索引 - 在堆建立时, 可以给定一个固定的数值 K, 让堆维护第 K 大的元素, 但毕竟这个 K 是建堆时固定的
- 多键索引 - 堆中的元素的排序索引是唯一的, 如果想要其它的索引, 则需要借助额外的数据结构
前两个手短指的是时间复杂度, 要完成这些功能, 跟直接到未排序数组里面去暴力解决是一回事. 而后面一个则是堆的硬伤. 严格来说, 堆并不是一种数据 结构, 说穿了堆只有数据而没有结构 (是的, 即使是数组也是数据结构, 因此严格来讲应该说成, 它没有自身独特的结构, 还记得 STL 中优先队列的模板定义吧, 它的底层存储结构是可以通过模板参数替换的), 其精髓在于算法. 由于不具备结构, 也就是说没有实质上的数据与数据的关系, 因而不方便弄出多个不同的键. 这个现在空谈就像白切鸡一样没什么味道, 以后有机会再加上油盐详述. 较之堆更加全能的索引数据结构非 二叉检索树 (binary search tree, 缩写为 BST) 莫属了, 一般的二叉检索树可以很轻松地解决按键索引, 而若将子树节点计数器加诸其上, 就能进行快速的随机索引. 不过, 在这篇文章中, 只讨论理想状态下的二叉树, 不考虑那种被精心准备的数据叉成链表的情况. 首先还是把二叉树的架子给搭出来 template <typename T>
class binary_search_tree {
struct node {
T t;
node* left;
node* right;
int load;
explicit node(T const& rhs)
: t(rhs)
, left(NULL)
, right(NULL)
, load(1)
{}
};
node* root;
typedef typename T::key_type key_type;
public:
binary_search_tree()
: root(NULL)
{}
public:
void insert(T const& e);
void remove_by(typename T::key_type const& key);
void remove_at(int position);
T& element_by(typename T::key_type const& key);
T& element_at(int position);
};
Posted at Jan 23 2012 - 05:04:23
Permanent Link:
/p/479
Load full text
|
Post tags:
C++
Generic Programming
Data Structure
Binary Search Tree
Algorithm
Order Statistic
Template
|
|
GAE 速成简易博客 - 开张
前期准备目前 GAE 官方推荐的 Python 版本是 2.7 (终于脱离了 2.5 的泥潭啊), 实际上 2.6.x 版本也是没问题的 (写个 CMS 这种简易的设备, 应该还用不到太多高端的语言特性). GAE 当然也是必不可少的. 下载和安装步骤在 Google Code 上都有 详细文档. 如果使用 ArchLinux, 还可以通过 AUR 安装. 这里就不废话了. 找个地方, 建立一个目录, 比如叫做 cms-build, 切到这个目录作为工作目录. 下面开始. 数据结构既然是写博客, 那么最关键的当然要是文章 (post) 了. 先来建立用于定义数据的源文件 model.py from google.appengine.ext import db
class Post(db.Model):
title = db.StringProperty(multiline=False)
content = db.TextProperty()
每篇文章的基本属性有标题 title, 内容 content 和创建时间 date. 其中标题不允许多行; 而内容使用 db.TextProperty 类型而不是 db.StringProperty (根据 GAE 文档, StringProperty 只能存至多 500 字符). 首页模板 首先, 将首页给弄出来, 建立目录 templates, 并在这个目录下弄一个 index.html 文件, 内容是 <html>
<head><title>My Blog</title></head>
<body>
{% for post in posts %}
<h1>{{ post.title }}</h1>
<p>{{ post.content }}</p>
{% endfor %}
在 GAE 中, HTML 模板文件使用的是 django 的模板语法. 上面文件中, {% for ... %} 到 {% endfor %} 是对传入模板的参数 posts 的迭代. {{ post.title }} 则是对 post 对象的 title 的引用, 而 {{ post.content }} 则是引用 content. 简而言之 {% xxx %} 是模板中的控制语句, 而 {{ xxx }} 则是引用值. 在 django 官方网站可以看到 详细文档, 鄙博客之前也对 django 有过 简介. 这个首页是简单了点, 不过呢, 先看看样子. 视图源文件 光有 HTML 模板还不行, 至少, Python 源代码才是核心. 现在添加一个 Python 源文件 index.py
Posted at Jan 19 2012 - 03:30:27
Permanent Link:
/p/476
Load full text
|
Post tags:
Tutorial
Web Server
Template
Python
Google AppEngine
|
|
日常的数据结构 - 堆的实现与第 K 最小堆
在 前一篇文章中纸上谈了堆的性质以及如何在插入元素和弹出最值时保持这些性质. 这篇文章将聊聊实现方式. 从实现的角度来说, 使用完全二叉树作为堆的前提的好处是, 完全二叉树非常容易实现, 甚至可以说是最容易实现的二叉树. 由于完全二叉树的节点编号是连续的, 那么它可以被拉平, 放进一个日常的数组中, 如 +---+
| 4 |
+---+
/ \
+---+ +---+
| 5 | | 9 |
+---+ +---+
/ \
+---+ +---+
| 8 | | 5 |
+---+ +---+
这样一棵完全二叉树可以被转换成 .----.
/--. \
+---+---+---+---+---+---+-----
| - | 4 | 5 | 9 | 8 | 5 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
其中的线连接节点与它们的子节点. 如果用节点的编号来标识这个数组, 则会是 .----.
/--. \
+---+---+---+---+---+---+-----
| 0 | 1 | 2 | 3 | 4 | 5 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
这里有个很奇妙的性质, 索引为 i 的节点, 它的左子节点的索引是 2i, 而右子节点的索引是 2i+1, 其父节点索引则是 floor(i/2) (根节点除外). 如果用 0 号节点而不是 1 号节点存储根节点呢? 如 .----.
/--. \
+---+---+---+---+---+---+-----
| - | 0 | 1 | 2 | 3 | 4 | ...
+---+---+---+---+---+---+-----
\______/ /
\________/
也能很容易计算, 索引为 i 的节点, 左子节点索引是 2i+1, 右子节点索引是 2i+2, 父节点索引是 floor((i-1)/2). 似乎也没什么太大区别. 不过, 之前那种计算方式的好处在于, 2i, 2i+1, i/2 这样的算式都能换成极快的位运算: 2i 等效于 i << 1, 2i+1 等效于 (i << 1) | 1, floor(i/2) 等效于 i >> 1, 这还能提供一丁点效率优化 (和一部分代码混乱程度加成, 以及大量的极客自豪感上升). 既然堆的逻辑结构是数组, 那么可以采用 std::vector 作为存储数据结构. 此外, 将比较方式以模板形式抽出, 这样可以构造一个抽象的最值堆, 而不是死板的最大堆或者最小堆. 下面是堆的框架 template <typename _T, typename _Less>
class heap {
std::vector<_T> array;
_Less const less;
typedef typename std::vector<_T>::size_type size_type;
public:
heap()
: array(1) /* insert a placeholder, array[0] */
, less(_Less())
{}
void push(_T const& value);
_T pop();
};
Posted at Oct 07 2011 - 09:23:13
Permanent Link:
/p/441
Load full text
|
Post tags:
C++
Algorithm
Template
Heap
Order Statistic
Generic Programming
Data Structure
|
|
日常的算法 - 顺序统计
顺序统计指的是在一坨 并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 C++ 面向迭代器的程序设计描述, 不考虑集合为空的情形. 以后的例子相同) template <typename _Iterator>
_Iterator find_min(_Iterator begin, _Iterator end)
{
_Iterator min = begin;
for (++begin; begin != end; ++begin) {
if (*begin < *min) {
min = begin;
}
}
return min;
}
将这两件事情揉合在一起, 即从一个集合中同时找到最小值和最大值, 相比于分头寻找, 能够节省不少时间, 原因不仅仅是两次循环合并成一次循环, 运用一些技巧能显著地减少比较的次数. 在每一次取出剩余元素时, 同时取出两个, 先将这两个比较大小, 然后将较小的元素与当前最小值比较, 而将较大的值与当前最大值比较取出 +-------+-----------+-----
| begin | begin + 1 | ...
+-------+-----------+-----
| |
+--( < )--+
/ \
/ \
+----------+ +-------------+ +-----+
| less one | | greater one |--( < )--| max |
+----------+ +-------------+ +-----+
|
| +-----+
+-------------------------( < )--| min |
+-----+
这样每寻访 2 个元素, 需要 3 次元素比较, 加上判断循环是否结束需要 1 次比较, 而分开查找, 则每 1 个元素需要 2 次元素比较, 加上 1 次循环判断结束的比较. 之所以这么计较比较的次数, 因为目前计算机体系结构和分支语句非常不友好, 太多分支 (意味着大量的预测失败) 的程序会因为无法充分利用流水线而显著地降低实际执行效率. 下面是实现的例子
Posted at Sep 30 2011 - 09:20:03
Permanent Link:
/p/426
Load full text
|
Post tags:
Generic Programming
STL
C++
Order Statistic
Algorithm
Template
|
|
头文件禁区: C++ 中的 ABI
在 上一篇文章中写到了 C 的 ABI ( application binary interface) 有关的内容. 而 C++ 这货也采用 header / cpp 分离的方式来组织代码, 并在编译时将头文件直接在 cpp 中插入, 这种暴力方法已经不能简单说是为了兼容 C 的各种编译期行为, 完全就是彻头彻尾地重蹈覆辙, 甚至有过之而无不及. 首先, C++ 也会遇到 "如果直接用了动态库中修改过签名的函数怎么办" 这个全静态语言的千古难题. 而且比起 C 语言更要命的是, C++ 的类是不能进行前置声明来回避对象内存布局耦合: 前置声明就没有引用成员函数了, 那还怎么面向坑爹的对象呢? 不仅仅对象成员布局有此问题, 连同 C++ 藉由实现多态的虚函数亦面临着同样的窘境. 试想动态库中虚函数表都改得面目全非时, 使用该对象的代码却还用原来的方式访问, 那还不是各种鸡飞狗跳. 对于如此恶劣环境下仍然想保持 ABI 兼容性的 C++ 程序员来说, 倒也不是完全无路可走. 具体的方案就不在这篇文章中赘述了, 请转到 陈硕老师的 C++ 工程实践: 二进制兼容性和 C++ 工程实践: 避免使用虚函数作为库的接口. 两篇文章都写得非常详细. 撇开这些跟 C 语言有关的孽缘不谈, C++ 本身也提供了一些机制来帮助程序员养成编码恶习, 比如一些函数实现可以直接写进头文件中, 而无须担忧任何链接错误. 首当这个批评的就是成员函数, 包括静态或非静态, 虚或非虚. inline 函数或者 template 函数实现要写头文件这点可以理解可以忍, 但成员函数来凑什么热闹? 成员函数的不往头文件里面写, 可以避免一些 ABI 耦合, 比如 class Date {
int month;
int day;
public:
int getDay() const;
int getMonth() const;
};
这种情况下, 在使用 Date* date /* initialize */;
date->getDay();
不必担心内存布局耦合, 因为作为非虚的成员函数, Date::getDay() const 这样的函数签名正如 getday(Date const*) 一样, 这就回到了上一篇文章最后提到的解决方法了. 但是如果用得不恰当, 比如头脑发热认为 inline 一下能提高效率什么的, 而活生生地写成 class Date {
int month;
int day;
public:
inline int getDay() const
{
return day;
}
inline int getMonth() const
{
return month;
}
};
Posted at Aug 31 2011 - 06:52:02
Permanent Link:
/p/404
Load full text
|
Post tags:
C++
Template
ABI
STL
inline
|
|
Page 0
1
|
