C++

Forum

 
Feedback for Stack Implementation

mpark4656 (181)
TextBook Problem: Efficiently implement a stack class using a singly linked list, with no header or tail nodes.

The below is my implementation. Please provide feedback.

Goals
Support similar operations as C++ Standard Template Library <stack>
Follow the Rules of 3 / 5
Utilize class template
Good code readability
Efficiency of algorithm

Also, please look at the copy constructor and suggest a better way to implement it (Implementing this was the most difficult for me)

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
 
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

#include <algorithm>

template <typename Object>
struct StackNode
{
    Object data;
    StackNode* prev;

    StackNode( const Object &x , StackNode* p = nullptr ): data{ x } , prev{ p } {}
    StackNode( const Object &&x , StackNode* p = nullptr ): data{ std::move( x ) } , prev{ p } {}
};

template <typename Object>
class Stack
{
public:
   /**
    *   Default Constructor
    */
    Stack(): theSize{ 0 } , theTop{ nullptr } {}

   /**
    *   Copy Constructor
    */
    Stack( const Stack &rhs ): theSize{ rhs.theSize } , theTop{ nullptr }
    {
        StackNode<Object>* current = rhs.theTop;

        // prev is set to null pointer for now, but in the while loop, prev will be updated
        StackNode<Object>* thisCurrent = new StackNode<Object> { current->data , nullptr };

        // Set theTop
        theTop = thisCurrent;

        while( current != nullptr ) {
            if( current->prev != nullptr ) {
                current = current->prev;    // Go to the previous element in rhs

                // Create a new pointer and copy the previous element in rhs
                StackNode<Object>* thisPrevious = new StackNode<Object> { current->data , nullptr };

                thisCurrent->prev = thisPrevious;
                thisCurrent = thisCurrent->prev;
            }
            else {
                thisCurrent->prev = nullptr;
                current = nullptr;  // Set current to null and end the loop
            }
        }
    }

    /**
    *   Move Constructor
    */
    Stack( const Stack &&rhs ): theSize{ rhs.theSize } , theTop{ rhs.theTop }
    {
        rhs.theSize = 0;

        // Reset pointer to prevent destruction of the original list
        rhs.theTop = nullptr;
    }

    /**
    *   Copy Assignment
    */
    Stack & operator= ( const Stack &rhs )
    {
        Stack copy = rhs;
        std::swap( *this , copy );
        return *this;
    }

    /**
    *   Move Assignment
    */
    Stack & operator= ( const Stack &&rhs )
    {
        std::swap( theSize , rhs.theSize );
        std::swap( theTop , rhs.theTop );
        return *this;
    }

    /**
    *   Destructor
    */
    ~Stack()
    {
        clear();
        delete theTop;
    }

   /**
    *   Add an element to the stack
    */
    void push( const Object &x )
    { push_back( x , theTop ); }

   /**
    *   Add an element to the stack (Move)
    */
    void push( const Object &&x )
    { push_back( std::move( x ) , theTop ); }

   /**
    *   Remove top element from the stack
    */
    void pop()
    { pop_back( theTop ); }

   /**
    *   Return reference to the top element in the stack
    */
    Object & top()
    { return back( theTop ); }

   /**
    *   Return the size of the stack
    */
    int size() const
    { return theSize; }

   /**
    *   Test if the stack is empty or not
    */
    bool empty() const
    { return theSize == 0; }

private:

   /**
    *   Internal Method to clear all contents in the stack
    */
    void clear()
    {
        while( !empty() ) {
            pop_back( theTop );
        }
    }

   /**
    *   Internal Method to return reference to the top element
    */
    Object & back( StackNode<Object>* &t ) const
    {
        if( t != nullptr ) {
            return t->data;
        }
        else {
            // Exception;
        }
    }

   /**
    *   Internal Method to remove top element in the stack
    */
    void pop_back( StackNode<Object>* &t )
    {
        if( t == nullptr ) {
            return;
        }
        else {
            StackNode<Object>* toDelete = t;

            t = t->prev;
            delete toDelete;
            theSize --;
        }
    }

