2
\$\begingroup\$

Using feedback from my previous implementation I'm writing a very simple Queue of struct Nodes with only these methods get_front(), get_back(), pop_front(), push_back(), and a ostream friend method. I want this to be reviewed as production code and is to be treated as code that could be used in an interview. I'm really curious about the approach I've taken here to keep track of the size, empty status, and back and front pointers. I resolved some of the padding issues in my data structures, not sure if that's over kill or would look good to show my C++ proficiency.

I'd like to know also if my member functions for the Queue have any edge cases I am not catching and any improvements I can make to run time efficiency overall. Anyway I can simplify this code further with c++11 features, shorter variable names or smart pointers would be appreciated.

Lastly if you optionally would like to share the memory/space complexity for my code that would be a huge help! I have noted some examples in the member data of my Node struct.

#include <iostream>
#include <string>

class Queue
{
    private:
        struct Node
        {
            int data;
            char padding[4];
            Node* previous;
            Node(int data) : data(data), previous(nullptr) { }
        };
        int _size{0};
        char padding[4];
        Node* _back{nullptr};
        Node* _front{nullptr};
    public:
        ~Queue() {
            while(_front) {
                auto n = _front;
                _front = _front->previous;
                delete n;
            }
        }

        void pop_front() {
            --_size;
            if (!_back) {
                throw std::out_of_range{"cannot get data from empty queue"};
            }
            else if (_front->previous) {
                auto danglingptr = _front;
                _front = _front->previous;
                delete danglingptr;
            }
            else {
                _front = _back = nullptr;
            }
        }
        void push_back(int data) {
            auto n = new Node(data);
            ++_size;
            if (!_back) {
                _front = _back = n;
            }
            else {
                _back->previous = n;
                _back = _back->previous;
            }
        }
        int get_back() { return _back ? _back->data : 0; }
        int get_front() { return _front ? _front->data : 0; }
        std::size_t get_size() { return _size; }
        bool is_empty() { return _size > 0; }

        friend std::ostream& operator<<(std::ostream& os, const Queue& queue) {
            int size = queue._size;
            if (size == 0) {
                os << "Queue is empty";
            }
            else {
                for (int i = 1; i < size*2; i++) { os << "_"; }
                os << std::endl;
                std::string queue_string = "";
                auto current = queue._front;
                for(; current; current = current->previous) {
                    queue_string =  std::to_string(current->data) +  " " + queue_string;
                }
                os << queue_string << std::endl;
                for (int i = 1; i < size*2; i++) { os << "_"; }
            }

            return os;
        }
};

int main()
{
    Queue queue;

    queue.push_back(9);
    queue.push_back(8);
    queue.push_back(7);
    queue.push_back(6);
    queue.push_back(5);

    std::cout << queue << std::endl;
    std::cout << "back is " << std::to_string(queue.get_back()) << '\n';
    std::cout << "front is " << std::to_string(queue.get_front()) << '\n';
    std::cout << "size is " << std::to_string(queue.get_size()) << "\n\n";

    queue.pop_front();
    queue.pop_front();
    queue.pop_front();

    std::cout << queue << std::endl;
    std::cout << "back is " << std::to_string(queue.get_back()) << '\n';
    std::cout << "front is " << std::to_string(queue.get_front()) << '\n';
    std::cout << "size is " << std::to_string(queue.get_size()) << "\n\n";

    queue.pop_front();
    queue.pop_front();

    std::cout << queue << std::endl;
    std::cout << "back is " << std::to_string(queue.get_back()) << '\n';
    std::cout << "front is " << std::to_string(queue.get_front()) << '\n';
    std::cout << "size is " << std::to_string(queue.get_size()) << "\n\n";

    queue.pop_front();
}
\$\endgroup\$
4
\$\begingroup\$

This is going to be somewhat more conversational on things to do or don't looking at it as if you'd shown this in the course of an interview. Any response with respect to an interview example would always take into account the amount of experience that the candidate is claiming to have. Note, I am also writing this in the way I am looking at the code, noticing superficial things first and then looking closer and closer at the implementation.

