3
\$\begingroup\$

I’m moving from c98 to c++14 and I’m trying to figure out how to write move correctly.

I just wrote the simplest list with no functionality, just testing the construction and copy behavior. I would love to get an input as to what I can improve

Thanks

#ifndef EXERCIS_SIMPLELIST_H
#define EXERCIS_SIMPLELIST_H

#include <algorithm> //std::swap
#include <ostream>
#include <initializer_list>

namespace simple
{


template<typename T>
class SimpleList
{
public:
    struct Node
    {
        T m_data;
        Node* p_next = nullptr;
    };

public:

    SimpleList() = default;

    explicit SimpleList(const std::initializer_list<T>& il)
        : SimpleList()
    {
        auto iter = il.begin();
        pHead = new Node{*iter};
        ++iter;
        auto node = pHead;
        for (; iter < il.end(); ++iter) {
            node->p_next = new Node{*iter};
            node = node->p_next;
        }

        mSize = il.size();
    }

    ~SimpleList()
    {
        clear();
    }

    SimpleList(const SimpleList& rhs)
        : SimpleList()
    {
        pHead = new Node{rhs.pHead->m_data};
        auto node = pHead;
        auto rhs_node = rhs.pHead;
        while(rhs_node = rhs_node->p_next){
            node->p_next = new Node{rhs_node->m_data};
            node = node->p_next;
        }
        mSize = rhs.mSize;
    }
    SimpleList& operator=(const SimpleList& rhs) noexcept
    {
        auto tmp{rhs};
        swap(*this, tmp);

        return *this;
    }

    SimpleList(SimpleList&& rhs) noexcept
        :SimpleList()
    {
        swap(*this, rhs);
    }

    SimpleList& operator=(SimpleList&& rhs) noexcept
    {
        swap(*this, rhs);

        return *this;
    }


    void clear()
    {
        if(!pHead){
            return;
        }
        auto node = pHead;
        while(node = node->p_next)
        {
            delete pHead;
            pHead = node;
        }
        mSize = 0;
        pHead = nullptr;
    }

    auto empty() const  { return mSize == 0; }
    auto size() const   { return mSize; }


    //T should support op==, op!=
    bool operator== (const SimpleList& rhs) const
    {
        if(!pHead || !rhs.pHead || mSize != rhs.mSize){
            return false;
        }
        auto this_node = pHead;
        auto rhs_node = rhs.pHead;

        while(this_node && rhs_node){
            if(this_node->m_data != rhs_node->m_data){
                return false;
            }
            this_node = this_node->p_next;
            rhs_node = rhs_node->p_next;
        }

        return true;
    }
    bool operator!= (const SimpleList& rhs) const {
        return !(*this == rhs);
    }
    friend void swap(SimpleList& rhs, SimpleList& lhs) noexcept
    {
        using std::swap;
        swap(rhs.pHead, lhs.pHead);
        swap(rhs.mSize, lhs.mSize);
    }

    //T should support operator<<
    friend std::ostream& operator<<(std::ostream& os, const SimpleList& sl)
    {
        os<<"list "<<sl.mSize<<": {";
        auto node = sl.pHead;
        while(node)
        {
            os<<node->m_data<<(node->p_next ? ", " : "");
            node = node->p_next;
        }
        os<<"}\n";
        return os;
    }
private:
    Node* pHead = nullptr;
    std::size_t mSize = 0;
};

}//namespace simple
#endif //EXERCIS_SIMPLELIST_H

Some simple sanity tests

#include <gtest/gtest.h>
#include <gmock/gmock.h>
#include <iostream>
#include "../SimpleList.h"

using namespace simple;
using namespace std;

TEST(CTOR, simple_ctor_list)
{

    SimpleList<int> s0;
    SimpleList<int> s1{1, 2, 3, 4};
    cout<<s0<<s1;

}

TEST(CCTOR, simple_cctor_list)
{
    SimpleList<int> s0{1, 2, 3, 4};
    SimpleList<int> s1{s0};
    cout<<"s1: "<<s1<<"so: "<<s0;
}

TEST(EQUAL, simple_equal_list_test)
{
    SimpleList<std::string> s0{"hello", "world"};
    SimpleList<std::string> s1{s0};
    SimpleList<std::string> s2{};
    EXPECT_TRUE(s0 == s1);
    EXPECT_TRUE(s1 != s2);
    SimpleList<std::string> s3{"hello"};
    EXPECT_TRUE(s1 != s3);

}

TEST(MOVE_CCTOR, simple_move_cctor_list)
{
    SimpleList<std::string> s0{"hello", "world"};
    SimpleList<std::string> s2{s0};
    SimpleList<std::string> s1{std::move(s0)};


    EXPECT_EQ(s2, s1);
}


