Общий связанный список в C ++

Question

Я слишком долго боролся с довольно простым вопросом о том, как создать общий связанный список в c ++.Список должен содержать несколько типов структур, но каждый список будет содержать только один тип структуры.Проблема возникает, когда я хочу реализовать функцию getNode () [см. Ниже], потому что тогда я должен указать, какую из структур она должна вернуть.Я попытался заменить структуры классами, где функция getNode возвращает базовый класс, который унаследован всеми другими классами, но он все равно не работает, поскольку компилятор не позволяет функции getNode возвращать что-либо, крометогда базовый класс.

Итак, вот некоторый фрагмент кода:

typedef struct struct1 
{
    int param1;
(...)
} struct1;

typedef struct struct2 
{
    double param1;
(...)
} struct2;


typedef struct node
{
    struct1 data;
    node* link;
} node;

class LinkedList
{
public:
    node *first;
    int nbrOfNodes;
    LinkedList();
    void addNode(struct1);
    struct1 getNode();
    bool isEmpty();
};

LinkedList::LinkedList()
{
    first = NULL;
    nbrOfNodes = 0;
}

void LinkedList::addNode(struct1 newData)
{
    if (nbrOfNodes == 0)
    {
        first = new node;
        first->data = newData;
    }
    else
    {
        node *it = first;
        for (int i = 0; i < nbrOfNodes; i++)
        {
            it = it->link;
        }
        node *newNode = new node;
        newNode->data = newData;
        it->link = newNode;
    }
    nbrOfNodes++;
}

bool LinkedList::isEmpty()
{
    return !nbrOfNodes;
}

struct1 LinkedList::getNode()
{
    param1 returnData = first->data;
    node* deleteNode = first;
    nbrOfNodes--;
    if (nbrOfNodes)
        first = deleteNode->link;
    delete deleteNode;
    return returnData;
}

Итак, вопрос, заключенный в одно предложение, состоит в следующем: Как настроить вышеупомянутый класс связанного списка так, чтобыэто также может быть использовано для struct2, без необходимости создавать новый почти идентичный список класса для объектов struct2?Как я сказал выше, каждый экземпляр LinkedList будет иметь дело только с struct1 или struct2.Благодарен за подсказки или помощь

Answer 1

В C ++ уже есть общий список ссылок, std :: list . Это определенно будет более эффективным и должно быть достаточно для вашего использования.

Если вы все еще хотите создать свой собственный список общих ссылок Вам следует рассмотреть возможность использования templates и создать шаблонную реализацию списка ссылок.

В c, где шаблоны недоступны, узел данных сохраняется в виде указателя void*. Он использует тот факт, что указатель void может указывать на любой тип данных общего характера. Вы также можете рассмотреть этот подход.

Answer 2

Базовые шаблоны просты.

Просто объявите класс как шаблон с переменной шаблонного типа.
Теперь везде, где у вас есть тип объявления, который вы хотите использовать в качестве универсального, в классе замените явныйвведите имя с шаблонным именем переменной.

Например, в вашем коде вы хотите, чтобы struct1 было универсальным, поэтому мы заменили его на T :

template<class T>
class LinkedList { 
    public:     
    node *first;     
    int nbrOfNodes;     LinkedList();     
    void addNode(T);     
    T getNode();     
    bool isEmpty(); 

}; 

Answer 3

struct1 и struct2 имеют разный размер в байтах, поэтому sizeof (struct1)! = Sizeof (struct2). Возврат структуры из функции требует ее копирования, поэтому c ++ требует, чтобы вы указали правильный тип для нее, чтобы можно было скопировать правильное количество байтов. Чтобы начать исправлять эту проблему, вам нужно подумать на очень низком уровне:

struct GenericStruct {
   void *ptr;
   size_t size;
   type_info t;
};
struct1 extract_struct1(GenericStruct &s);
struct2 extract_struct2(GenericStruct &s)
  {
  if (s.size != sizeof(struct2)) throw -1;
  if (s.t != typeid(struct2)) throw -1;
  struct2 *s2 = (struct2*)s.ptr;
  return *s2;
  }
GenericStruct make_generic(const struct1 &ss)
 {
 GenericStruct s;
 s.ptr = (void*)&ss;
 s.size = sizeof(struct1);
 s.t = typeid(struct1);
 return s;
 }
 GenericStruct make_generic(const struct2 &ss);

реальная проблема заключается в том, что эти функции могут не работать во время выполнения, если размеры или типы не совпадают. Копирование очевидно также необходимо:

GenericStruct Copy(const GenericStruct &s);

После того, как эти базовые примитивы существуют, вы можете создать класс с конструктором копирования и оператором присваивания, который использует эти функции для реализации надлежащей поддержки универсальной структуры.

Answer 4

Источник STL будет частью кода для изучения.

Вы также можете попробовать https://github.com/simonask/ftl/blob/master/list.hpp

Оба используют шаблоны ,который следует понимать, чтобы иметь возможность создавать любые общие классы.