   /**
    *   Internal Method to add element to stack
    */
    void push_back( const Object &x , StackNode<Object>* &t )
    {
        if( t == nullptr ) {
            t = new StackNode<Object> { x , nullptr };
        }
        else {
            StackNode<Object>* toAdd = new StackNode<Object> { x , t };
            t = toAdd;
        }
        theSize ++;
    }

    // Points to the top element in the stack
    StackNode<Object>* theTop;

    int theSize;
};

#endif // STACK_H_INCLUDED
Last edited on
dhayden (5795)
struct StackNode should be a struct within class Stack. Otherwise you pollute the namespace with what is fundamentally an implementation detail.

Lines 30-33: If rhs.theTop is null then you dereference a null pointer at line 33.
Copy assignment and move assignment methods: These swaps two stacks rather than assigning one to the other. If this contains data then you need to release it first and then copy or move the rhs data to this. Also, check for self-assignment.

push_back is overly complex. why not just
1
2
 
t = new StackNode<Object> { x , t };
theSize ++;

Line 92 is unnecessary since clear() will set theTop to nullptr

As far as readability, the data and methods say that theTop points to the back of the list which then contains a pointers to previous nodes. It's more common for a singly linked list to have next pointers and to refer to insert/delete from the front of the list.

mpark4656 (181)
@dhayden
Thank you for the time you spent reading my code and providing useful suggestions.

1. You're right. StackNode should be inside the Stack class

2. I will add a line to check if the rhs.theTop is null or not. Thank you for this good catch

3. I'm going to do more research on copy/move assignments and get back.

4. I don't know why I made push_back more complicated than it needs to be. The 2 lines you suggested should work just fine with another line for updating theTop.

5. I will remove line 92.

6. Lastly, the reason why I chose to insert and delete from the back of the list is because
I read the following article.
http://www.cplusplus.com/reference/stack/stack/

This article says the following

The container shall support the following operations:
empty
size
back
push_back
pop_back

This quote implies that stack is supposed to return reference to the last element in the list (back), insert at the end (push_back) and delete last item (pop_back). So I figured that all of these operations would be simple if I used link to previous node and have one pointer variable point to the last element, which is essentially "the top of the stack". Is this still a bad practice?

I have to admit though that if I set up the node in the way way you described, implementing the copy constructor would've been much easier and simpler for me.
Last edited on
mpark4656 (181)
UPDATED
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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
 
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

#include <algorithm>

template <typename Object>
class Stack
{
    struct StackNode
    {
        Object data;
        StackNode* prev;

        StackNode( const Object &x , StackNode* p = nullptr ): data{ x } , prev{ p } {}
        StackNode( const Object &&x , StackNode* p = nullptr ): data{ std::move( x ) } , prev{ p } {}
    };

public:
   /**
    *   Default Constructor
    */
    Stack(): theSize{ 0 } , theTop{ nullptr } {}

   /**
    *   Copy Constructor
    */
    Stack( const Stack &rhs ): theSize{ rhs.theSize } , theTop{ nullptr }
    {
        if( rhs.theTop != nullptr ) {
            StackNode* current = rhs.theTop;

            // prev is set to null pointer for now, but in the while loop, prev will be updated
            StackNode* thisCurrent = new StackNode { current->data , nullptr };

            // Set theTop
            theTop = thisCurrent;

            while( current != nullptr ) {
                if( current->prev != nullptr ) {
                    current = current->prev;    // Go to the previous element in rhs

                    // Create a new pointer and copy the previous element in rhs
                    StackNode* thisPrevious = new StackNode { current->data , nullptr };

                    thisCurrent->prev = thisPrevious;
                    thisCurrent = thisCurrent->prev;
                }
                else {
                    thisCurrent->prev = nullptr;
                    current = nullptr;  // Set current to null and end the loop
                }
            }
        }
        else{
            ;
        }
    }

    /**
    *   Move Constructor
    */
    Stack( Stack &&rhs ): theSize{ rhs.theSize } , theTop{ rhs.theTop }
    {
        rhs.theSize = 0;

        // Reset pointer to prevent destruction of the original list
        rhs.theTop = nullptr;
    }

