使用 C++创建通用类型 - 具有共享实现的模板

Question

作为一个例子，考虑一个简单的数据结构，比如链表。在 C 中，它可能看起来像：

struct Node
{
    struct Node *next;
    void *data;
};

void *getLastItem(struct Node*);
...

我希望拥有相同的结构和函数，但通过声明 data 字段的类型来进行更好的类型检查，该字段始终是指向某个内容的指针。使用示例：

Node<Thing*> list = getListOfThings();
Thing *t = list->data;
t = getLastItem(list);
...

但我不想像普通模板那样为每种类型的指针生成实现。换句话说，我想要一些更像 Java、ML 和其他语言的泛型或参数类型的东西。我刚刚尝试了下面的代码作为测试。非类型化的类似 C 的部分最终将进入实现文件，而模板和函数声明将位于头文件中。我假设它们会被优化掉，我会留下与 C 版本大致相同的机器代码，除了它会进行类型检查。

但我不太擅长 C++...有没有办法改进这一点，或者使用更惯用的 C++，也许是模板专业化？

#include <stdio.h>

struct NodeImpl
{
    NodeImpl *next;
    void *data;
};

void *getLastItemImpl(NodeImpl *list)
{
    printf("getLastItem, non-template implementation.\n");
    return 0;  // not implemented yet
}

template <typename T>
struct Node
{
    Node<T> *next;
    T data;
};

template <typename T>
T getLastItem(Node<T> *list)
{
    return (T)getLastItemImpl((NodeImpl*)list);
}

struct A { };
struct B { };

int main()
{
    Node<A*> *as = new Node<A*>;
    A *a = getLastItem(as);
    Node<B*> *bs = new Node<B*>;
    B *b = getLastItem(bs);

}

Answer 1

这正是 Boost.PointerContainer 所做的，检查它的实现。基本上，它的作用是实现 void* 的专门化，并将任何其他实现转发给它 static_cast 传入和传出参数。

Answer 2

struct Node
{
    struct Node *next;
    void *data;
};

void *getLastItem(struct Node*);
...

这对于 C 来说很常见，但对于 C++ 来说却不常见。在 C++ 中，它通常如下所示：

template<typename T>
struct Node
{
    struct Node *next;
    T data;
};

T& getLastItem(const Node&);
...

请注意重要的区别 - C 版本具有另一级间接性以便共享实现，而 C++ 版本不需要这样做。这意味着 C 版本还有另一个 n 动态内存分配，其中 n 是列表中的项目数。鉴于每次分配通常都需要获取全局锁，每次分配通常至少有 16 字节的开销，以及内存管理器给各方带来的所有开销，C++ 版本的优势并非微不足道，特别是当您包括诸如缓存局部性之类的考虑因素。

换句话说，对于 Node，C++ 版本存储一个 int，而 C 版本存储一个 int * 以及一个int 的动态分配。

当然，这并没有考虑到链表在 90% 的情况下都是一种可怕的数据结构。

如果你必须使用链表，并且如果你必须使用数据成员的动态分配，那么你的“用void*s替换指针”的想法也不无道理。但是，如果您可以访问 C++11 编译器（VS2010、最新的 GCC 版本等），则应该使用 T 来放置一个断言，表明您依赖于 T 作为指针类型。 >std::is_pointer 和 static_assert，并且您应该在接口方法中使用 static_cast 而不是 C 风格的强制转换。 C 风格的强制转换可以让某人执行 Node，它会编译，但在运行时会爆炸。

Answer 3

正如其他答案和评论所说，使用 std::forward_list 或另一个现有库。如果你拒绝，这更像是我会做的：

#include <stdio.h>

struct NodeImpl
{
    NodeImpl *next;
    void *data;
public:    
    // we have pointers, so fulfill the rule of three
    NodeImpl() : next(NULL), data(NULL) {}
    ~NodeImpl() {}
    NodeImpl& operator=(const NodeImpl& b) {next = b.next; data = b.data; return *this;}
    // This function now a member.  Also, I defined it.
    void* getLastItem()
    {
        if (next)
            return next->getLastItem();
        return data;
    }
    void* getData() {return data;}
    void setData(void* d) {data = d;}
};

// the template _inherits_ from the impl
template <typename T>
struct Node : public NodeImpl
{
    Node<T> operator=(const Node<T>& b) {NodeImpl::operator=(b);}
    // we "redefine" the members, but they're really just wrappers
    T* getLastItem()
    { return static_cast<T*>(NodeImpl::getLastItem());}

    T* getData() {return static_cast<T*>(NodeImpl::getData());}
    void setData(T* d) {NodeImpl::setData(static_cast<void*>(d));}

    //or, if you prefer directness...
    operator T*() {return static_cast<T*>(NodeImpl::getData());}
    Node<T> operator=(T* d) {NodeImpl::setData(static_cast<void*>(d));}  
};


struct A { };
struct B { };

int main()
{
    Node<A> as;  //why were these heap allocated?  The root can be on the stack
    A *a = as.getLastItem();
    Node<B> bs; //also, we want a each node to point to a B, not a B*
    B *b = bs.getLastItem();

    B* newB = new B;
    bs = newB;  //set the data member
    newB = bs;  //read the data member
}

http://ideone.com/xseYk
请记住，该对象并不真正封装 next 或数据，因此您必须自己管理所有这些。