c++ - No appropriate default constructor -
this learning project please give additional advice comes mind.
i trying learn data structures re-implementing stl containers/algorithms , i've started linked lists. if try make list of class lacking default constructor compiler error of "no appropriate default constructor":
#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; } the problem i'm using dummy node in list store link beginning , end of list. use .end() function work , give decrement-able iterator 1 past end of list. when declare empty list 1 of functions wants default constructor templated type can make dummy node! if no default constructor exists, gives error message.
on positive side, looks couple of stl implementations use dummy head node idea. on negative side, looks pull nasty tricks around issue. visual studio 2010 stl implementation calls raw operator new , delete without calling constructor. i've copied has (look ::operator new , delete) , compile. here full code:
#include <cassert> #include <iostream> namespace mtl { template< typename t > class list { private: // if listnode in private part of list, clients // can't mess around 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>)))) { // .begin or .end work 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; (unsigned int = 0; < 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(); } // 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; } }; }; surely, there must cleaner way work. can't seem split listnode base class of previous , next pointers , derived class of contained data because getnodeval() needs return type of templated value. again need @ least appropriate constructor dummy value in base class. not make pure virtual because dummy node can not instantiated base class.
this: http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-users-3.3/stl__list_8h-source.html version using static casts seem less nasty haven't been able apply code.
so, how can code work without calling raw operator new/deletes? , cleaner?
one option delayed/optional construction of value be:
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) {} ... }; you need explicitly call destructor, however, since compiler no longer knows of variant members active.
but it's better dummy listnode inside list. guess implementation ::operator new special-casing dummy. this:
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; }; these both "standard-layout", , 9.2:
if standard-layout union contains 2 or more standard-layout structs share common initial sequence, , if standard-layout union object contains 1 of these standard-layout structs, permitted inspect common initial part of of them.
let's take advantage of now:
union { dummylistnode dummy_head_tail; listnode head_tail }; // ... iterators , stuff, using &head_tail first , last listnode* public: list() : dummy_head_tail{ nullptr, nullptr } { } ~list() { /* free nodes, */ dummy_head_tail->~dummylistnode(); } };
Comments
Post a Comment