    /**
    *   Copy Assignment
    */
    Stack & operator= ( const Stack &rhs )
    {
        Stack copy = rhs;
        std::swap( *this , copy );
        return *this;
    }

    /**
    *   Move Assignment
    */
    Stack & operator= ( Stack &&rhs )
    {
        std::swap( theSize , rhs.theSize );
        std::swap( theTop , rhs.theTop );
        return *this;
    }

    /**
    *   Destructor
    */
    ~Stack()
    {
        clear();
    }

   /**
    *   Add an element to the stack
    */
    void push( const Object &x )
    { push_back( x , theTop ); }

   /**
    *   Add an element to the stack (Move)
    */
    void push( Object &&x )
    { push_back( std::move( x ) , theTop ); }

   /**
    *   Remove top element from the stack
    */
    void pop()
    { pop_back( theTop ); }

   /**
    *   Return reference to the top element in the stack
    */
    Object & top()
    { return back( theTop ); }

   /**
    *   Return the size of the stack
    */
    int size() const
    { return theSize; }

   /**
    *   Test if the stack is empty or not
    */
    bool empty() const
    { return theSize == 0; }

private:

   /**
    *   Internal Method to clear all contents in the stack
    */
    void clear()
    {
        while( !empty() ) {
            pop_back( theTop );
        }
    }

   /**
    *   Internal Method to return reference to the top element
    */
    Object & back( StackNode* &t ) const
    {
        if( t != nullptr ) {
            return t->data;
        }
        else {
            // Exception;
        }
    }

   /**
    *   Internal Method to remove top element in the stack
    */
    void pop_back( StackNode* &t )
    {
        if( t == nullptr ) {
            return;
        }
        else {
            StackNode* toDelete = t;

            t = t->prev;
            delete toDelete;
            theSize --;
        }
    }

   /**
    *   Internal Method to add element to stack
    */
    void push_back( const Object &x , StackNode* &t )
    {
        StackNode* toAdd = new StackNode { x , t };
        t = toAdd;
        theSize ++;
    }

    // Points to the top element in the stack
    StackNode* theTop;

    int theSize;
};

#endif // STACK_H_INCLUDED
JLBorges (13770)
A somewhat different implementation; you may want to compare your implementation with this.

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
 
#ifndef MY_STACK_H_INCLUDED
#define MY_STACK_H_INCLUDED

#include <utility>
#include <cassert>

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

        stack() noexcept = default ; // default constructor

        ~stack() noexcept { clear() ; } // destructor

        stack( const stack<T>& that ) // copy constructor // *** TO BE FIXED *** see dhayden's post below
        { for( auto n = that.top_node ; n != nullptr ; n = n->next ) push(n->value) ; }

        stack( stack<T>&& that ) noexcept { this->swap(that) ; } // move constructor

        // dual purpose assignment operator: copy assignment, move assignment
        stack& operator= ( stack<T> that ) noexcept { return this->swap(that) ; }

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

        const_reference top() const noexcept { assert( !empty() ) ; return top_node->value ; }
        reference top() noexcept { assert( !empty() ) ; return top_node->value ; }

        void push( const T& v )
        {
            auto n = new node(v,top_node) ;
            top_node = n ;
            ++sz ;
        }

        void push( T&& v )
        {
            auto n = new node( std::move(v), top_node ) ;
            top_node = n ;
            ++sz ;
        }

        void pop() noexcept { assert( !empty() ) ; auto p = top_node ; top_node = top_node->next ; delete p ; --sz ; }

        void clear() noexcept { while( !empty() ) pop() ; }

        stack<T>& swap( stack<T>& that ) noexcept
        { using std::swap ; swap( top_node, that.top_node ) ; swap( sz, that.sz ) ; return *this ; }

        // note: emplace elided for brevity

        private:

            struct node // node is an implementation detail
            {
                T value ;
                node* next = nullptr ;

                node( const T& v ) : value(v) {}
                node( T&& v ) : value( std::move(v) ) {}
                node( const T& v, node* n ) : value(v), next(n) {}
                node( T&& v, node* n ) : value( std::move(v) ), next(n) {}

                // non-copyable, non-assignable
                node( const node& ) = delete ;
                node& operator= ( node& ) = delete ;
            };

            node* top_node = nullptr ;
            size_type sz = 0 ;
    };

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

