Register    Login    Forum    Search    FAQ

Board index » Everything




Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post Posted: July 18th, 2017, 2:57 am 
 

Joined: February 28th, 2013, 3:23 am
Posts: 2554
Location: Oklahoma, United States
Ok, I hate linked lists, and to deal with the way a stack is organized on top of that, chili you're evil.

Spoiler:
Code:
class Stack
{
   class Elem
   {
   public:
      Elem( int Value, Elem *NextElem )
         :
         value( Value ),
         pNext( NextElem )
      {
      }
      int value = -1;
      Elem *pNext = nullptr;
   };
public:
   Stack();
   Stack( const Stack &Src );
   ~Stack();

   Stack &operator=( const Stack &Src );
   
   void Push( int val );
   int Pop();
   int Size() const;
   bool Empty() const;

private:
   void Release();
   void Copy( Elem *pElem );
private:   
   Elem *pHead = nullptr;
   int size = 0;
};

Spoiler:
Code:
#include "Stack.h"

Stack::Stack()
{
}

Stack::Stack( const Stack & Src )
{   
   *this = Src;
}

Stack::~Stack()
{
   Release();
}

Stack & Stack::operator=( const Stack & Src )
{
   Release();
   Copy( Src.pHead );

   return *this;
}

void Stack::Push( int val )
{   
   pHead = new Stack::Elem( val, pHead );
   ++size;
}

int Stack::Pop()
{
   if( Empty() ) return -1;

   --size;
   const auto val = pHead->value;
   auto ptr = pHead->pNext;

   delete pHead;
   pHead = ptr;

   return val;
}

int Stack::Size() const
{
   return size;
}

bool Stack::Empty() const
{
   return pHead == nullptr;
}

void Stack::Release()
{
   while( Pop() != -1 );
}

void Stack::Copy( Elem * pElem )
{
   if( !pElem )return;   
   Copy( pElem->pNext );

   Push( pElem->value );
}


Didn't mean to hijack Yumtard's thread, moved to it's own.

_________________
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com


Top 
 Profile  
Reply with quote  
 Post Posted: July 18th, 2017, 3:25 pm 
Site Admin
User avatar

Joined: December 31st, 2011, 4:53 pm
Posts: 3284
Location: Japan
Looks good, looks good. Moving the release/copy code to private funcs is a good move to eliminate code duplication (I didn't bother to do that in the solution video).

You should remove the destructor altogether and see what happens ;)

_________________
Chili


Top 
 Profile  
Reply with quote  
 Post Posted: July 18th, 2017, 5:14 pm 
 

Joined: February 28th, 2013, 3:23 am
Posts: 2554
Location: Oklahoma, United States
Quote:
Detected memory leaks!
Dumping objects ->
{99} normal block at 0x0000028713F3F460, 16 bytes long.
Data: < > 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
{97} normal block at 0x0000028713F3F320, 16 bytes long.
Data: < > 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
{94} normal block at 0x0000028713F3F2D0, 16 bytes long.
Data: < > 03 00 00 00 00 00 00 00 F0 F0 F3 13 87 02 00 00
{93} normal block at 0x0000028713F3F0F0, 16 bytes long.
Data: < > 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
{91} normal block at 0x0000028713F3F280, 16 bytes long.
Data: < > 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
{89} normal block at 0x0000028713F3F0A0, 16 bytes long.
Data: < > 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
{86} normal block at 0x0000028713F3F690, 16 bytes long.
Data: < > 03 00 00 00 00 00 00 00 E0 F1 F3 13 87 02 00 00
{85} normal block at 0x0000028713F3F1E0, 16 bytes long.
Data: < > 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
{79} normal block at 0x0000028713F3F7D0, 16 bytes long.
Data: <E @ > 45 00 00 00 00 00 00 00 40 F1 F3 13 87 02 00 00
{77} normal block at 0x0000028713F3F140, 16 bytes long.
Data: < > 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
{76} normal block at 0x0000028713F3F780, 16 bytes long.
Data: < > 03 00 00 00 00 00 00 00 10 F4 F3 13 87 02 00 00
{75} normal block at 0x0000028713F3F410, 16 bytes long.
Data: < > 03 00 00 00 00 00 00 00 C0 F3 F3 13 87 02 00 00
{74} normal block at 0x0000028713F3F3C0, 16 bytes long.
Data: < > 03 00 00 00 00 00 00 00 B0 F4 F3 13 87 02 00 00
{73} normal block at 0x0000028713F3F4B0, 16 bytes long.
Data: < > 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Object dump complete.


That's cool, it shows the address of the unreleased Stack::Elem pointers and their data members {int,Elem*}.

_________________
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com


Top 
 Profile  
Reply with quote  
 Post Posted: July 18th, 2017, 5:28 pm 
 