My first question would be about the padding, and if you wouldn't be able to answer as to why it is important here or why you added it (saying that there was a warning wouldn't be a sufficient answer), what it does, and what the issues are whether this works under 32 and 64 bit architectures, etc... . If you can't answer these questions it would be a bad sign for me. For interviews don't use features in your code that you can't explain.

I'd definitely ask you why you didn't use std::unique_ptr as this would remove large swaths of the code, it's a feature of c++11 in an interview i'd probably expect to see that. I'd probably also ask whether you thought about making the interface closer to the standard library calls e.g. get_back() vs back() or is_empty() vs empty().

Note that most of these are actually superficial but they are really easy to pick up on a first look, without even having to think about if the code is correct or not (which would be more work on my side) there are already a ton of things to talk about that might let me exclude you as a candidate. The quicker you can be excluded, the less work for everybody.

So on closer look, you'd get dinged for returning a valid piece of data on failure in get_back() and get_front(). Here you are return 0 if there aren't any items, this is really a big issue. This would start a discussion on error handling in general, what could you have done, what did you do just a few lines above that section.

I see a bug in pop_front() first I'd ask you to look at it and we'd try to find it together. You decrease size before the check if the queue is empty, this would make size incorrect. Looking at the bug also made me notice that you never tested popping from the empty list. Now that I have seen the first bug, i'm looking closer and there is another bug that leaks the first nodes memory if its the last item. If we haven't talked about unique_ptr up to this point, I'd ask now.

Depending on how your responses are we might talk about some general points, i'd comment that you're probably putting out too much text on <<, i'd ask if the to_string() in the demo code is really necessary. I'd comment on your style for member variables (pet peeve). Leading underscores are iffy at best with regard to their use, the standard reserves names with leading underscores in combination with capital letters and double underscores, so you're just one keystroke away from code that violates that. I'd also remark that the test code could have used some assertions rather than just output, this would have made things much more like a unit test, and if there is time we might talk about what you know about unit testing.

When I interview, i take any issue I see as an opportunity to talk about what caused it, what might remedy it, why the candidate did this. The answers to these questions may matter more than the actual code.

\$\endgroup\$
  • \$\begingroup\$ Thanks for all the feedback Harald. For padding I would say I added this to properly align the bits for my data structures in memory. Without padding there would be wasted space (at large scale this a big issue) in the memory addresses where my logic is contained and performance is improved by this as well. I can not answer if this works on different bit architectures, but would like to understand that more. \$\endgroup\$ – greg Mar 15 at 18:58
  • \$\begingroup\$ You wasted the exact same space as the compiler ... coliru.stacked-crooked.com/a/beb5efd219f81262 \$\endgroup\$ – Harald Scheirich Mar 15 at 19:38
  • 1
    \$\begingroup\$ The padding is still wasted space, a solution saving space could have been to use a long for the node payload that would have in that case used the same 4 byte that you used for padding. Sometimes the answers here are not a good fit for the person asking the question. You don't necessarily want to tell a somebody trying to crawl that they should be running instead, all in good time. But I realize it can be hard to figure that out on the readers side. \$\endgroup\$ – Harald Scheirich Mar 15 at 19:48
  • 1
    \$\begingroup\$ I thought about the purpose of the -Wpadded switch. And I would probably use it to check my code to see where padding occurs and then try to rearrange the struct to reduce the amount of padding e.g if you have int;int*;int that would be padded but int;int;int* wouldn't. \$\endgroup\$ – Harald Scheirich Mar 18 at 13:03
  • 1
    \$\begingroup\$ Unless you have a specific reason to manually introduce the padding, don't. The compiler is already doing it, you are worrying about this too much.Manually padding might be important in applications where you need to be sure about the binary layout of the data that you are producing. Worry about the bugs in your code rather than a warning given by an optional flag. \$\endgroup\$ – Harald Scheirich Mar 20 at 18:12

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.