#endif // MY_STACK_H_INCLUDED

http://coliru.stacked-crooked.com/a/5f98b8269bea94e1
Last edited on
mpark4656 (181)
@JLBorges

Could you explain the difference between using the std::swap and the swap that you defined for the move/copy assignment operator?

Also, how does your assignment operator achieve dual-purpose? It was my understanding that rvalue has to be passed as a parameter in order for that function to be used for moving.

Thank you.

JLBorges (13770)
> the difference between using the std::swap and the swap that you defined

Here, using unqualified swap using std::swap ; swap( top_node, that.top_node ) ; swap( sz, that.sz ) ;
is just being idiomatic, as the types (pointer and size_t) are not user-defined types.

More information: http://www.cplusplus.com/forum/general/155730/#msg801948

If we follow Scott Meyers' suggestion, in addition to defining a non-member swap in the enclosing namespace, we would also specialise std::swap for my::stack<>


> how does your assignment operator achieve dual-purpose?

See 'Copy-and-swap idiom' http://en.cppreference.com/w/cpp/language/copy_assignment

In C++11, such an assignment operator is known as a unifying assignment operator because it eliminates the need to write two different assignment operators: copy-assignment and move-assignment. As long as a class has a move-constructor, a C++11 compiler will always use it to optimize creation of a copy from another temporary (rvalue). https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Copy-and-swap
dhayden (5795)
JLBorges, doesn't your copy constructor reverse the order of the items (line 21)?

Also, it seems to me that the move constructor and assignment operator start with uninitialized values in top_node and sz. So when you swap them with "that", "this* becomes initialized by "that" contains uninitialized data, which means the behavior of the destructor for that is undefined. Am I missing something?

Thanks.
JLBorges (13770)
> doesn't your copy constructor reverse the order of the items (line 21)?

Yes, it does. Needs to be fixed. Thank you!


> the move constructor and assignment operator start with uninitialized values in top_node and sz.

Move constructor: there are in-class default member initialisers for top_node and sz.

Assignment operator: assignment always involves objects that were already initialised.
dhayden (5795)
Thanks. I knew I was missing something! :)
mpark4656 (181)
@JLBorges

I read http://www.cplusplus.com/forum/general/155730/#msg801948 but I still do not understand the real benefit of using specialized swap over the standard swap function. I'm rather new to C++, so please forgive me.

First, who is Scott Meyer? Second, could you explain in layman's term (with examples if possible) why it's recommended that swap is specialized? Why does the swap have to be (or what is the benefit of it being) non-throwing?

I may not have enough experience to understand all of your explanations, but if you can clarify, I would appreciate it.
JLBorges (13770)
> who is Scott Meyer?

Scott Meyers: https://en.wikipedia.org/wiki/Scott_Meyers


> I still do not understand the real benefit of using specialized swap over the standard swap function.

After C++11, with the advent of move semantics, it is not essential that we provide a custom swap for moveable types.

Scott Meyers' article was written prior to C++11.

With our stack class, we can see that while qualified_legacy_std98_swap is very expensive (copy construct, copy assign, copy assign, destroy non-trivially), qualified_std_swap (C++11) is a lot more efficient (move construct, move assign, move assign, destroy trivially).

The custom swap invoked via unqualified lookup unqualified_swap is the most efficient (swap pointer, swap size).

1
2
3
4
5
6
7
 
namespace std98 { template < typename T > void swap( T& a, T& b ) { T temp(a) ; a = b ; b = temp ; } }

void qualified_std_swap( my::stack<int>& a, my::stack<int>& b ) { std::swap(a,b) ; }

void unqualified_swap( my::stack<int>& a, my::stack<int>& b ) { using std::swap ; swap(a,b) ; }

void qualified_legacy_std98_swap( my::stack<int>& a, my::stack<int>& b ) { std98::swap(a,b) ; }


_Z18qualified_std_swapRN2my5stackIiEES2_: # @_Z18qualified_std_swapRN2my5stackIiEES2_
	.cfi_startproc
# BB#0:
	pushq	%r15
.Ltmp0:
	.cfi_def_cfa_offset 16
	pushq	%r14
.Ltmp1:
	.cfi_def_cfa_offset 24
	pushq	%rbx
.Ltmp2:
	.cfi_def_cfa_offset 32
	subq	$16, %rsp
.Ltmp3:
	.cfi_def_cfa_offset 48
.Ltmp4:
	.cfi_offset %rbx, -32
.Ltmp5:
	.cfi_offset %r14, -24
.Ltmp6:
	.cfi_offset %r15, -16
	movq	%rsi, %r14
	movq	%rdi, %rax
	movups	(%rax), %xmm0
	movaps	%xmm0, (%rsp)           # 16-byte Spill
	xorps	%xmm0, %xmm0
	movups	%xmm0, (%rax)
	movups	(%r14), %xmm1
	movups	%xmm0, (%r14)
	movq	(%rax), %rdi
	movq	8(%rax), %rbx
	movups	%xmm1, (%rax)
	testq	%rbx, %rbx
	je	.LBB0_4
	.align	16, 0x90
.LBB0_1:                                # %.lr.ph.i.i5.i
                                        # =>This Inner Loop Header: Depth=1
	movq	8(%rdi), %r15
	testq	%rdi, %rdi
	je	.LBB0_3
# BB#2:                                 #   in Loop: Header=BB0_1 Depth=1
	callq	_ZdlPv
.LBB0_3:                                # %_ZN2my5stackIiE3popEv.exit.i.i7.i
                                        #   in Loop: Header=BB0_1 Depth=1
	decq	%rbx
	movq	%r15, %rdi
	jne	.LBB0_1
.LBB0_4:                                # %_ZN2my5stackIiED2Ev.exit8.i
	movq	(%r14), %rdi
	movq	8(%r14), %rbx
	movaps	(%rsp), %xmm0           # 16-byte Reload
	movups	%xmm0, (%r14)
	testq	%rbx, %rbx
	je	.LBB0_8
	.align	16, 0x90
.LBB0_5:                                # %.lr.ph.i.i1.i
                                        # =>This Inner Loop Header: Depth=1
	movq	8(%rdi), %r14
	testq	%rdi, %rdi
	je	.LBB0_7
# BB#6:                                 #   in Loop: Header=BB0_5 Depth=1
	callq	_ZdlPv
.LBB0_7:                                # %_ZN2my5stackIiE3popEv.exit.i.i3.i
                                        #   in Loop: Header=BB0_5 Depth=1
	decq	%rbx
	movq	%r14, %rdi
	jne	.LBB0_5
.LBB0_8:                                # %_ZNSt3__14swapIN2my5stackIiEEEENS_9enable_ifIXaasr21is_move_constructibleIT_EE5valuesr18is_move_assignableIS5_EE5valueEvE4typeERS5_S8_.exit
	addq	$16, %rsp
	popq	%rbx
	popq	%r14
	popq	%r15
	retq
.Lfunc_end0:
	.size	_Z18qualified_std_swapRN2my5stackIiEES2_, .Lfunc_end0-_Z18qualified_std_swapRN2my5stackIiEES2_
	.cfi_endproc

	.globl	_Z16unqualified_swapRN2my5stackIiEES2_
	.align	16, 0x90
	.type	_Z16unqualified_swapRN2my5stackIiEES2_,@function
_Z16unqualified_swapRN2my5stackIiEES2_: # @_Z16unqualified_swapRN2my5stackIiEES2_
	.cfi_startproc
# BB#0:
	movups	(%rdi), %xmm0
	movups	(%rsi), %xmm1
	movups	%xmm1, (%rdi)
	movups	%xmm0, (%rsi)
	retq
.Lfunc_end1:
	.size	_Z16unqualified_swapRN2my5stackIiEES2_, .Lfunc_end1-_Z16unqualified_swapRN2my5stackIiEES2_
	.cfi_endproc