Joined: February 28th, 2013, 3:23 am
Posts: 2554
Location: Oklahoma, United States
While I thought it clever to use recursion on the Copy function, I wouldn't know how to avoid stack overflows.

The test I failed first was the copy ( test 5 I think ). This was really the reason I called you evil. :) The reason I failed it was because of the order of stacks. The first time I copied, of course it was in reverse order. I tried cheating by looking through Yumtard's code, but got confused by his implementation.

When I thought about it some, you need to start at the bottom, but this is a singly linked list so you don't have access to the parent/previous element. The easiest way I could think of to go in reverse was to have the compiler unwind the stack through recursion. These are two things (recursion and linked lists) I've always passed over because I didn't understand the implementations I've seen. The code I've looked through from random places always seemed to complicated.

Thanks for the challenge, it was fun.

_________________
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com


Top 
 Profile  
Reply with quote  
 Post Posted: July 18th, 2017, 9:31 pm 
 

Joined: February 28th, 2013, 3:23 am
Posts: 2554
Location: Oklahoma, United States
Just for fun.
Spoiler:
LinkedList.h
Code:
#pragma once

class LinkedList
{
   class Elem
   {
   public:
      Elem( int Value, Elem *NextElem );

   public:
      int value = -1;
      Elem *pNext = nullptr;
   };
public:
   class ListIter
   {
   public:
      ListIter( Elem *pElem );
      ListIter &operator++();
      ListIter operator++( int );

      operator bool()const;
      bool operator==( const ListIter &Iter )const;
      bool operator!=( const ListIter &Iter )const;

      Elem *operator*();
      const Elem *operator*()const;

   private:
      Elem *pElem;
   };
public:
   LinkedList();
   LinkedList( const LinkedList &Src );

   LinkedList &operator=( const LinkedList &Src );

   ListIter begin();
   const ListIter begin()const;
   ListIter end();
   const ListIter end()const;

   Elem *front();
   Elem *back();
   void PushFront( int val );
   void PushBack( int val );
   void Insert( ListIter &Where, int val );

   int PopFront();
   int PopBack();
   int Erase( ListIter &Where );

   int Size() const;
   bool Empty() const;

   void Clear();
private:
   ListIter &FindPrevious( const ListIter &Where )const;
   void Release();
   void Copy( const ListIter &pElem );

private:
   Elem *pHead = nullptr;
   int size = 0;
};

LinkedList.cpp
Code:
#include "LinkedList.h"

// Begin Elem class
LinkedList::Elem::Elem( int Value, Elem * NextElem )
   :
   value( Value ),
   pNext( NextElem )
{
}

// Begin Iter class
LinkedList::ListIter::ListIter( Elem * pElem )
   :
   pElem( pElem )
{
}

LinkedList::ListIter &LinkedList::ListIter::operator++()
{
   if( !pElem ) return ListIter( nullptr );
   pElem = pElem->pNext;
   return *this;
}

LinkedList::ListIter LinkedList::ListIter::operator++( int )
{
   ListIter itr( pElem );
   ++( *this );
   return itr;
}

LinkedList::ListIter::operator bool()const
{
   return pElem != nullptr;
}

bool LinkedList::ListIter::operator==( const ListIter & Iter ) const
{
   return pElem == ( *Iter );
}

bool LinkedList::ListIter::operator!=( const ListIter & Iter ) const
{
   return !( *this == Iter );
}

LinkedList::Elem *LinkedList::ListIter::operator*()
{
   return pElem;
}

const LinkedList::Elem *LinkedList::ListIter::operator*() const
{
   return pElem;
}

// Begin List class
LinkedList::LinkedList()
{
}

LinkedList::LinkedList( const LinkedList & Src )
{
   Copy( Src.begin() );
}

LinkedList & LinkedList::operator=( const LinkedList & Src )
{
   if( this == &Src )return *this;

   Release();
   Copy( Src.begin() );

   return *this;
}

LinkedList::ListIter LinkedList::begin()
{
   return{ pHead };
}

const LinkedList::ListIter LinkedList::begin() const
{
   return{ pHead };
}

LinkedList::ListIter LinkedList::end()
{
   auto next = begin();
   while( next++ );
   return next;
}

const LinkedList::ListIter LinkedList::end() const
{
   auto next = begin();
   while( next++ );
   return next;
}

LinkedList::Elem * LinkedList::front()
{
   return pHead;
}

LinkedList::Elem * LinkedList::back()
{
   if( !pHead )return pHead;

   auto cur = begin();
   auto next = cur;

   while( ++next )
   {
      ++cur;
   }

   return *cur;
}

void LinkedList::PushFront( int val )
{
   pHead = new Elem( val, pHead );
   ++size;
}

void LinkedList::PushBack( int val )
{
   if( !pHead )
   {
      PushFront( val );
      return;
   }
   auto pBack = back();
   
   pBack->pNext = new Elem( val, nullptr );
   ++size;
}

