1
\$\begingroup\$

I am trying out different data structures to learn more about smart pointers. I have created a queue implementation which has push, pop, front, back and size functions.

#include <iostream>
#include <memory>
#include <cstddef>

template<typename T>
class Queue
{
    std::unique_ptr<T[]> q_ptr;
    int front_idx = -1;
    int back_idx = -1;
    int capacity = 0;
public:
    Queue(std::size_t space)
    {
        q_ptr = std::unique_ptr<T[]>(new T[space]);
        capacity = space;
    }
    void push(T value);
    void pop();
    T front() const;
    T back() const;
    std::size_t size() const;
};

template<typename T>
void Queue<T>::push(T value)
{
    if(front_idx == -1)
    {
        front_idx++;
    }
    if(back_idx - front_idx + 1 == capacity)
    {
        std::cerr << "Queue full\n";
        return;
    }
    q_ptr[++back_idx] = value;
}

template<typename T>
void Queue<T>::pop()
{
    if(front_idx == -1)
    {
        std::cerr << "Empty queue\n";
        return;
    }
    q_ptr[front_idx++] = T{};
}

template<typename T>
T Queue<T>::front() const
{
    return q_ptr[front_idx];
}

template<typename T>
T Queue<T>::back() const
{
    return q_ptr[back_idx];
}

template<typename T>
std::size_t Queue<T>::size() const
{
    return back_idx - front_idx + 1;
}

int main()
{
    Queue<int> q1{20};
    q1.pop();
    for(int i = 0; i < 23; i++)
    {
        q1.push(i);
    }
    std::cout << "Queue size: " << q1.size() << "\n";
    std::cout << "Queue front: " << q1.front() << "\n";
    std::cout << "Queue back: " << q1.back() << "\n";
    q1.pop();
    std::cout << "Queue size: " << q1.size() << "\n";
    std::cout << "Queue front: " << q1.front() << "\n";
    q1.pop();
    std::cout << "Queue size: " << q1.size() << "\n";
    std::cout << "Queue front: " << q1.front() << "\n";
    q1.push(12);
    std::cout << "Queue size: " << q1.size() << "\n";
    std::cout << "Queue back: " << q1.back() << "\n";
}
  1. The attempt is to use unique_ptr as an array similar to a raw pointer. Is the usage and approach correct? Can it be improved?

  2. As far as I know, I cannot use shared_ptr this way in C++11 or C++14. Is this the best approach with shared_ptr?

\$\endgroup\$
4
\$\begingroup\$

Yes I think your usage of unique_ptr is correct. The only recommendation I would make is to use make_unique for construction:

explicit Queue(std::size_t space) : 
    q_ptr(std::make_unique<T[]>(space)), 
    capacity(space) {}

This answer provides motivation for its use. I've also used explicit to avoid implicit conversion from size_t to Queue. And I made use of a member initialization list.

I wrote the following tests using googletest:

TEST(QueueTester, testEmpty) {
    Queue<int> queue(0);
    EXPECT_EQ(0, queue.size());
}

TEST(QueueTester, testSingle) {
    Queue<int> queue(1);
    EXPECT_EQ(0, queue.size());
    queue.push(0);
    EXPECT_EQ(1, queue.size());
}

But neither passed. I corrected this by using the following:

int front_idx = 0;

And changing push:

template<typename T>
void Queue<T>::push(T value)
{
    if (back_idx - front_idx + 1 == capacity)
    {
        std::cerr << "Queue full\n";
        return;
    }
    q_ptr[++back_idx] = value;
}

I changed front and back to return references to the elements to allow the user to modify the contents. I also wrote overloads for returning const references to allow reading when the Queue is passed by const reference:

template<typename T>
T &Queue<T>::front()
{
    return q_ptr[front_idx];
}

template<typename T>
T &Queue<T>::back()
{
    return q_ptr[back_idx];
}

template<typename T>
const T &Queue<T>::front() const
{
    return q_ptr[front_idx];
}

template<typename T>
const T &Queue<T>::back() const
{
    return q_ptr[back_idx];
}

I further noticed that push, given a nonzero front_idx, will write past the end of the array pointed to by q_ptr. I took inspiration from this page and modified the code to store elements circularly around the array. Here is the final implementation:

#include <iostream>
#include <memory>
#include <cstddef>

template<typename T>
class Queue
{
    std::unique_ptr<T[]> q_ptr;
    int front_idx = 0;
    int back_idx = -1;
    std::size_t _size = 0;
    std::size_t capacity;
public:
    explicit Queue(std::size_t space) :
        q_ptr(std::make_unique<T[]>(space)),
        capacity(space)
    {
    }
    void push(T value);
    void pop();
    bool full();
    bool empty();
    T &front();
    T &back();
    const T &front() const;
    const T &back() const;
    std::size_t size() const;
};

template<typename T>
void Queue<T>::push(T value)
{
    if (full())
    {
        std::cerr << "Queue full\n";
        return;
    }
    back_idx = (back_idx + 1) % capacity;
    q_ptr[back_idx] = value;
    ++_size;
}

template<typename T>
bool Queue<T>::full()
{
    return _size == capacity;
}

template<typename T>
void Queue<T>::pop()
{
    if (empty())
    {
        std::cerr << "Empty queue\n";
        return;
    }
    q_ptr[front_idx] = T{};
    front_idx = (front_idx + 1) % capacity;
    --_size;
}

template<typename T>
bool Queue<T>::empty()
{
    return _size == 0;
}

template<typename T>
T &Queue<T>::front()
{
    return q_ptr[front_idx];
}

template<typename T>
T &Queue<T>::back()
{
    return q_ptr[back_idx];
}

template<typename T>
const T &Queue<T>::front() const
{
    return q_ptr[front_idx];
}

template<typename T>
const T &Queue<T>::back() const
{
    return q_ptr[back_idx];
}

template<typename T>
std::size_t Queue<T>::size() const
{
    return _size;
}
\$\endgroup\$
  • \$\begingroup\$ Thank you for the detailed answer. I am using C++11 in this case. So it does not have make_unique. But thank you for the suggestion. \$\endgroup\$ – skr_robo Sep 9 '18 at 14:28

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.