browser icon
You are using an insecure version of your web browser. Please update your browser!
Using an outdated browser makes your computer unsafe. For a safer, faster, more enjoyable user experience, please update your browser today or try a newer browser.

轻量级泛型

Posted by on 2011 年 01 月 19 日

你可以任意转载本文,但请在转载后的文章中注明作者和原始链接。
媒体约稿请联系 titilima_AT_163.com(把“_AT_”换成“@”)。

我必须承认,一直以来我对模板和泛型有着相当的敌意。从客观上来讲,我先前的工作环境(移动设备)限制了模板的使用;从主观上来讲,我又很厌恶多次实例化后的模板所带来的庞大代码体积。于是乎,我尽量避免在我的私人代码中使用模板。
但是,我仍然需要容器类,而且我希望这些容器类是可复用的,也就是能够容纳不同类型的元素。一个偶然的机会,我从 CRT 中的 qsort 函数中得到灵感,使用 void* 这个万能的无类型指针完成了我要的容器。这些类后来被我收入到了 PDL 之中,你可以在这里这里找到它们的实现。
以 LPtrVector 类为例,它的创建代码为:

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
BOOL LPtrVector::Create(
    __in DWORD dwUnitSize,
    __in DWORD dwMaxCnt,
    __in int nGrowCnt /* = -1 */,
    __in CopyPtr pfnCopy /* = NULL */,
    __in DestructPtr pfnDestroy /* = NULL */,
    __in ILock* lock /* = NULL */)
{
    if (NULL != m_data)
        Destroy();
 
    m_dwUnitSize = dwUnitSize;
    m_dwUnitCnt = 0;
    m_dwMaxCnt = (dwMaxCnt > 0) ? dwMaxCnt : VECTOR_DEFMAXCNT;
    m_nGrowCnt = nGrowCnt;
    m_pfnCopy = pfnCopy;
    m_pfnDestroy = pfnDestroy;
    if (NULL != lock)
        m_lock = lock;
    else
        m_lock = LDummyLock::Get();
 
    m_data = new BYTE[dwUnitSize * m_dwMaxCnt];
    return NULL != m_data;
}

其中 dwUnitSize 标识了每个元素的大小,m_data 是存储所有元素的数据区,它的总大小为 (dwUnitSize * 预分配的元素个数)。pfnCopy 和 pfnDestroy 为两个回调函数,它们分别作为构造器与析构器,用于处理非 POD 元素的深拷贝行为。以 LPtrVector 数据的写入为例:

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
BOOL LPtrVector::SetAt(__in int idx, __in LPCVOID pvData)
{
    if (NULL == m_data || idx >= (int)m_dwUnitCnt)
        return FALSE;
    if (idx > 0 && (idx >= (int)m_dwUnitCnt || 0 == m_dwUnitCnt))
        return FALSE;
 
    BOOL bAdd = FALSE;
    LAutoLock lock(m_lock);
    if (idx < 0)
    {
        bAdd = TRUE;
        idx = m_dwUnitCnt;
        if (m_dwUnitCnt == m_dwMaxCnt)
            Grow();
    }
 
    PVOID p = DataFromPos(idx);
    if (NULL != m_pfnDestroy && !bAdd)
        m_pfnDestroy(p);
 
    CopyMemory(p, pvData, m_dwUnitSize);
    if (NULL != m_pfnCopy)
        m_pfnCopy(p, pvData);
 
    if (bAdd)
        ++m_dwUnitCnt;
    return TRUE;
}

在第 19 行的写入数据之前,会调用 pfnDestroy 对先前已有的数据进行销毁操作,然后复制新的数据,再对新的数据执行复制操作。
也就是说,对于调用者而言,为了使用 LPtrVector 这个类,需要把代码写成如下的样子:

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
struct ArrayElement {
    int n;
    char* str;
    static void Copy(void* dst, const void* src)
    {
        ArrayElement* d = (ArrayElement*)dst;
        ArrayElement* s = (ArrayElement*)src;
        d->str = _strdup(s->str);
    }
    static void Destroy(void* ptr)
    {
        ArrayElement* p = (ArrayElement*)ptr;
        free(p->str);
    }
};
 
LPtrVector v;
v.Create(sizeof(ArrayElement), 16, 16, ArrayElement::Copy,
    ArrayElement::Destroy);
 
// ...
ArrayElement e;
e.n = 10;
e.str = "Hello, World!";
v.SetAt(0, &e);

对于 ArrayElement 来说,遵循 Copy 和 Destroy 这种二段构造/析构的编程范式实在有失优雅,甚至可以算是丑陋(让我想起了 Symbian 的编程范式)。不过,它的好处也是显而易见的——LPtrVector 并不会产生多个实例的二进制代码。鱼与熊掌,按需取舍尔。

其实,如果代码中加入一点点模板,这个世界还是会变得更美的。下面的代码来自于某个尚未公开的 framework:

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
#include <new> // for placement new
 
template <typename T>
class UtTypeTraits
{
public:
    static void UTAPI fnCopy(void* dst, const T* src)
    {
        new(dst) T(*src);
    }
    static void UTAPI fnDestroy(T* obj)
    {
        obj->~T();
    }
};
 
template <typename T>
class UtArray
{
public:
    UtArray(size_t initcount = 16, size_t growcount = 16)
    {
        m_data = ut_array_create(sizeof(T), initcount, growcount,
            (ut_fncopy)UtTypeTraits<T>::fnCopy,
            (ut_fndestroy)UtTypeTraits<T>::fnDestroy);
    }
    ~UtArray(void)
    {
        ut_array_destroy(m_data);
    }
    // ...
private:
    ut_array m_data;
};

简单说明一下:

  • ut_array 是一个类似于 LPtrVector 的数据结构,同样以 unitsize、fnCopy 和 fnDestroy 的形式实现了一个基于无类型指针的容器。所不同的是,它是用 C API 的方式进行操作的。
  • UtArray 是一个类模板,它对 ut_array 的操作进行了封装,提供了诸如 operator[] 此类的便捷操作。这个类借助于 UtTypeTraits、placement new 与显式调用析构函数的方式将二段构造/析构隐藏掉了。
  • 这里之所以要用一个 UtTypeTraits 类来包含二段构造器与析构器,是因为如果直接将构造器和析构器写成全局的函数模板的话,在 VC6 下会收到一个 C2469 的编译错误。

如果使用了 UtArray,那么调用者的使用代码就可以简化成:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct ArrayElement {
    ArrayElement(void)
    {
        n = 10;
        str = _strdup("Hello, World!");
    }
    ArrayElement(const ArrayElement& obj)
    {
        n = obj.n;
        str = _strdup(obj.str);
    }
    ~ArrayElement(void)
    {
        free(str);
    }
    int n;
    char* str;
};
 
UtArray<ArrayElement> a;
ArrayElement e;
a.SetAt(0, e);

另外,由于 UtArray 只是对 ut_array API 进行了一层薄薄的封装,所以在编译器的优化下,并不会产生多份同样逻辑的二进制代码实例。此可谓“轻量级泛型”,乃我所欲也。

———- 传说中的分隔线 ———-

Q:既然你已经有了 UtArray 的解决方案,为什么不改写 LPtrVector 这些类?
A:因为 PDL 的作者是个 lib 控,他仍然希望把容器的实现代码隐藏在 cpp 里。

订阅本站

11 Comments

  • At 2013.05.13 17:29, FF said:

    好的,多谢!

    (Required)
    (Required, will not be published)