Planet Chili

Learn to program or die trying
https://forum.planetchili.net:443/

Yo' that list be stacked...

https://forum.planetchili.net:443/viewtopic.php?f=3&t=4090

Page 1 of 1

Yo' that list be stacked...

Posted: July 18th, 2017, 2:57 am
by albinopapa
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: Select all

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: Select all

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

Re: Yo' that list be stacked...

Posted: July 18th, 2017, 3:25 pm
by chili
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 ;)

Re: Yo' that list be stacked...

Posted: July 18th, 2017, 5:14 pm
by albinopapa
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*}.

Re: Yo' that list be stacked...

Posted: July 18th, 2017, 5:28 pm
by albinopapa
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.

Re: Yo' that list be stacked...

Posted: July 18th, 2017, 9:31 pm
by albinopapa
Just for fun.
Spoiler:
LinkedList.h

Code: Select all

#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: Select all

#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: Select all

#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: Select all

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

Re: Yo' that list be stacked...

Posted: July 19th, 2017, 2:43 pm
by chili
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.

Re: Yo' that list be stacked...

Posted: July 19th, 2017, 5:24 pm
by albinopapa
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: Select all

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. :(

Re: Yo' that list be stacked...

Posted: July 20th, 2017, 4:05 am
by chili
You shouldn't need traits. All you need is begin and end in the container, and your iterator needs to support increment, dereference, and !=.
All times are UTC
Page 1 of 1
Powered by phpBB® Forum Software © phpBB Limited
https://www.phpbb.com/