3
\$\begingroup\$

Regarding C++, I have an experience in writing only short non-object-oriented programs and competitive programming challenges.

I would like to get your feedback about my C++ style, design decisions, and overall quality.

The below is the implementation of a Singly Linked List containing a multiset of values of type T. Type T is required to provide equal to operator. The class supports the following operations:

  1. push a new value to the front of the list
  2. push a new value to the end of the list
  3. remove the first encountered occurrence of a given value
  4. check if the list contains a given value
  5. get the number of elements in the list
  6. print the list in a pretty format
  7. swap two lists

For the design, I decided to use both head and tail pointers to make both inserts constant time operations. For now, all pointers are raw pointers. The Node class is the internal class of LinkedList and an instance of LinkedList is responsible to delete its nodes. I decided to do that because this allows freeing the memory iteratively instead of recursively, which could cause problems if stack size is limited.

/* Singly Linked List by @pkacprzak */

#ifndef LINKED_LIST_HH__
#define LINKED_LIST_HH__

#include <ostream>

template<typename T>
class LinkedList {
public:
    LinkedList() {}

    LinkedList(const LinkedList& x) {
        auto cur = x.head;
        while (cur != nullptr) {
            pushBack(cur->val);
            cur = cur->next;
        }
    }

    LinkedList& operator=(const LinkedList& rhs) {
        LinkedList tmp(rhs);
        swap(*this, tmp);
        return *this;
    }

    ~LinkedList() {
        auto cur = head;
        while (cur != nullptr) {
            auto tmp = cur;
            cur = cur->next;
            delete tmp;
            tmp = nullptr;
        }
    }

    void pushFront(T val) {
        auto node = new Node(val);
        node->next = head;
        if (head == nullptr) {
            tail = node;
        }
        head = node;
        ++sz;
    }

    void pushBack(T val) {
        auto node = new Node(val);
        if (head == nullptr) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
        ++sz;
    }

    bool contains(T val) const {
        auto cur = head;
        while (cur != nullptr) {
            if (cur->val == val) {
                return true;
            }
            cur = cur->next;
        }
        return false;
    }

    void removeValue(T val) {
        if (head == nullptr) return;
        if (head->val == val) {
            auto cur = head;
            head = head->next;
            delete cur;
            if (head == nullptr) {
                tail = nullptr;
            }
            --sz;
        } else {
            auto cur = head->next;
            auto prev = head;
            while (cur != nullptr) {
                if (cur->val == val) {
                    prev->next = cur->next;
                    if (cur == tail) {
                        tail = prev;
                    }
                    delete cur;
                    --sz;
                    return;
                }
                prev = cur;
                cur = cur->next;
            }
        }
    }

    int size() const {
        return sz;
    }

    friend std::ostream& operator<<(std::ostream& os, const LinkedList& x) {
        auto cur = x.head;
        os << "[";
        while (cur != nullptr) {
            os << cur->val;
            if (cur != x.tail) {
                os << ",";
            }
            cur = cur->next;
        }
        os << "]";
        return os;
    }

    friend void swap(LinkedList& a, LinkedList& b) {
        std::swap(a.head, b.head);
        std::swap(a.tail, b.tail);
    }

private:
    struct Node {
        Node(T val_) : val(val_) {}
        T val;
        Node* next = nullptr;
    };
    Node* head = nullptr;
    Node* tail = nullptr;
    int sz = 0;
};
#endif
\$\endgroup\$
  • 1
    \$\begingroup\$ As I mentioned in the comment, please do not fix bugs mentioned in the answers. Let them pass. Only in extreme cases people will try to do something about it when upvoted answers are already present. On the side note: extensive testing before posting (and testing in general) will fix this. Try to learn how to write useful tests. May be google test will facilitate you. \$\endgroup\$ – Incomputable Sep 28 '17 at 17:26
  • \$\begingroup\$ Don't use double underscore. It is reserved for the implementation. LINKED_LIST_HH__ stackoverflow.com/a/228797/14065 \$\endgroup\$ – Martin York Sep 29 '17 at 19:38
4
\$\begingroup\$

Item 1. swap does not handle sz member

Item 2. No move constructor or operator= (no move semantic at all)

Item 3. Functions like contains get parameters by value - which is Ok for primitive types T and could be expensive for complex types

Item 4. No iterators - so not usable with algorithms. And also implementing something like remove_all is almost impossible - no indication of the remove success (except comparing size before and after), no possibility to continue scanning from the last location...

I suggest to take the std::forward_list http://en.cppreference.com/w/cpp/container/forward_list and try to emulate its API a lot closer then current attemp. Or justify your design choices explaining in more details why you think your change in the standard list API is superior to the stl approach.

Generally I like how the code looks and compiles. :)

