template <typename _Type>
class CNode
{
public:
_Type* m_pNext, m_pPrevious;
void Set(CNode<_Type>* pNext, CNode<_Type>* pPrevious, _Type Data);
const CNode<_Type>* operator ++()
{
*this = m_pNext;
return *this;
}
const CNode<_Type>* operator --()
{
*this = m_pPrevious;
return *this;
}
};
Data Structures
I'm working on my code base before I start coding my engine. At the moment I am working on a templated linked list system (CNode and TLinkedList). My question has to do with my CNode class. I have it set up so that the ++/-- operators set the this variable:
Is this a bad idea (or a bad programming technique?)
That shouldn't even compile.
And unless you are doing this to learn how to code it, just use std::list. You said it is for a code base for an engine, just use std::list.
edit: My mistake, it will compile, I thought you meant the pointer (didn't look at the code).
And unless you are doing this to learn how to code it, just use std::list. You said it is for a code base for an engine, just use std::list.
edit: My mistake, it will compile, I thought you meant the pointer (didn't look at the code).
Yag Ni!
and why not use std::list? the standard library is there to be used, highly efficent and implemented by experts. If you're not writing that list for academic purposes I really don't see any reason for it.
And you're not setting 'this' you're setting the object pointed to by 'this' basicly you're calling operator=( other) but something tells me you should ismply be reassigning a pointer or something.
and why not use std::list? the standard library is there to be used, highly efficent and implemented by experts. If you're not writing that list for academic purposes I really don't see any reason for it.
And you're not setting 'this' you're setting the object pointed to by 'this' basicly you're calling operator=( other) but something tells me you should ismply be reassigning a pointer or something.
Quote:Original post by Kibble
That shouldn't even compile.
And unless you are doing this to learn how to code it, just use std::list. You said it is for a code base for an engine, just use std::list.
Ok, it was compiling just fine and now after tinkering with things, its giving me errors on this. I'll fix it and just do pNode = pNode->m_pNext.
I don't work for a company at the moment, so everything I do is for learning. I use STL all the time and when I feel I've learned what I need from this engine, I'll start on my next engine and most likely use STL.
Quote:Original post by DigitalDelusion
Yag Ni!
The operator was actually needed. I was trying something new and the it was based around the ++operator. Obviously the idea has a flaw and I'll have to rework it.
Ok, now I'm getting an access violation when I'm cleaning up:
I can't seem to find where the error is. I've run the debugger and I'm not trying to delete a null pointer. Any help would be appreciated.
Thanks,
Programmer16
template <typename _Type> class CNode{public: CNode* m_pNext; CNode* m_pPrevious; _Type m_Data; CNode() { m_pNext = 0; m_pPrevious = 0; } void Set(CNode* pNext, CNode* pPrevious, _Type Data) { m_pNext = pNext; m_pPrevious = pPrevious; m_Data = Data; }};
template <typename _Type> class TLinkedList{ CNode<_Type>* m_pHead; CNode<_Type>* m_pTail; unsigned int m_nSize;public: TLinkedList(); ~TLinkedList(); void Add(_Type Data); void Remove(unsigned int nIndex); void ForEach(void (*lpfnForEach)(_Type Data)); _Type* At(unsigned int nIndex) const; unsigned int Size() const;};template <typename _Type>TLinkedList<_Type>::TLinkedList(){ m_pHead = 0; m_pTail = 0; m_nSize = 0;}template <typename _Type>TLinkedList<_Type>::~TLinkedList(){ CNode<_Type>* pNode = m_pHead; while(pNode != 0) { CNode<_Type>* pTemp = pNode; pNode = pNode->m_pNext; delete pTemp; <- GIVES ME AN ERROR HERE }}template <typename _Type>void TLinkedList<_Type>::Add(_Type Data){ if(!m_pHead) { m_pHead = new CNode<_Type>; m_pTail = new CNode<_Type>; m_pHead->Set(0, 0, Data); m_pHead->m_pNext = m_pTail; m_pTail = m_pHead; } else { CNode<_Type>* pTemp = new CNode<_Type>; pTemp->Set(0, m_pTail, Data); m_pTail->m_pNext = pTemp; m_pTail = pTemp; } ++m_nSize;}template <typename _Type>void TLinkedList<_Type>::Remove(unsigned int nIndex){ CNode<_Type>* pNode = m_pHead; while(pNode != 0) pNode = pNode->m_pNext; pNode->m_pPrevious->m_pNext = pNode->m_pNext; delete pNode; --m_nSize;}template <typename _Type>void TLinkedList<_Type>::ForEach(void (*lpfnForEach)(_Type Data)){ CNode<_Type>* pNode = m_pHead; while(pNode != 0) { (*lpfnForEach)(pNode->m_Data); pNode = pNode->m_pNext; }}template <typename _Type>_Type* TLinkedList<_Type>::At(unsigned int nIndex) const{ CNode<_Type>* pNode = m_pHead; for(;nIndex > 0; --nIndex) pNode = pNode->m_pNext; return &pNode->m_Data;}template <typename _Type>unsigned int TLinkedList<_Type>::Size() const{ return m_nSize;}
I can't seem to find where the error is. I've run the debugger and I'm not trying to delete a null pointer. Any help would be appreciated.
Thanks,
Programmer16
Wouldn't your code:
if(!m_pHead)
{
m_pHead = new CNode<_Type>;
m_pTail = new CNode<_Type>;
m_pHead->Set(0, 0, Data);
m_pHead->m_pNext = m_pTail;
m_pTail = m_pHead;
}
be better if you did:
if(!m_pHead)
{
m_pHead = new CNode<_Type>;
m_pHead->Set(0, 0, Data);
m_pTail = m_pHead;
}
That shouldn't change your problem but it seems cleaner... You should give the code that you use to test the bug too, it would help to understand what's going on...
if(!m_pHead)
{
m_pHead = new CNode<_Type>;
m_pTail = new CNode<_Type>;
m_pHead->Set(0, 0, Data);
m_pHead->m_pNext = m_pTail;
m_pTail = m_pHead;
}
be better if you did:
if(!m_pHead)
{
m_pHead = new CNode<_Type>;
m_pHead->Set(0, 0, Data);
m_pTail = m_pHead;
}
That shouldn't change your problem but it seems cleaner... You should give the code that you use to test the bug too, it would help to understand what's going on...
Your mistake is that you are confusing your Node class, which is a structural element of the list with an iterator, which is what you would increment/decrement. Merely iterating over the list shouldn't modify the nodes. Write a class whose only purpose is to iterate through the list.
Incidentally, a name like _Type, with a leading underscore and a capital letter, is reserved to the compiler/standard library implementers.
Incidentally, a name like _Type, with a leading underscore and a capital letter, is reserved to the compiler/standard library implementers.
Quote:Original post by Programmer16
template <typename _Type>
void TLinkedList<_Type>::Add(_Type Data)
{
if(!m_pHead)
{
m_pHead = new CNode<_Type>;
m_pTail = new CNode<_Type>;
m_pHead->Set(0, 0, Data);
m_pHead->m_pNext = m_pTail;
m_pTail = m_pHead;
}
else
{
CNode<_Type>* pTemp = new CNode<_Type>;
pTemp->Set(0, m_pTail, Data);
m_pTail->m_pNext = pTemp;
m_pTail = pTemp;
}
++m_nSize;
}
Not entirely certain its relevent to your access violation, but the first time you add an element, you create two nodes. Then you forget about one, and set both the head and the tail pointers to the same memory. Not sure if its the cause of your problem, because the rest of the code seems to work out, but worth fixing either way.
*edit:
Quote:
template <typename _Type>
void TLinkedList<_Type>::Remove(unsigned int nIndex)
{
CNode<_Type>* pNode = m_pHead;
while(pNode != 0)
pNode = pNode->m_pNext;
pNode->m_pPrevious->m_pNext = pNode->m_pNext;
delete pNode;
--m_nSize;
}
Because of the above bug, if you only have the one element, then pNode->m_pNext will not be 0 [it'll be that forgotten tail pointer]. So pNode becomes that forgotten tail pointer. But that pointer's ->m_pPrevious *is* 0, because you forgot about it. So that's an access violation right after your loop. But that entire function's broken, so I imagine you haven't gotten to testing it yet.
*edit2: Actually, I take that back. That'll access a null pointer no matter how many elements you've added. while(pNode != 0) will terminate when pNode=0, so if you reach the next line you're guarenteed to crash.
CM
[Edited by - Conner McCloud on June 20, 2005 5:22:00 AM]
Here's an example of a list class I just whipped up.
There's much, much more work to be done to make it equivalent to std::list, but that should give you a few ideas.
I still have to add in the copy constructor & assignment operators. Stay tuned.
#include <iostream>template<class T>class list{private: struct listnode { listnode* prev_; listnode* next_; T data_; listnode() {} listnode(const T& data) : data_(data) {} listnode(listnode* prev, listnode* next) : prev_(prev), next_(next) {} listnode(listnode* prev, listnode* next, const T& data) : prev_(prev), next_(next), data_(data) {} };private: listnode head_;public: // Give list::iterator access to the private list::listnode class. friend class iterator; class iterator { // list needs access to the non-default constructor. friend class list; private: listnode* node_; public: iterator() : node_(0) {} private: iterator(listnode* node ) : node_(node) {} public: iterator& operator++() { node_ = node_->next_; return *this; } iterator& operator--() { node_ = node_->prev_; return *this; } T& operator*() const { return node_->data_; } T* operator->() const { return &(node_->data); } bool operator==(const iterator& rhs) const { return node_ == rhs.node_; } bool operator!=(const iterator& rhs) const { return !(*this == rhs); } };public: list() : head_(&head_, &head_) {} ~list() { while( !empty() ) erase( begin() ); }public: iterator begin() { return iterator(head_.next_); } iterator end() { return iterator(&head_); } bool empty() const { return head_.next_ == &head_; }public: // Insert a new element before the specified location iterator insert(const iterator& itor, const T& data) { listnode* node = itor.node_; listnode* newnode = new listnode(node->prev_, node, data); node->prev_->next_ = newnode; node->prev_ = newnode; return iterator(newnode); } // Remove an element at the specified location iterator erase(const iterator& itor) { listnode* node = itor.node_; listnode* nextnode = node->next_; node->next_->prev_ = node->prev_; node->prev_->next_ = node->next_; delete node; return iterator(nextnode); }public: void push_back(const T& data) { insert(end(), data); } void pop_back() { erase(--end()); }};int main(){ list<int> l; std::cout << (l.empty() ? "list empty" : "list not empty") << std::endl; l.push_back(25); l.push_back(42); std::cout << (l.empty() ? "list empty" : "list not empty") << std::endl; list<int>::iterator it; for( it = l.begin(); it != l.end(); ++it ) { std::cout << *it << std::endl; } l.push_back(55); l.push_back(99); std::cout << (l.empty() ? "list empty" : "list not empty") << std::endl; for( it = l.begin(); it != l.end(); ++it ) { std::cout << *it << std::endl; } l.pop_back(); l.pop_back(); std::cout << (l.empty() ? "list empty" : "list not empty") << std::endl; for( it = l.begin(); it != l.end(); ++it ) { std::cout << *it << std::endl; } l.pop_back(); l.pop_back(); std::cout << (l.empty() ? "list empty" : "list not empty") << std::endl;}
There's much, much more work to be done to make it equivalent to std::list, but that should give you a few ideas.
I still have to add in the copy constructor & assignment operators. Stay tuned.
[smile] Note the way he uses nested classes for notational convenience.
Don't forget postfix operators:
Don't forget postfix operators:
public: iterator& operator++() { node_ = node_->next_; return *this; } iterator& operator--() { node_ = node_->prev_; return *this; } iterator& operator++(int) { node_ = node_->next_; return node_->prev_; } iterator& operator--(int) { node_ = node_->prev_; return node_->next_; }
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement