2

例如，考虑一个简单的数据结构，如链表。在 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);

}
4

3 回答 3

4

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

于 2011-09-20T16:08:51.427 回答
3 
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<int>，C++ 版本存储一个int，而 C 版本存储一个int *，以及对int.

这当然忽略了链表在 90% 的情况下是一种可怕的数据结构。

如果你必须使用链表，并且如果你必须对数据成员使用动态分配，那么你的“用void*s替换指针”的想法不是没有道理的。但是，如果您可以访问 C++11 编译器（VS2010、最新的 GCC 版本等），您应该使用 and 插入一个断言，表明您依赖于指针T类型，并且您应该使用而不是 C-在您的界面方法中进行样式转换。C 风格的演员会让某人这样做，它会编译，但在运行时会爆炸。std::is_pointerstatic_assertstatic_castNode<SomeTypeBiggerThanVoidPtr>

于 2011-09-20T16:17:59.710 回答
1

正如其他答案和评论所说，使用 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 或 data，因此您必须自己管理所有这些。

于 2011-09-20T17:29:22.803 回答