2
\$\begingroup\$

My original deque implementation and efficiency question lacked move semantics. After ratchet freak provided an example of how to define them I decided to try adding them to my deque. The unit test + output below shows that the code is working.

However, my new question is: Are there edge cases in any of my move semantic functions that I may have forgotten, and is the data.~type(); necessary in the eNode<type>::operator=(type && other)? I'd also appreciate any feedback on my coding style.

template<class type>
class eDeque;
//*************************************************
//              eNode
// to be used with friend class eDeque<type>
//*************************************************
template<class type>
class eNode {

    friend class eDeque<type>;

public :

// ... remainder of class definition (see referenced question)

    explicit        eNode(type && data) : prev(nullptr), next(nullptr) { std::swap(this->data, data); };    // move constructor
                    // DEBUG: destructor omitted because no heap allocation occurs

    eNode<type> &   operator=(eNode<type> && other) {                                                                   // move assignment
                                                  data.~type(); 
                                                  std::swap(this->data, other.data); 
                                                  return *this;};

// ... remainder of class definition (see referenced question)

private:

    eNode<type> *   prev;
    eNode<type> *   next;
    type            data;
};

template <class type>
class eDeque {
public:

// ... remainder of class definition (see referenced question)

                        eDeque(eDeque<type> && other);              // move constructor
    eDeque<type> &      operator=(eDeque<type> && other);           // move assignment
    void                PushFront(type && data);                    // emplace and move
    void                PushBack(type && data);                     // emplace and move

private:

    eNode<type> *       front;
    eNode<type> *       back;
    int                 nodeCount;
 // ... remainder of class definition (see referenced question)
};

//******************
// eDeque::eDeque
// move constructor
//******************
template <class type>
inline eDeque<type>::eDeque(eDeque<type> && other) : nodeCount(0), front(nullptr), back(nullptr) {
    std::swap(nodeCount, other.nodeCount);
    std::swap(front, other.front);
    std::swap(back, other.back);
}

//******************
// eDeque::operator=
// move assignment
//******************
template <class type>
inline eDeque<type> & eDeque<type>::operator=(eDeque<type> && other) {
    Clear();
    std::swap(nodeCount, other.nodeCount);
    std::swap(front, other.front);
    std::swap(back, other.back);
    return *this;
}

//******************
// eDeque::PushFront
// emplace and move
//******************
template <class type>
inline void eDeque<type>::PushFront(type && data) {
    eNode<type> * newFront;

    newFront = new eNode<type>(std::move(data));
    if (front == nullptr) {
        back = newFront;
        front = newFront;
    } else {
        newFront->prev = front;
        front->next = newFront;
        front = newFront;
    }
    nodeCount++;
}

//******************
// eDeque::PushBack
// emplace and move
//******************
template <class type>
inline void eDeque<type>::PushBack(type && data) {
    eNode<type> * newBack;

    newBack = new eNode<type>(std::move(data));
    if (back == nullptr) {
        back = newBack;
        front = newBack;
    }
    else {
        newBack->next = back;
        back->prev = newBack;
        back = newBack;
    }
    nodeCount++;
}

The following is the parts of the unit test added to the original source plus some context:

#include "Deque.h"

// iterate and print back to front
template<class type>
void PrintDeque(const eDeque<type> & de, const char * name) {
    eNode<int> * iterator;
    int i;

    printf("%s size == %i\n", name, de.Size());
    for (i = 0, iterator = de.Back(); iterator != nullptr; iterator = iterator->Next())
        printf("node %i == %i\n", i++, iterator->Data());
    printf("\n\n");
}

// iterate and increment by amount back to front
template<class type>
void IncrementData(const eDeque<type> & de, int amount) {
    eNode<int> * iterator;

    for (iterator = de.Back(); iterator != nullptr; iterator = iterator->Next())
        iterator->Data() += amount;
}

