C++

Forum

 
Garbled Output

ChesterPlus (29)
I've encountered some wild output issues that I don't even know where to start with. I'm getting some garbled text that I've never seen before.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
#include <iostream>
#include "stack.h"
using namespace std;

int main(void)
{
    Stack<char> Char10;         // Test Character Stack, Default constructor
    Stack<float> Float5(5);     // Test Float Stack
    Stack<double> Double8(8);   // Test Double Stack
    Stack<bool> Bool2(2);       // Test Bool Stack
    Stack<char> Charcy(Char10); // Default copy constructor

    Bool2.Push(true);           // Test Push on Bool
    Bool2.Push(false);          // Test Push on Bool
    Bool2.Push(true);           // Test error on Push

    cout << "Size of Bool2 is:        " << Bool2.Size() << endl;
    cout << "Top element of Bool2 is: " << Bool2.Top() << endl;
    cout << "Size on Double8 should be 8: " << Double8.Size() << endl;

    Char10.Push('A');
    Char10.Push('B');
    Char10.Push('C');

    cout << "Test Pop on Char10, should produce a 'C': ";

    Char10.Pop();
    Char10.Push('C');

    cout << "Test ostream overload on Charcy, should be Empty:  ";
    cout << Charcy << endl;

    cout << "Test ostream overload on Char10, should be a 'C': ";
    cout << Char10 << endl;

    cout << "Test ostream overload on Char10, should be a 'B': ";
    cout << Char10 << endl;

    cout << "Test ostream overload on Char10, should be a 'A': ";
    cout << Char10 << endl;

    cout << "Test ostream overload on Char10, should be an error: ";
    cout << Char10 << endl;

    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
#ifndef STACK_H
#define STACK_H

#include <iostream>
#include <stack>
using namespace std;

const int DEFAULTSIZE = 100;

template <class T>
class Stack {
public:
    // Default Constructor, stack is size 100.
    Stack() {
        _capacity = DEFAULTSIZE;
        _stack = new T[_capacity];
        _top = -1;  //stack is empty
    }
    ~Stack();                       // Destructor
    Stack(const int size);          // Constructor, creates stack of size "size"
    Stack(const Stack<T>& other);    // Copy constructor

    bool Full();                    // Return true if the stack is full
    bool Empty();                   // Return true if the stack is empty

    int Size();                     // Return the size of the stack
    T Top();                        // Returns the top element, does not pop it.

    bool Push(const T item);        // Put an item on the stack.
    bool Pop();                     // Pop an item off and display to std out

    friend ostream& operator <<(ostream& os, const Stack<T>& s) {
        os << s._stack;
        return os;
    }
    Stack& operator = (const Stack<T> &s) {
        _capacity = s._capacity;
        _stack = new T[_capacity];
        _top = s._top;

        for (int i = 0; i < _capacity; i++) {
            _stack[i] = s._stack[i];
        }

        return *this;
    }
private:
    T* _stack;                      // The "stack"
    int _size;                      // The number of elements the stack can hold
    int _top;                       // Points to the first empty node
    int _capacity;                  // The size you allocated for the stack . 
    T  dummy;                       // Something to return in case there was an error on the Top()
};

#endif

template <class T>
Stack<T>::~Stack() {
    delete[] _stack;
}
template <class T>
Stack<T>::Stack(const int size) {
    _capacity = size;
    _stack = new T[_capacity];
    _top = -1;  //stack is empty
}
template <class T>
Stack<T>::Stack(const Stack<T>& other) {
    _capacity = other._capacity;
    _stack = new T[_capacity];
    _top = other._top;

    for (int i = 0; i < _capacity; i++) {
        _stack[i] = other._stack[i];
    }
}
        
template <class T>
bool Stack<T>::Full() {
    return (_top == _capacity - 1);
}
template <class T>
bool Stack<T>::Empty() {
    return (_top == -1);
}

template <class T>
int Stack<T>::Size() {
    return _top+1;
}
template <class T>      
T Stack<T>::Top() {
    return _stack[_top];
}

template <class T>
bool Stack<T>::Push(const T item) {
    if (_top == _capacity - 1) {
        cout << "Stack overflow." << endl;
        return false;
    }
    else {
        _top++;
        _stack[_top] = item;
        return true;
    }
}
template <class T>      
bool Stack<T>::Pop() {
    if (_top == -1) {
        cout << "Stack underflow." << endl;
        return false;
    }
    else {
        int temp = _stack[_top];
        _top--;
        return true;
    }
}
jonnin (11429)
pop of a stack usually gets the value and provides it to the user. yours discards the value.

what is your output?

while char* has a << magic overload, its the C string one and expects a 0 terminated string, which your stacks are not. Your overload will not behave well for non char*, even if you fix that. But you can see if the problem clears up with push (0) added in there to ensure the c-string compatibility.
Last edited on
Peter87 (11228)
jonnin wrote:
pop of a stack usually gets the value and provides it to the user. yours discards the value.

The way that ChesterPlus does it is the same way that pop() works for std::stack in the standard library. The only difference is that std::stack::pop() returns void and the behaviour is undefined if you call it on an empty stack.

https://en.cppreference.com/w/cpp/container/stack/pop

ChesterPlus wrote:
int temp = _stack[_top];

Though, you probably want to remove this line. It's meaningless and won't compile if the stack contains a type that is not implicitly convertible to int.

ChesterPlus wrote:
cout << Char10 << endl;

You repeat this code four times and expect different output each time, why?

The << operator does not modify the object that you print so it should print the same each time.

ChesterPlus wrote:
1
2
3
4
 
friend ostream& operator <<(ostream& os, const Stack<T>& s) {
    os << s._stack;
    return os;
}

This is not correct. You're printing s._stack which is a pointer.

For non-char pointers this will print the memory address.

But as jonnin said, the << overload for char* is special so it will assume it's a pointer to the first character in a null-terminated array (s._stack is not a null terminated array so the behaviour is undefined).

If you want it to print all the element of the stack then you need to use a loop that loops over all the elements in the stack and outputs them one by one.
Last edited on
jonnin (11429)
you are correct -- the stl pop does force you to get & then remove explicitly. Guess that was a throwback ... way back when you did your own containers, the ones I used pop gave the value back and I got used to it being a 2-for operation. Apologies, yours is fine if you get rid of the assignment to a discarded value.
ChesterPlus (29)
I have corrected all the error using everyone's input:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
#ifndef STACK_H
#define STACK_H

#include <iostream>
#include <stack>
using namespace std;

const int DEFAULTSIZE = 100;

template <class T>
class Stack {
public:
    // Default Constructor, stack is size 100.
    Stack() {
        _capacity = DEFAULTSIZE;
        _stack = new T[_capacity];
        _top = -1;  //stack is empty
    }
    ~Stack();                       // Destructor
    Stack(const int size);          // Constructor, creates stack of size "size"
    Stack(const Stack<T>& other);    // Copy constructor

    bool Full();                    // Return true if the stack is full
    bool Empty();                   // Return true if the stack is empty

    int Size();                     // Return the size of the stack
    T Top();                        // Returns the top element, does not pop it.

    bool Push(const T item);        // Put an item on the stack.
    bool Pop();                     // Pop an item off and display to std out

    friend ostream& operator <<(ostream& os, Stack<T>& s) {
        for (int i = s._top; i >= 0; i--) {
            os << s._stack[i] << " ";
        }
        s._top--;
        return os;
    }
    Stack& operator = (const Stack<T> &s) {
        _capacity = s._capacity;
        _stack = new T[_capacity];
        _top = s._top;

        for (int i = 0; i < _capacity; i++) {
            _stack[i] = s._stack[i];
        }

        return *this;
    }
private:
    T* _stack;                      // The "stack"
    int _size;                      // The number of elements the stack can hold
    int _top;                       // Points to the first empty node
    int _capacity;                  // The size you allocated for the stack . 
    T  dummy;                       // Something to return in case there was an error on the Top()
};

#endif

template <class T>
Stack<T>::~Stack() {
    delete[] _stack;
}
template <class T>
Stack<T>::Stack(const int size) {
    _capacity = size;
    _stack = new T[_capacity];
    _top = -1;  //stack is empty
}
template <class T>
Stack<T>::Stack(const Stack<T>& other) {
    _capacity = other._capacity;
    _stack = new T[_capacity];
    _top = other._top;

    for (int i = 0; i < _capacity; i++) {
        _stack[i] = other._stack[i];
    }
}
        
template <class T>
bool Stack<T>::Full() {
    return (_top == _capacity - 1);
}
template <class T>
bool Stack<T>::Empty() {
    return (_top == -1);
}

template <class T>
int Stack<T>::Size() {
    return _top + 1;
}
template <class T>      
T Stack<T>::Top() {
    return _stack[_top];
}

template <class T>
bool Stack<T>::Push(const T item) {
    if (_top == _capacity - 1) {
        cout << "Stack overflow." << endl;
        return false;
    }
    else {
        _top++;
        _stack[_top] = item;
        return true;
    }
}
template <class T>      
bool Stack<T>::Pop() {
    if (_top == -1) {
        cout << "Stack underflow." << endl;
        return false;
    }
    else {
        cout << _stack[_top] << endl;
        _top--;
        return true;
    }
}


I intended fo the << operator overload to pop one off the stack. That's why I called that function 4 times.
Peter87 (11228)
I still think it is a bit surprising to have a << operator that modifies the object that is printed. I don't understand why you would want this.

Normally the << stream output operator would take its second argument by const reference (like you did before) and just print it without modifying it.
Enoizat (1343)
Hi, ChesterPlus.
If I’m not misunderstanding your code, you’re using _top to represent the ‘size’ concept and you don’t tell properly apart the ‘size’ from the ‘capacity’.

‘Capacity’ → how many elements your array can store (before asking for new memory);
‘Size’ → the current number of elements that have been pushed into your array.
I don’t think you need _top at all.

E.g. (please note these are only examples!!):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
constexpr int Default_Size { 100 };

template <class T> class Stack {
public:
    Stack()
        : _capacity { Default_Size }
        , _stack { new T[_capacity] }
        , _size {}
    {
    }

private:
    int _capacity;      // The memory allocated
    T* _stack;
    int _size;          // The number of elements the stack currently holds
    T  dummy;           // ??? Do your really need this?
};


template <class T> Stack<T>::Stack( int capacity )
    : _capacity { capacity }
    , _stack { new T[_capacity] }
    , _size {}  //stack is empty
{
}


Full() --> return _size == _capacity;
Empty() --> return 0 == _size;
Size() --> return _size;
Top() --> return _stack[_size – 1];


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
template <class T> bool Stack<T>::Push(const T item)
{
    if (_size == _capacity) {
        std::cout << "Stack overflow.\n";
        return false;
    }
    else {
        _stack[_size] = item;
        ++_size;
        return true;
    }
}


template <class T> bool Stack<T>::Pop()
{
    if (0 == _size) {
        std::cout << "Stack underflow.\n";
        return false;
    }
    // Do you want to display the 'lost' element or the 'new' top element?
    else {
        --_size;
        std::cout << _stack[_size] << '\n';
        return true;
    }
}

Peter87 (11228)
Enoiza wrote:
I don’t think you need _top at all.

It's not necessary to have both _top and _size because one can be calculated from the other.

ChesterPlus wrote:
T dummy; // Something to return in case there was an error on the Top()
Enoiza wrote:
T dummy; // ??? Do your really need this?

This might have made sense if Top() returned a reference, but in that case you might want to store it as a static variable so that you only have to store one dummy object per element type instead of having each stack object contain its own.

Now Top() doesn't return a reference and you don't make use of the dummy object (calling Top() on an empty stack leads to undefined behaviour) so it doesn't look like your current code, the way it is written right now, needs a dummy object.

If you change Top() to return a reference and you want to allow calling it on an empty stack (which would be consistent with how Push and Pop works) then you might want to return a reference to the dummy object. Another perhaps more idiomatic alternative would be to throw an exception.
Last edited on
seeplus (6585)
Maybe something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
#include <iostream>
#include <algorithm>
#include <utility>

template <class T>
class Stack {
public:
	Stack(size_t size = DEFAULTSIZE);			// Constructor, creates stack of size "size"
	~Stack();						// Destructor

	Stack(const Stack<T>& other);				// Copy constructor
	Stack (Stack<T>&& other) noexcept;			// Move constructor

	Stack& operator= (Stack<T> s) noexcept;		        // Operator =

	bool Full() const noexcept;				// Return true if the stack is full
	bool Empty() const noexcept;				// Return true if the stack is empty
	size_t Size() const noexcept;				// Return the size of the stack
	size_t Capacity() const noexcept;			// Return stack capacity
	void Clear() noexcept;		         		// Clear the stack

	const T& Top() const;					// Returns the top element, does not pop it.
	T& Top();						// Returns the top element, does not pop it.
	bool Push(const T& item) noexcept;			// Put an item onto the stack.
	bool Push(T&& item) noexcept;				// Move an item onto the stack.
	bool Pop() noexcept;					// Pop an item off the stack

	Stack<T>& swap(Stack<T>& other) noexcept ;	        // Swap contents

	template<class T>
	friend std::ostream& operator<<(std::ostream& os, const Stack<T>& s);

private:
	constexpr static size_t DEFAULTSIZE { 100 };	        // Stack default size
	T* _stack {};						// The "stack"
	size_t _size {};					// The current number of elements
	const size_t _capacity { DEFAULTSIZE };			// The size allocated for the stack.
};

template<class T>
std::ostream& operator<<(std::ostream& os, const Stack<T>& s) {
	for (size_t i { s._size }; i > 0; --i)
		os << s._stack[i - 1] << ' ';

	return os;
}

template <class T>
Stack<T>::~Stack() {
	delete[] _stack;
}

template <class T>
Stack<T>::Stack(size_t cap) : _capacity { cap }, _stack { new T[cap] } {}

template <class T>
Stack<T>::Stack(const Stack<T>& other) : _capacity { other._capacity }, _stack { new T[_capacity] }, _size { other._size } {
	std::copy_n(other._stack, other._size, _stack);
}

template<class T>
Stack<T>::Stack(Stack<T>&& other) noexcept {
	swap(other);
}

template<class T>
Stack<T>& Stack<T>::swap(Stack<T>& other) noexcept {
	using std::swap;

	swap(other._capacity, _capacity);
	swap(other._size, _size);
	swap(other._stack, _stack);
	return *this;
}

template<class T>
Stack<T>& Stack<T>::operator= (Stack<T> s) noexcept {
	return swap(s);
}

template <class T>
bool Stack<T>::Full() const noexcept {
	return _size == _capacity;
}

template <class T>
bool Stack<T>::Empty() const noexcept {
	return (_size == 0);
}

template <class T>
size_t Stack<T>::Size() const noexcept {
	return _size;
}

template <class T>
size_t Stack<T>::Capacity() const noexcept {
	return _capacity;
}

template <class T>
void Stack<T>::Clear() noexcept {
	_size = 0;
}

template <class T>
const T& Stack<T>::Top() const {
	return _stack[_size - 1];
}

template <class T>
T& Stack<T>::Top() {
	return _stack[_size - 1];
}

template <class T>
bool Stack<T>::Push(const T& item) noexcept {
	if (Full()) {
		std::cout << "Stack overflow.\n";
		return false;
	}

	_stack[_size++] = item;
	return true;
}

template <class T>
bool Stack<T>::Push(T&& item) noexcept {
	if (Full()) {
		std::cout << "Stack overflow.\n";
		return false;
	}

	_stack[_size++] = std::move(item);
	return true;
}

template <class T>
bool Stack<T>::Pop() noexcept {
	if  (Empty()){
		std::cout << "Stack underflow.\n";
		return false;
	}

	_stack[--_size];
	return true;
}

int main() {
	Stack<int> si;

	si.Push(1);
	si.Push(2);

	std::cout << si << '\n';
	std::cout << si.Top() << '\n';
	si.Pop();
	std::cout << si.Top() << '\n';
	si.Push(3);

	const auto s2 { si };

	std::cout << s2 << '\n';
}



2 1
2
1
3 1

Last edited on
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
#include <iostream>
#include <concepts>
#include <cassert>
#include <memory>

namespace util
{
    template < typename T > requires std::copy_constructible<T> && std::destructible<T>
    struct stack
    {
        using value_type = T ;
        using size_type = std::size_t ;
        using reference = value_type& ;
        using const_reference = const value_type& ;

        stack() noexcept = default ;
        explicit stack( size_type max_size ) : cap(max_size), buffer( allocate(cap) ) {}
        ~stack() { if(buffer) { clear() ; deallocate(buffer) ; } }
        stack( const stack& that ) : sz(that.sz), cap(that.cap), buffer( allocate(cap) )
        { for( size_type i = 0 ; i < size() ; ++i ) push( that.buffer[i] ) ; }
        stack( stack&& that ) noexcept { swap(that) ; }
        stack& operator= ( stack that ) noexcept { return swap(that) ; }

        size_type capacity() const noexcept { return cap ; }
        size_type size() const noexcept { return sz ; }
        bool empty() const noexcept { return size() == 0 ; }
        bool full() const noexcept { return size() == capacity() ; }

        void clear() { while( !empty() ) pop() ; }
        reference top() noexcept { assert( !empty() && "top of empty stack!" ) ; return buffer[size()-1] ; }
        const_reference top() const noexcept { assert( !empty() && "top of empty stack!" ) ; return buffer[size()-1] ; }

        // https://en.cppreference.com/w/cpp/memory/construct_at
        void push( const_reference v ) { assert( !full() && "stack full!" ) ; std::construct_at( buffer+sz, v ) ; ++sz ; }
        void push( value_type&& v ) { assert( !full() && "stack full!" ) ; std::construct_at( buffer+sz, std::move(v) ) ; ++sz ; }
        template < typename... ARGS > void emplace( ARGS&&... args )
        {
            assert( !full() && "stack full!" ) ;
            std::construct_at( buffer+sz, std::forward<ARGS>(args)... ) ;
            ++sz ;
        }

        // https://en.cppreference.com/w/cpp/memory/destroy_at
        void pop() { assert( !empty() && "pop from empty stack!" ) ; --sz ; std::destroy_at( buffer + sz ) ; }

        private:

            size_type sz = 0 ;
            size_type cap = 0 ;
            T* buffer = nullptr ;

            // allocate uninitialised storage sufficient to hold n objects of type T
            // (note: even though the returned pointer is typed as T*, no objects of type T is created)
            static T* allocate( size_type n ) { return static_cast<T*>( ::operator new( n * sizeof(T) ) ) ; }

            // deallocate the uninitialised storage obtained from an earlier call to allocate
            static void deallocate( T* buffer ) noexcept { ::operator delete(buffer) ; }

            stack& swap( stack& that ) noexcept
            {
                using std::swap ;
                swap( sz, that.sz ) ;
                swap( cap, that.cap ) ;
                swap( buffer, that.buffer ) ;
                return *this ;
            }
    };

    template < typename T > void swap( stack<T>& a, stack<T>& b ) noexcept { a.swap(b) ; }
}

template struct util::stack<int> ;

struct A // *** A is copy constructible and destructible
{
    explicit A( int v ) : v(v) {} // *** but A is not not default constructible
    A& operator=( const A& ) = delete ; // *** and not assignable (to be placed in a non-resizeable container)
    int v ;
    friend std::ostream& operator<< ( std::ostream& stm, const A& a ) { return stm << "A{" << a.v << '}' ; }
};

int main()
{
    const std::size_t STK_SZ = 15 ;

    util::stack<A> stk(STK_SZ) ;

    while( stk.size() < STK_SZ/3 )
    {
        stk.emplace( stk.size() + 100 ) ; // *** construct in-place
        std::cout << stk.top() << ' ' ;
    }

    while( stk.size() < STK_SZ*2/3 )
    {
        stk.push( A( stk.size() + 100 ) ) ; // *** move construct
        std::cout << stk.top() << ' ' ;
    }

    while( !stk.full() )
    {
        const A a( stk.size() + 100 ) ;
        stk.push(a) ; // *** copy construct
        std::cout << stk.top() << ' ' ;
    }

    std::cout << "\n-----------------------------\n" ;

    while( !stk.empty() )
    {
       std::cout << stk.top() << ' ' ;
       stk.pop() ;
    }
    std::cout << "\n-----------------------------\n" ;
}

http://coliru.stacked-crooked.com/a/e8bf4bcf3e8754fd
Topic archived. No new replies allowed.