http://coliru.stacked-crooked.com/a/8dd4a39e68c173be
Last edited on
JLBorges (13770)
	.globl	_Z27qualified_legacy_std98_swapRN2my5stackIiEES2_
	.align	16, 0x90
	.type	_Z27qualified_legacy_std98_swapRN2my5stackIiEES2_,@function
_Z27qualified_legacy_std98_swapRN2my5stackIiEES2_: # @_Z27qualified_legacy_std98_swapRN2my5stackIiEES2_
	.cfi_startproc
# BB#0:
	jmp	_ZN5std984swapIN2my5stackIiEEEEvRT_S5_ # TAILCALL
.Lfunc_end2:
	.size	_Z27qualified_legacy_std98_swapRN2my5stackIiEES2_, .Lfunc_end2-_Z27qualified_legacy_std98_swapRN2my5stackIiEES2_
	.cfi_endproc

	.section	          .text._ZN5std984swapIN2my5stackIiEEEEvRT_S5_,"axG",@progbits,_ZN5std984swapIN2my5stackIiEEEEvRT_S5_,comdat
	.weak	_ZN5std984swapIN2my5stackIiEEEEvRT_S5_
	.align	16, 0x90
	.type	_ZN5std984swapIN2my5stackIiEEEEvRT_S5_,@function
_ZN5std984swapIN2my5stackIiEEEEvRT_S5_: # @_ZN5std984swapIN2my5stackIiEEEEvRT_S5_
.Lfunc_begin0:
	.cfi_startproc
	.cfi_personality 3, __gxx_personality_v0
	.cfi_lsda 3, .Lexception0
# BB#0:
	pushq	%rbp
.Ltmp13:
	.cfi_def_cfa_offset 16
	pushq	%r15
.Ltmp14:
	.cfi_def_cfa_offset 24
	pushq	%r14
.Ltmp15:
	.cfi_def_cfa_offset 32
	pushq	%r13
.Ltmp16:
	.cfi_def_cfa_offset 40
	pushq	%r12
.Ltmp17:
	.cfi_def_cfa_offset 48
	pushq	%rbx
.Ltmp18:
	.cfi_def_cfa_offset 56
	subq	$24, %rsp
.Ltmp19:
	.cfi_def_cfa_offset 80
.Ltmp20:
	.cfi_offset %rbx, -56
.Ltmp21:
	.cfi_offset %r12, -48
.Ltmp22:
	.cfi_offset %r13, -40
.Ltmp23:
	.cfi_offset %r14, -32
.Ltmp24:
	.cfi_offset %r15, -24
.Ltmp25:
	.cfi_offset %rbp, -16
	movq	%rsi, %r12
	movq	%rdi, 8(%rsp)           # 8-byte Spill
	movq	(%rdi), %rbx
	xorl	%r13d, %r13d
	testq	%rbx, %rbx
	je	.LBB3_1
# BB#2:
	xorl	%r14d, %r14d
	movq	%rbx, %rbp
	.align	16, 0x90
.LBB3_3:                                # %.lr.ph.i
                                        # =>This Inner Loop Header: Depth=1
	movl	$16, %edi
	callq	_Znwm
	movq	%rax, %r15
	movl	(%rbp), %eax
	movl	%eax, (%r15)
	movq	%r14, 8(%r15)
	incq	%r13
	movq	8(%rbp), %rbp
	testq	%rbp, %rbp
	movq	%r15, %r14
	jne	.LBB3_3
	jmp	.LBB3_4
.LBB3_1:
	xorl	%r15d, %r15d
.LBB3_4:                                # %_ZN2my5stackIiEC2ERKS1_.exit
	movq	(%r12), %r14
	movq	%r12, 16(%rsp)          # 8-byte Spill
	xorl	%r12d, %r12d
	testq	%r14, %r14
	je	.LBB3_5
# BB#6:
	xorl	%ebp, %ebp
	.align	16, 0x90
.LBB3_7:                                # %.lr.ph.i2
                                        # =>This Inner Loop Header: Depth=1
.Ltmp7:
	movl	$16, %edi
	callq	_Znwm
.Ltmp8:
# BB#8:                                 # %.noexc
                                        #   in Loop: Header=BB3_7 Depth=1
	movl	(%r14), %ecx
	movl	%ecx, (%rax)
	movq	%rbp, 8(%rax)
	incq	%r12
	movq	8(%r14), %r14
	testq	%r14, %r14
	movq	%rax, %rbp
	jne	.LBB3_7
	jmp	.LBB3_9
.LBB3_5:
	xorl	%eax, %eax
.LBB3_9:                                # %_ZN2my5stackIiEC2ERKS1_.exit5
	movq	8(%rsp), %rcx           # 8-byte Reload
	movq	%rax, (%rcx)
	movq	8(%rcx), %rbp
	movq	%r12, 8(%rcx)
	testq	%rbp, %rbp
	je	.LBB3_13
	.align	16, 0x90
.LBB3_10:                               # %.lr.ph.i.i6
                                        # =>This Inner Loop Header: Depth=1
	movq	8(%rbx), %r14
	testq	%rbx, %rbx
	je	.LBB3_12
# BB#11:                                #   in Loop: Header=BB3_10 Depth=1
	movq	%rbx, %rdi
	callq	_ZdlPv
.LBB3_12:                               # %_ZN2my5stackIiE3popEv.exit.i.i8
                                        #   in Loop: Header=BB3_10 Depth=1
	decq	%rbp
	movq	%r14, %rbx
	jne	.LBB3_10
.LBB3_13:                               # %_ZN2my5stackIiED2Ev.exit9
	xorl	%ebx, %ebx
	testq	%r15, %r15
	movl	$0, %eax
	movq	16(%rsp), %r12          # 8-byte Reload
	je	.LBB3_17
# BB#14:                                # %.lr.ph.i11.preheader
	xorl	%ebx, %ebx
	xorl	%r14d, %r14d
	movq	%r15, %rbp
	.align	16, 0x90
.LBB3_15:                               # %.lr.ph.i11
                                        # =>This Inner Loop Header: Depth=1
.Ltmp10:
	movl	$16, %edi
	callq	_Znwm
.Ltmp11:
# BB#16:                                # %.noexc14
                                        #   in Loop: Header=BB3_15 Depth=1
	movl	(%rbp), %ecx
	movl	%ecx, (%rax)
	movq	%r14, 8(%rax)
	incq	%rbx
	movq	8(%rbp), %rbp
	testq	%rbp, %rbp
	movq	%rax, %r14
	jne	.LBB3_15
.LBB3_17:                               # %_ZN2my5stackIiEC2ERKS1_.exit15
	movq	(%r12), %rdi
	movq	%rax, (%r12)
	movq	8(%r12), %rbp
	movq	%rbx, 8(%r12)
	testq	%rbp, %rbp
	je	.LBB3_21
	.align	16, 0x90
.LBB3_18:                               # %.lr.ph.i.i20
                                        # =>This Inner Loop Header: Depth=1
	movq	8(%rdi), %r14
	testq	%rdi, %rdi
	je	.LBB3_20
# BB#19:                                #   in Loop: Header=BB3_18 Depth=1
	callq	_ZdlPv
.LBB3_20:                               # %_ZN2my5stackIiE3popEv.exit.i.i22
                                        #   in Loop: Header=BB3_18 Depth=1
	decq	%rbp
	movq	%r14, %rdi
	jne	.LBB3_18
.LBB3_21:                               # %_ZN2my5stackIiED2Ev.exit23
	testq	%r13, %r13
	je	.LBB3_25
	.align	16, 0x90
.LBB3_22:                               # %.lr.ph.i.i16
                                        # =>This Inner Loop Header: Depth=1
	movq	8(%r15), %rbp
	testq	%r15, %r15
	je	.LBB3_24
# BB#23:                                #   in Loop: Header=BB3_22 Depth=1
	movq	%r15, %rdi
	callq	_ZdlPv
.LBB3_24:                               # %_ZN2my5stackIiE3popEv.exit.i.i18
                                        #   in Loop: Header=BB3_22 Depth=1
	decq	%r13
	movq	%rbp, %r15
	jne	.LBB3_22
.LBB3_25:                               # %_ZN2my5stackIiED2Ev.exit19
	addq	$24, %rsp
	popq	%rbx
	popq	%r12
	popq	%r13
	popq	%r14
	popq	%r15
	popq	%rbp
	retq
.LBB3_27:                               # %.loopexit.split-lp
.Ltmp9:
	jmp	.LBB3_28
.LBB3_26:                               # %.loopexit
.Ltmp12:
.LBB3_28:
	movq	%rax, %r14
	testq	%r13, %r13
	je	.LBB3_32
	.align	16, 0x90
.LBB3_29:                               # %.lr.ph.i.i
                                        # =>This Inner Loop Header: Depth=1
	movq	8(%r15), %rbx
	testq	%r15, %r15
	je	.LBB3_31
# BB#30:                                #   in Loop: Header=BB3_29 Depth=1
	movq	%r15, %rdi
	callq	_ZdlPv
.LBB3_31:                               # %_ZN2my5stackIiE3popEv.exit.i.i
                                        #   in Loop: Header=BB3_29 Depth=1
	decq	%r13
	movq	%rbx, %r15
	jne	.LBB3_29
.LBB3_32:                               # %_ZN2my5stackIiED2Ev.exit
	movq	%r14, %rdi
	callq	_Unwind_Resume
.Lfunc_end3:
	.size	_ZN5std984swapIN2my5stackIiEEEEvRT_S5_, .Lfunc_end3-_ZN5std984swapIN2my5stackIiEEEEvRT_S5_
	.cfi_endproc
	.section	.gcc_except_table,"a",@progbits
	.align	4
GCC_except_table3:
.Lexception0:
	.byte	255                     # @LPStart Encoding = omit
	.byte	3                       # @TType Encoding = udata4
	.asciz	"\266\200\200"          # @TType base offset
	.byte	3                       # Call site Encoding = udata4
	.byte	52                      # Call site table length
	.long	.Lfunc_begin0-.Lfunc_begin0 # >> Call Site 1 <<
	.long	.Ltmp7-.Lfunc_begin0    #   Call between .Lfunc_begin0 and .Ltmp7
	.long	0                       #     has no landing pad
	.byte	0                       #   On action: cleanup
	.long	.Ltmp7-.Lfunc_begin0    # >> Call Site 2 <<
	.long	.Ltmp8-.Ltmp7           #   Call between .Ltmp7 and .Ltmp8
	.long	.Ltmp9-.Lfunc_begin0    #     jumps to .Ltmp9
	.byte	0                       #   On action: cleanup
	.long	.Ltmp10-.Lfunc_begin0   # >> Call Site 3 <<
	.long	.Ltmp11-.Ltmp10         #   Call between .Ltmp10 and .Ltmp11
	.long	.Ltmp12-.Lfunc_begin0   #     jumps to .Ltmp12
	.byte	0                       #   On action: cleanup
	.long	.Ltmp11-.Lfunc_begin0   # >> Call Site 4 <<
	.long	.Lfunc_end3-.Ltmp11     #   Call between .Ltmp11 and .Lfunc_end3
	.long	0                       #     has no landing pad
	.byte	0                       #   On action: cleanup
	.align	4


	.ident	"clang version 3.8.0 (tags/RELEASE_380/final 263969)"
	.section	".note.GNU-stack","",@progbits

http://coliru.stacked-crooked.com/a/8dd4a39e68c173be
JLBorges (13770)
> could you explain in layman's term (with examples if possible) why it's recommended that swap is specialized?

To protect uninformed programmers who may write std::swap(a,b) ;
where they should have written using std::swap ; swap(a,b) ;.
If swap in namespace std is spcialised, the specialisation would call the custom swap.


> Why does the swap have to be (or what is the benefit of it being) non-throwing?

With a custom swap, the move constructor and the the unifying assignment operator) would use it. If the swap is non-throwing, the move constructor and move assignment would be non-throwing (as they should be) and copy assignment would provide a strong exception guarantee (ie. it would be an all or nothing operation).
mpark4656 (181)
Thank you so much!
Topic archived. No new replies allowed.