Нет подходящего конструктора по умолчанию
Это учебный проект, поэтому, пожалуйста, дайте любые дополнительные советы, которые приходят на ум.
Я пытаюсь изучить структуры данных путем повторной реализации некоторых контейнеров / алгоритмов STL, и я начал со связанных списков. Если я попытаюсь составить список класса без конструктора по умолчанию, я получу ошибку компилятора "нет подходящего конструктора по умолчанию":
#include "list.h"
#include <list>
class testA
{
private:
int mInt;
public:
testA(int i) : mInt(i) {}
};
int _tmain(int argc, _TCHAR* argv[])
{
std::list<testA> wS; // Fine
wS.push_back(1); // Fine
MTL::list<testA> wM; // 'testA' has no appropriate default constructor
wM.push_back(1);
return 0;
}
Проблема в том, что я использую фиктивный узел в списке, чтобы сохранить ссылку на начало и конец списка. Я использую это главным образом для того, чтобы функция.end() работала должным образом и передавала итератор с возможностью декремента до конца списка. Когда я объявляю пустой список, одна из функций хочет конструктор по умолчанию для шаблонного типа, чтобы он мог сделать мой фиктивный узел! Если конструктор по умолчанию не существует, выдается сообщение об ошибке.
С другой стороны, похоже, что пара реализаций STL на самом деле использует идею фиктивного головного узла. С другой стороны, похоже, что они решают некоторые неприятные уловки, чтобы обойти эту проблему. Моя реализация STL в Visual Studio 2010 в конечном итоге вызывает необработанный оператор new и delete без вызова конструктора. Я в основном скопировал то, что у него есть (ищите::operator new и delete), и я получаю его для компиляции. Вот полный код:
#include <cassert>
#include <iostream>
namespace MTL
{
template< typename T >
class list
{
private:
// If ListNode is in the private part of list, clients
// can't mess around with ListNodes.
template <typename T>
class ListNode
{
private:
ListNode<T>* p_mNextNode;
ListNode<T>* p_mPreviousNode;
T mNodeVal;
public:
// ListNode() :
// p_mNextNode(0),
// p_mPreviousNode(0) {}
ListNode(T const & aVal) :
p_mNextNode(0),
p_mPreviousNode(0),
mNodeVal(aVal) {}
ListNode<T>* GetNextNode() {return p_mNextNode;}
ListNode<T>* GetPreviousNode() {return p_mPreviousNode;}
void SetNextNode(ListNode<T>* const aNode) {p_mNextNode = aNode;}
void SetPreviousNode(ListNode<T>* const aNode) {p_mPreviousNode = aNode;}
T& GetNodeVal() {return mNodeVal;}
};
public:
class iterator
{
private:
ListNode<T>* mIteratorNode;
public:
iterator() : mIteratorNode(0) {}
iterator(ListNode<T>* aListNode) {mIteratorNode = aListNode;}
T& operator*() {return mIteratorNode->GetNodeVal();}
iterator& operator++() {mIteratorNode = mIteratorNode->GetNextNode(); return *this;}
iterator& operator--() {mIteratorNode = mIteratorNode->GetPreviousNode(); return *this;}
bool operator==(iterator const& aIterator) {return mIteratorNode==aIterator.mIteratorNode;}
bool operator!=(iterator const& aIterator) {return !(mIteratorNode==aIterator.mIteratorNode);}
ListNode<T>* GetNode() {return mIteratorNode;}
ListNode<T>* GetNextNode() {return mIteratorNode->GetNextNode();}
ListNode<T>* GetPreviousNode() {return mIteratorNode->GetPreviousNode();}
};
private:
ListNode<T>* p_mHeadNode;
void insert(ListNode<T>* const aNewNode, iterator& aIterator)
{
ListNode<T>* currentNode = aIterator.GetNode();
ListNode<T>* currentsPreviousNode = currentNode->GetPreviousNode();
currentsPreviousNode->SetNextNode(aNewNode);
aNewNode->SetPreviousNode(currentsPreviousNode);
aNewNode->SetNextNode(currentNode);
currentNode->SetPreviousNode(aNewNode);
}
void eraseNode(ListNode<T>* aListNode)
{
ListNode<T>* previousNode = aListNode->GetPreviousNode();
ListNode<T>* nextNode = aListNode->GetNextNode();
previousNode->SetNextNode(aListNode->GetNextNode());
nextNode->SetPreviousNode(aListNode->GetPreviousNode());
if (p_mHeadNode != aListNode)
{
delete aListNode;
}
}
protected:
public:
list() : p_mHeadNode(static_cast<ListNode<T>*>(::operator new (sizeof(ListNode<T>))))
{
// To get .begin or .end to work immediately after construction
p_mHeadNode->SetNextNode(p_mHeadNode);
p_mHeadNode->SetPreviousNode(p_mHeadNode);
}
list(list const& aList) : p_mHeadNode(static_cast<ListNode<T>*>(::operator new (sizeof(ListNode<T>))))
{
p_mHeadNode->SetNextNode(p_mHeadNode);
p_mHeadNode->SetPreviousNode(p_mHeadNode);
ListNode<T>* pCurrent = (aList.p_mHeadNode)->GetNextNode();
while (pCurrent != aList.p_mHeadNode)
{
this->push_back(pCurrent);
pCurrent = pCurrent->GetNextNode();
}
}
void push_front(T const& aNewVal)
{
ListNode<T>* newNode = new ListNode<T>(aNewVal);
this->insert(newNode,this->begin());
}
void push_back(T const& aNewVal)
{
ListNode<T>* newNode = new ListNode<T>(aNewVal);
this->insert(newNode,this->end());
}
void push_back(ListNode<T>* const aListNode)
{
this->push_back(aListNode->GetNodeVal());
}
void push_front(ListNode<T>* const aListNode)
{
this->push_front(aListNode->GetNodeVal());
}
T& front(){ return p_mHeadNode->GetNextNode()->GetNodeVal(); }
T& back(){ return p_mHeadNode->GetPreviousNode()->GetNodeVal(); }
void pop_front() {this->eraseNode(p_mHeadNode->GetNextNode());}
void pop_back() {this->eraseNode(p_mHeadNode->GetPreviousNode());}
const T& front() const { return (p_mHeadNode->GetNextNode())->GetNodeVal(); }
const T& back() const { return (p_mHeadNode->GetPreviousNode())->GetNodeVal(); }
iterator begin() {return iterator(p_mHeadNode->GetNextNode());}
iterator end() {return iterator(p_mHeadNode);}
iterator insert(iterator aPosition, const T& aVal)
{
assert(0);
return iterator();
}
iterator insert(iterator aPosition, unsigned int n, const T& aVal)
{
ListNode<T>* newNode = 0;
for (unsigned int i = 0; i < n; ++i)
{
newNode = new ListNode<T>(aVal);
this->insert(newNode,aPosition);
++aPosition;
}
return iterator(newNode->GetNextNode());
}
iterator insert(iterator aPosition, iterator aFirst, iterator aLast)
{
assert(0);
return iterator();
}
unsigned int size()
{
unsigned int counter = 0;
ListNode<T>* pCurrent = p_mHeadNode->GetNextNode();
while (pCurrent != p_mHeadNode)
{
++counter;
pCurrent = pCurrent->GetNextNode();
}
return counter;
}
~list()
{
this->clear();
::operator delete(p_mHeadNode);
}
void clear()
{
ListNode<T>* pCurrent = p_mHeadNode->GetNextNode();
ListNode<T>* pNext = pCurrent->GetNextNode();
while (pNext != p_mHeadNode)
{
this->eraseNode(pCurrent);
pCurrent = pNext;
pNext = pCurrent->GetNextNode();
}
// All but the last has been deleted
this->eraseNode(pCurrent);
}
bool empty() {return (p_mHeadNode->GetNextNode() != p_mHeadNode);}
friend std::ostream& operator<<(std::ostream& os, list<T> const& aList)
{
ListNode<T>* pCurrent = (aList.p_mHeadNode)->GetNextNode();
std::cout << "List Contents are:\n";
std::cout << "{";
while (pCurrent != aList.p_mHeadNode)
{
std::cout << pCurrent->GetNodeVal();
pCurrent = pCurrent->GetNextNode();
if (pCurrent != aList.p_mHeadNode)
{
std::cout << ",";
}
}
std::cout << "}\n";
return os;
}
};
};
Конечно, должен быть более чистый способ заставить это работать. Я не могу разделить свой ListNode на базовый класс только из предыдущих и следующих указателей и производный класс содержащихся данных, потому что GetNodeVal() нуждается в типе возврата шаблонного значения. Итак, еще раз, мне нужен по крайней мере соответствующий конструктор, чтобы получить фиктивное значение в базовом классе. Я не мог сделать это чисто виртуальным, потому что тогда мой фиктивный узел не может быть создан как базовый класс.
Это: http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-3.3/stl__list_8h-source.html версия использует статические приведения, которые кажутся менее неприятными, но я не смог их применить к моему коду.
Итак, как я могу заставить этот код работать без вызова необработанного оператора new/delete? И будет ли он чище?
1 ответ
Один вариант для отложенного / необязательного построения значения может быть:
template <typename T>
class ListNode
{
private:
ListNode<T>* p_mNextNode;
ListNode<T>* p_mPreviousNode;
union {
char dummy;
T mNodeVal;
};
ListNode() :
p_mNextNode(0),
p_mPreviousNode(0),
dummy() {}
ListNode(T const & aVal) :
p_mNextNode(0),
p_mPreviousNode(0),
mNodeVal(aVal) {}
...
};
Однако вам нужно будет явно вызвать его деструктор, поскольку компилятор больше не знает, какой из вариантов-членов активен.
Но лучше сделать это для манекена ListNode внутри List, Я думаю, что реализация с ::operator new был также специальный корпус манекена. Что-то вроде этого:
template< typename T >
class List
{
private:
class ListNode
{
private:
ListNode* p_mNextNode;
ListNode* p_mPreviousNode;
T mNodeVal;
};
class DummyListNode
{
public:
ListNode* p_mNextNode;
ListNode* p_mPreviousNode;
};
Это как "стандартная раскладка", так и по 9.2:
Если объединение стандартной компоновки содержит две или более структур стандартной компоновки, которые совместно используют общую начальную последовательность, и если объект объединения стандартной компоновки в настоящее время содержит одну из этих структур стандартной компоновки, разрешается проверять общую начальную часть любой из них.
Давайте воспользуемся этим сейчас:
union {
DummyListNode dummy_head_tail;
ListNode head_tail
};
// ... iterators and stuff, using &head_tail as the first and last ListNode*
public:
List() : dummy_head_tail{ nullptr, nullptr } { }
~List() { /* free all nodes, then */ dummy_head_tail->~DummyListNode(); }
};