// unit test
int main() {
    int lValues[] = { 0, 1, 2, 3, 4, 5, 6 };
    printf("BEGIN eDeque COPY TESTS\n\n");

    eDeque<int> original;
    original.PushFront(lValues[0]);
    original.PushFront(lValues[1]);
    original.PushFront(lValues[2]);
    original.PushFront(lValues[3]);
    original.PushFront(lValues[4]);
    original.PushFront(lValues[5]);
    original.PushBack(lValues[6]);
    original.PopBack();
    original.PopFront();
    PrintDeque(original, "original");


    eDeque<int> B;
    printf("B.Size() < original.Size()\n");
    PrintDeque(B, "B_before_copyAssign");
    B = original;                               // copy assignment test with B.Size() < original.Size()
    printf("B = original\n");
    PrintDeque(B, "B result");

    eDeque<int> C;
    // these are now emplace and move calls
    C.PushBack(10);
    C.PushFront(11);
    C.PushBack(12);
    C.PushFront(13);
    C.PushBack(14);
    C.PushFront(15);
    C.PushBack(16);
    C.PushFront(17);
    printf("C.Size() > original.Size()\n");
    PrintDeque(C, "C_before_copyAssign");
    C = original;                               // copy assignment test with C.Size() > original.Size()
    printf("C = original\n");
    PrintDeque(C, "C result");

    // verify the original is intact
    printf("original deque intact\n");
    PrintDeque(original, "original");

    IncrementData(C, 5);
    printf("incremented each node of C by 5\n");
    PrintDeque(C, "C result");

    printf("B.Size() == C.Size()\n");
    B = C;                                      // copy assignment test with B.Size() == C.Size()
    printf("B = C\n");
    PrintDeque(B, "B result");

// BEGIN eDeque move semantics testing
    eDeque<int> G = eDeque<int>(B);             // copy construct an rvalue eDeque, then move construct G
    printf("eDeque<int> G = eDeque<int>(B) move construction\n");
    PrintDeque(G, "G result");

    IncrementData(B, 10);
    printf("incremented each node of B by 10\n");
    PrintDeque(B, "B result");

    G = eDeque<int>(std::move(B));              // move construct an rvalue eDeque, then move assign G (B becomes undefined/unspecified)
    printf("G = eDeque<int>(B) move assignment (B becomes unspecified)\n");
    PrintDeque(G, "G result");
    PrintDeque(B, "B result");

    int lValue = 666;
    printf("G.PushBack(std::move(lValue == 666)); G.PushFront(777) emplace and move\n");
    G.PushBack(std::move(lValue));              // emplace and move
    G.PushFront(777);                           // emplace and move
    PrintDeque(G, "G result");
// END eDeque move semantics testing

    printf("END eDeque COPY TESTS\n\n");
    printf("BEGIN eNODE COPY TESTS\n\n");

// BEGIN eNode move semantics testing
    eNode<int> H = eNode<int>(123);             // move construction
    printf("eNode<int> H = eNode<int>(123) move construction result: H.Data() == %i\n\n", H.Data());

    H = eNode<int>(456);                        // move assignment
    printf("H = eNode<int>(456) move assignment result: H.Data() == %i, H.Next() == %p, H.Prev() == %p\n\n", H.Data(), H.Next(), H.Prev());

    printf("G.PushFront(std::move(H.Data()))\n");
    G.PushFront(std::move(H.Data()));           // H.data now unspecified
    PrintDeque(G, "G result");
// END eNode move semantics testing

    printf("END eNODE COPY TESTS\n\n");
    return 0;
}

The following is the output of the relevant unit test code:

BEGIN eDeque COPY TESTS

original size == 5
node 0 == 0
node 1 == 1
node 2 == 2
node 3 == 3
node 4 == 4


B.Size() < original.Size()
B_before_copyAssign size == 0


B = original
B result size == 5
node 0 == 0
node 1 == 1
node 2 == 2
node 3 == 3
node 4 == 4


C.Size() > original.Size()
C_before_copyAssign size == 8
node 0 == 16
node 1 == 14
node 2 == 12
node 3 == 10
node 4 == 11
node 5 == 13
node 6 == 15
node 7 == 17  


C = original
C result size == 5
node 0 == 0
node 1 == 1
node 2 == 2
node 3 == 3
node 4 == 4


original deque intact
original size == 5
node 0 == 0
node 1 == 1
node 2 == 2
node 3 == 3
node 4 == 4


incremented each node of C by 5
C result size == 5
node 0 == 5
node 1 == 6
node 2 == 7
node 3 == 8
node 4 == 9


B.Size() == C.Size()
B = C
B result size == 5
node 0 == 5
node 1 == 6
node 2 == 7
node 3 == 8
node 4 == 9


eDeque<int> G = eDeque<int>(B) move construction
G result size == 5
node 0 == 5
node 1 == 6
node 2 == 7
node 3 == 8
node 4 == 9


incremented each node of B by 10
B result size == 5
node 0 == 15
node 1 == 16
node 2 == 17
node 3 == 18
node 4 == 19


G = eDeque<int>(B) move assignment (B becomes unspecified)
G result size == 5
node 0 == 15
node 1 == 16
node 2 == 17
node 3 == 18
node 4 == 19


B result size == 0


G.PushBack(std::move(lValue == 666)); G.PushFront(777) emplace and move
G result size == 7
node 0 == 666
node 1 == 15
node 2 == 16
node 3 == 17
node 4 == 18
node 5 == 19
node 6 == 777


END eDeque COPY TESTS

BEGIN eNODE COPY TESTS


eNode<int> H = eNode<int>(123) move construction result: H.Data() == 123

H = eNode<int>(456) move assignment result: H.Data() == 456, H.Next() == 0000000
0, H.Prev() == 00000000