void LinkedList::Insert( ListIter &Where, int val )
{
   ( *Where )->pNext = new Elem( val, ( *Where )->pNext );
   ++size;
}

int LinkedList::PopFront()
{
   if( !pHead )return -1;

   auto pFront = front();
   pHead = pFront->pNext;

   const auto val = pFront->value;
   --size;

   delete pFront;

   return val;
}

int LinkedList::PopBack()
{
   if( !pHead )return -1;

   return Erase( ListIter{ back() } );
}

int LinkedList::Erase( ListIter &Where )
{
   if( !pHead ) return -1;

   --size;
   auto cur = FindPrevious( Where );
   const auto val = ( *Where )->value;
   ( *cur )->pNext = ( *Where )->pNext;
   delete ( *Where );

   return val;
}

int LinkedList::Size() const
{
   return size;
}

bool LinkedList::Empty() const
{
   return pHead == nullptr;
}

void LinkedList::Clear()
{
   Release();
}

LinkedList::ListIter &LinkedList::FindPrevious( const ListIter &Where )const
{
   auto cur = begin();
   auto next = cur;
   while( ( ++next ) != Where )
   {
      ++cur;
   }

   return cur;
}

void LinkedList::Release()
{
   while( PopFront() != -1 );
}

void LinkedList::Copy( const ListIter &pElem )
{
   do
   {
      auto cur = ListIter( pElem )++;
      PushBack( ( *cur )->value );
   } while( pElem );
}



Spoiler:
LinkedStack.h
Code:
#pragma once

#include "LinkedList.h"

class LinkedStack
{
public:
   LinkedStack() = default;
   LinkedStack( const LinkedStack &Src );
   ~LinkedStack();

   LinkedStack &operator=( const LinkedStack &Src );

   void Push( int val );
   int Pop();
   int Size() const;
   bool Empty() const;

private:
   void Copy( const LinkedList &Src );
private:
   LinkedList list;
};


LinkedStack.cpp
Code:
#include "LinkedStack.h"



LinkedStack::LinkedStack( const LinkedStack & Src )
{
   Copy( Src.list );
}

LinkedStack::~LinkedStack()
{
   list.Clear();
}

LinkedStack & LinkedStack::operator=( const LinkedStack & Src )
{
   Copy( Src.list );
   return *this;
}

void LinkedStack::Push( int val )
{
   list.PushFront( val );
}

int LinkedStack::Pop()
{
   return list.PopFront();
}

int LinkedStack::Size() const
{
   return list.Size();
}

bool LinkedStack::Empty() const
{
   return list.Empty();
}

void LinkedStack::Copy( const LinkedList & Src )
{
   auto elem = Src.begin();
   while( elem != Src.end() )
   {
      list.PushBack( ( *elem )->value );
      ++elem;
   }
}

_________________
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com


Top 
 Profile  
Reply with quote  
 Post Posted: July 19th, 2017, 2:43 pm 
Site Admin
User avatar

Joined: December 31st, 2011, 4:53 pm
Posts: 3284
Location: Japan
Yeah, I didn't really take stack overflows into consideration for this exercise, but it would be a real concern if you were actually building a general-purpose container.

Also, nice custom iterators. I love custom iterators.

_________________
Chili


Top 
 Profile  
Reply with quote  
 Post Posted: July 19th, 2017, 5:24 pm 
 

Joined: February 28th, 2013, 3:23 am
Posts: 2554
Location: Oklahoma, United States
I perused the STL list file last night and found out that it's a doubly linked list; I did not know that.

I wish I could figure out how to make iterators that work with ranged for loops and other algorithms. Was trying to make a STL compatible 2D buffer and some similar algorithms to the STL; an example algorithm would be
Code:
template<size_t Width, size_t Height>
OutIt std::copy2d( InIt srcbeg, InIt srcend, OutIt dstbeg );


As far as custom iterators and algorithm interaction goes, they seem fairly accepting; you can use raw pointers as the In and Out iterators. I wasn't able to use a range based for loop with the custom iterator class that I've tried in the past. I'll try again and see if I can get some info posted. I guess, if I remember right, had something to do with me not using the iterator traits, but it's been awhile.

You know, I'm not sure why I don't post here more often when I'm actually needing help. :(

_________________
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com


Top 
 Profile  
Reply with quote  
 Post Posted: July 20th, 2017, 4:05 am 
Site Admin
User avatar

Joined: December 31st, 2011, 4:53 pm
Posts: 3284
Location: Japan
You shouldn't need traits. All you need is begin and end in the container, and your iterator needs to support increment, dereference, and !=.

_________________
Chili


Top 
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
 
Post new topic Reply to topic  [ 8 posts ] 

Board index » Everything


 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for: