Использование C ++ для создания универсального типа - шаблона с общей реализацией - PullRequest
Новая
       30

Использование C ++ для создания универсального типа - шаблона с общей реализацией

0 голосов
/ 20 сентября 2011

В качестве примера рассмотрим простую структуру данных, такую ​​как связанный список. В Си это может выглядеть так: 

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);

}

Ответы [ 3 ]

4 голосов
/ 20 сентября 2011

Это именно то, что делает Boost.PointerContainer, проверьте его реализацию. По сути, он реализует специализацию для void* и имеет любую другую реализацию, направленную на него static_cast, в которую входят и выводятся параметры.

3 голосов
/ 20 сентября 2011 
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 и т. Д.), Вы должны подтвердить, что вы зависите от T, являющегося типом указателя, используя std::is_pointer и static_assert, и вы должны использовать static_cast, а не приведения в стиле C в ваших методах интерфейса.Приведение в стиле C позволило бы кому-нибудь сделать Node<SomeTypeBiggerThanVoidPtr>, и оно скомпилировалось бы, но взорвалось во время выполнения.

1 голос
/ 20 сентября 2011

Как сказано в других ответах и ​​комментариях, используйте 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 Имейте в виду, что этот объект не инкапсулирует следующий или данные на самом деле, поэтому вам придется управлять всем этим самостоятельно.

...