G.PushFront(std::move(H.Data()))
G result size == 8
node 0 == 666
node 1 == 15
node 2 == 16
node 3 == 17
node 4 == 18
node 5 == 19
node 6 == 777
node 7 == 456


END eNODE COPY TESTS
\$\endgroup\$
  • 1
    \$\begingroup\$ Try your code with eDeque<std::string> and then with eDeque<std::unique_ptr<int>>. \$\endgroup\$ – Quuxplusone Nov 18 '16 at 4:08
  • \$\begingroup\$ std::string worked fine, but std::unique_ptr<type> usage exposed my lack of a eNode ( eNode<type> && other) move constructor. Fixed. \$\endgroup\$ – TOM__ Nov 18 '16 at 16:54
  • 1
    \$\begingroup\$ eNode<std::string> H("you might need more than 24 characters here"); H = eNode<std::string>("123"); should not have worked, because of that explicit destructor call you were worried about. (You were right to be worried.) Where do you even use that assignment operator, though? I don't think your deque relies on that functionality (nor should it). \$\endgroup\$ – Quuxplusone Nov 18 '16 at 20:51
1
\$\begingroup\$

Credit to Quuxplusone for the test cases.

The test-case for std::unique_ptr<type> came up and it threw a bug-unearthing monkey-wrench in my design (as did std::string) during assignment operations.

I devised the following std::unique_ptr test to see if my explicit data.~type(); call is necessary and I noticed that std::unique_ptr seems to call its pointed-to object's destructor if the std::unique_ptr<T> & std::unique_ptr<T>::operator=(std::unique_ptr<T> && rhs) is used, and during copy construction.

#include <memory>

int GUID = 0;       

typedef struct T_s {
    const char * value;
    int id;

    T_s(const char * value) : value(value), id(GUID++) {
        printf("CONSTRUCT\t(GUID %i): %s\tat address %p\n\n", id, this->value, &(this->value)); 
    };

    ~T_s() { 
        printf("DESTRUCT\t(GUID %i): %s\tat address %p\n\n", id, this->value, &(this->value)); 
    };
} T;

void DestructorTest() {

    // default construction of T, default constructon of unique_ptr
    std::unique_ptr<T> A(new T("ctor"));        
    printf("A->value ==\t(GUID %i): %s\tat address %p\n\n", A->id, A->value, &(A->value));

    // default construction of T, copy construction of unique_ptr
    std::unique_ptr<T> B = std::make_unique<T>(T("cctor"));     
    printf("B->value ==\t(GUID %i): %s\tat address %p\n\n", B->id, B->value, &(B->value));

    // default construction of T, move assignment of unique_ptr
    B = std::make_unique<T>(T("move")); 
    printf("B->value ==\t(GUID %i): %s\tat address %p\n\n", B->id, B->value, &(B->value));
}

The output of which is:

CONSTRUCT       (GUID 0): ctor  at address 01188AF0

A->value ==     (GUID 0): ctor  at address 01188AF0

CONSTRUCT       (GUID 1): cctor at address 00F6F6A8

DESTRUCT        (GUID 1): cctor at address 00F6F6A8

B->value ==     (GUID 1): cctor at address 01188A10

CONSTRUCT       (GUID 2): move  at address 00F6F698

DESTRUCT        (GUID 1): cctor at address 01188A10

DESTRUCT        (GUID 2): move  at address 00F6F698

B->value ==     (GUID 2): move  at address 01188A80

DESTRUCT        (GUID 2): move  at address 01188A80

DESTRUCT        (GUID 0): ctor  at address 01188AF0

As shown, the constructor only gets called 3 times, while the destructor gets called 5 times. This is because of temporary variables leaving scope in addition to std::unique_ptr's destructor calls.

I tried the copy-and-swap idiom for my eNode<type> assignment operator and it seems to have resolved the std::string and std::unique_ptr<int> crashes.

Here is the rewritten eNode<type> assignment operator (excerpted from its class declaration):

eNode(eNode<type> && other)      : prev(nullptr), next(nullptr), data(std::move(other.data)) {};      // move constructor 
eNode(const eNode<type> & other) : prev(nullptr), next(nullptr), data(other.data) {};               // copy constructor

// the input copy calls the appropriate constructor first
eNode<type> &   operator=(eNode<type> other) {          
                    std::swap(data, other.data);
                    return *this;
                };

SOME NOTES

  • A part of me doubts this would hold up if the template were eDeque<eDeque<int *>> or the like.
  • I agree with @Quuxplusone that direct eNode<type> reassignment is not how a deque should be used, but I was curious enough about memory management and move semantics that I had to try, for science. I've since marked the eNode<type> constructors that take eNode<type> parameters as deleted. I believe this will aid in preventing any accidental attempts at such a thing.
  • This answer will be edited if it turns out there are some strong exception safety or memory leak issues.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.