TEST(MOVE_ASSIGNMENT, simple_move_assignment_list)
{
    SimpleList<std::string> s0{"hello", "world"};
    SimpleList<std::string> s1{s0};
    SimpleList<std::string> s2;
    s2 = std::move(s1);

    EXPECT_EQ(s2, s0);
}
\$\endgroup\$
5
\$\begingroup\$
  1. SimpleList should be named ForwardList or similar to signal that it is only singly-linked.

  2. Why is SimpleList::Node public? It's a bona-fide implementation-detail AFAICS.

  3. I prefer always putting the links first, as it marginally helps with uniformity, especially when getting to implement the iterator-interface.

  4. Putting the dtor in the middle of the ctors is curious. Common order is ctors, op=, dtor, others, but those with the same name are virtually always grouped together.

  5. I have never seen a std::initializer_list-ctor marked explicit. I doubt it will work as advertised.

  6. I'm missing construction from iterators.

  7. A proper iterator-interface greatly simplifies comparison, and output to stream. With construction from iterators, copy-ctor and list-ctor also become obvious.

  8. Using ctor-delegation is quite useless when the delegatee and the empty mem-initializer-list do the same thing. Though it doesn't hurt.

  9. Your attempt at hungarian notation is not appreciated. It doesn't make the code easier to read, and you are very inconsistent in how you apply it. I will from now on pretend you desisted.

  10. clear() can be simplified. As a bonus, the compiler will have an easier time optimising it:

    void clear() noexcept {
        count = 0;
        auto p = std::exchange(head, nullptr);
        while (p)
            delete std::exchange(p, p->next);
    }
    
  11. Your op== is surprising. Specifically, it doesn't consider two empty lists equal.

  12. Is there any kind of pattern behind choosing return-type-deduction or being explicit for the members? Because it seems pretty arbitrary.

  13. Your move-ctor relies on the compiler fully inlining and then optimizing it for best performance, but that should be fine.

  14. You shouldn't import big amorphous namespaces into the global scope, as it can break the build or change the codes meaning at the drop of a hat. As you only did it in the test-code, the damage should at least be pretty well-contained.

\$\endgroup\$
  • \$\begingroup\$ Thanks! loved the clear method. Can you explain 13 though? what did you mean that im relying on the complier to fully inline and optimize? \$\endgroup\$ – Peretz Levinov Jun 29 at 8:46
  • \$\begingroup\$ @PeretzLevinov I saw somethink from a maintainer of libstdc++ or libc++, where he said that it might make a difference. Trouble is, I've long lost the reference, and cannot recall circumstances or age of the quote. Truthfully, I expect it to be irrelevant by now, but I'm not quite absolutely sure. \$\endgroup\$ – Deduplicator Jun 29 at 18:11
2
\$\begingroup\$

Design

I design my class exactly the same. The main difference I see is that you have a single friend void swap() standalone function where I break this into two separate functions. I have a member swap that does all the work and then a standalone swap that simply calls the member function.

 class X
 {
      public:
          void swap(X& rhs) noexcept {}
 };
 void swap(X& lhs, X& rhs) {lhs.swap(rhs);}

Code Review

Why are you exposing implementation details about the internals of the class?

public:
    struct Node
    {
        T m_data;
        Node* p_next = nullptr;
    };

This is a bug:

        auto iter = il.begin();
        pHead = new Node{*iter};

The list can easily be empty.

#include <iostream>
#include <initializer_list>

struct X
{
        explicit X(std::initializer_list<int> const& x) { std::cout << x.size() << "\n";}
};

int main()
{
    X   a{1};
    X   b{};
}

> ./a.out
1
0

Normally when you use iterators you only compare with !=. It will work with an initializer list. But I can see this causing cut/paste errors when you also start supporting std::list<T> in the future.

        for (; iter < il.end(); ++iter) {
        }

Again we are assuming the other list has at least one node.

    SimpleList(const SimpleList& rhs)
        : SimpleList()
    {
        pHead = new Node{rhs.pHead->m_data};

This loop looks more suitable with a for(;;) loop.

        while(rhs_node = rhs_node->p_next){
            node->p_next = new Node{rhs_node->m_data};
            node = node->p_next;
        }

Don't think you can gurantee noexcept here. You use the Copy Constructor which itself calls new which can throw. Thus you can't guarantee that no exception will be thrown during construction.

SimpleList& operator=(const SimpleList& rhs) noexcept

Looks like a good place for a for(;;) loop.

        auto node = pHead;
        while(node = node->p_next)
        {
            delete pHead;
            pHead = node;
        }

I see you are looking to return a quick fail.
But I think this is flawed. Two empty list should compare equal should they not?

        if(!pHead || !rhs.pHead || mSize != rhs.mSize){
            return false;
        }

TEST(CCTOR, equalityOfEmptyList)
{
    SimpleList<int> s0{};
    SimpleList<int> s1{};
    EXPECT_TRUE(s0 == s1);
}
\$\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.