Jump to content
  • Advertisement
Sign in to follow this  
Programmer16

Data Structures

This topic is 4873 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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:
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;
}
};


Is this a bad idea (or a bad programming technique?)

Share this post


Link to post
Share on other sites
Advertisement
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Ok, now I'm getting an access violation when I'm cleaning up:

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

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Here's an example of a list class I just whipped up.


#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.

Share this post


Link to post
Share on other sites
[smile] Note the way he uses nested classes for notational convenience.

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_;
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!