Yo' that list be stacked...

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Yo' that list be stacked...

Post by albinopapa » July 18th, 2017, 2:57 am

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

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Yo' that list be stacked...

Post by chili » July 18th, 2017, 3:25 pm

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

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Yo' that list be stacked...

Post by albinopapa » July 18th, 2017, 5:14 pm

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

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Yo' that list be stacked...

Post by albinopapa » July 18th, 2017, 5:28 pm

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

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Yo' that list be stacked...

Post by albinopapa » July 18th, 2017, 9:31 pm

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

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Yo' that list be stacked...

Post by chili » July 19th, 2017, 2:43 pm

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

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Yo' that list be stacked...

Post by albinopapa » July 19th, 2017, 5:24 pm

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

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Yo' that list be stacked...

Post by chili » July 20th, 2017, 4:05 am

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

Post Reply