\$\endgroup\$
  • \$\begingroup\$ Thaks a lot. Actually, the first item (member sz not swapped) is a bug, which I'll fix in the question. \$\endgroup\$ – pkacprzak Sep 28 '17 at 17:08
  • \$\begingroup\$ By no operator= do you mean no such operator with move semantic? \$\endgroup\$ – pkacprzak Sep 28 '17 at 17:11
  • 1
    \$\begingroup\$ @pkacprzak, there are 2 operator=, one copy, and one move. The latter has parameter T&& other. Move constructor is missing too. Though they are disabled by explicit implementation of rule of 3, so everything is ok for now. Also, please do not edit the part of code which was mentioned in the review, leave it as it is. \$\endgroup\$ – Incomputable Sep 28 '17 at 17:14
  • \$\begingroup\$ @Incomputable I didn't implement them on purpose because I wanted this implementation to be a basic one. Thanks for clarification \$\endgroup\$ – pkacprzak Sep 28 '17 at 17:16
  • 1
    \$\begingroup\$ @pkacprzak: Take heed of the iterators here, if your class exposed iterators and erase(it), both contain and remove could be implemented using the STL algorithms. Throw in insert(it, value) and the user can insert an item at a specific spot without having to pop items from the list, push value and push the items back. \$\endgroup\$ – Matthieu M. Sep 28 '17 at 18:01
3
\$\begingroup\$

First of all, let me tell you that learning how to implement standard library features is not the best way to learn postmodern C++ or standard library. Try to apply it on problems you've seen. Try to refactor some code into standard library compatible components.

Good things

  • Only necessary includes

    Well done. Having neat include list is one of the ways to achieve less compilation time and good dependency graph in general. One thing I would suggest is to bring <iosfwd> instead of <ostream>, as the former is even more compact.

  • Properly implemented rule of three.

    I'm not sure if rule of five was implemented correctly by accident, but the copy functions will disable move functions, so it is more or less all right.

  • Correct const qualifiers where appropriate.

    Not much to talk about this one, but in general, it is just another small piece which build up an insane code quality.

Things I didn't like

  • No element access

    By far, very few people will be happy with absence of the observer function.

  • No iterator support

    Iterators are fundamental concept. They are integral part of containers. Presence of iterators will eradicate following problems:

    • Ridiculous access complexity

      Users will just use the iterator to traverse back and forth, saving previous value if needed.

    • Rebuilding all of the algorithms from scratch

      With iterators, whole <algorithm> header will be available to them.

    • Storing index/reference/pointer to element.

      Iterator is an ultimate reference to an element in terms of containers. It provides a lot of information about container, element, location, etc.

    tl;dr: implement iterator support.

  • No passing by reference in push and delete

    It has multiple issues, which I hope you'll learn by yourself. This is the lesson one needs to learn the hard way. Might not be that important for now.

  • No emplace support

    Not all types are copy constructible. Especially from linked list, I would expect handling non-copyable types.

  • int for size.

    int is required to be only non less than 16 bit. Some computers can have 128 GiB of memory. Use std::size_t for elements in memory. It might be a good candidate for size in general, but not necessarily so.

  • Some other things that I don't think are that important.

Gotchas

Implement free swap, preferably put everything into namespace, so it wouldn't mess up ADL when people use it.

operator<< has a very big drawback: formatting! std::setw() applies only to first <<, then gets reset, which is very annoying. The output from a simulation got messed up, and I've been responsible for that. Fortunately matlab was confused enough to let us know before data got into paper...

\$\endgroup\$
  • \$\begingroup\$ Note: arguably, passing by value in push is better (since the value can be moved from). \$\endgroup\$ – Matthieu M. Sep 28 '17 at 17:57
  • 1
    \$\begingroup\$ @MatthieuM., not all types are moveable. So, it is still better to implement both copy and move versions. \$\endgroup\$ – Incomputable Sep 28 '17 at 18:32
  • \$\begingroup\$ "int is required to be only 16 bit" I'm sure you meant to say that it the only size constraint on int is that it must be 16 bits or wider. The way you've phrased it, IMO, is misleading. \$\endgroup\$ – Lightness Races in Orbit Sep 28 '17 at 23:38
  • \$\begingroup\$ @LightnessRacesinOrbit, yes, thank you. By the way, welcome back! Sorry for the last time. You would be a great contributor to our site. \$\endgroup\$ – Incomputable Sep 29 '17 at 2:48
  • \$\begingroup\$ @Incomputable: That's true, in absolute. In practice it's also incredibly rare that a type cannot be movable, so for beginners I'd advise "Want speed? Pass by value." to avoid overwhelming them with trivia. There are bigger fishes in the pond. \$\endgroup\$ – Matthieu M. Sep 29 '17 at 7:00

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.