3
\$\begingroup\$

I tried implementing a queue using std::vector, using some properties of vector class. Is there scope for further improvement in my code, to make it more efficient?

#include<bits/stdc++.h>
using namespace std;
vector<int> q;

 void push(int d){
   q.insert(q.end(),d);
 }

 void pop(){
 q.erase(q.begin());
 }

 int front(){
 return *q.begin();
 }

 int main(){
    push(1);
    push(2);
    push(3);
    push(4);
    pop();
    cout<<front()<<endl;
     for(int i=0;i<q.size();i++) cout<<q[i]<<" ";
  }
\$\endgroup\$
4
\$\begingroup\$

There are a number of things that could be improved here, and none of them have to do with the efficiency of the program. The problems with this code are more fundamental.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Don't use #include <bits/stdc++.h>

This is poor programming practice. Here's why.

Eliminate global variables where possible

The q variable is global but should really be in main or still better, see the next suggestion.

Create a C++ object

Whenever you have some data structure and associated actions (such as push and pop in this case), you should be thinking object. In this case, it's quite simple to create an object from the code you have. I'll leave that fun to you.

Use consistent formatting

The code as posted has inconsistent indentation which makes it hard to read and understand. Pick a style and apply it consistently.

Use more whitespace to enhance readability of the code

Instead of crowding things together like this:

 for(int i=0;i<q.size();i++) cout<<q[i]<<" ";

most people find it more easily readable if you use more space:

 for (int i=0; i < q.size(); i++) {
     std::cout << q[i] << " ";
 }

Use standard classes

Finally, there's the obvious: one could use std::queue. I am assuming that you did not because you are still learning C++ and wanted to try to create a queue yourself. That's fine as a programming exercise, but of course in real code, it's almost always better to use part of the standard library.

\$\endgroup\$
3
\$\begingroup\$

The style issues have already been covered. There is one question remaining:

to make it more efficient?

Imagine there are a million items in your queue (and therefore the vector). Now imagine popping an item off the front.

The implementation calls std::vector::erase(Iterator).

Looking at some documentation for this method on cppreference.com (a reasonable first port of call):

https://en.cppreference.com/w/cpp/container/vector/erase

We are interested in the method's complexity. The documentation has this to say:

Linear: the number of calls to the destructor of T is the same as the number of elements erased, the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements

It means we're going to destroy one int (zero cost) followed by 999,999 assignments as the remaining items are shuffled to the beginning of the vector.

For a vector of ints this may not be a huge problem, depending on your application. In the general case, doing a million of anything every time we dequeue a value has a bad feeling about it. For a vector of something more heavyweight it could start to become a noticeable performance burden.

We have a number of ways to go, depending on what trade-offs we are prepared to make.

We could, rather than maintain one huge vector, perhaps maintain a list of structures that represent a 'chunk' of 10 items. Such a chunk would be able to record where the first and last item is within the vector. Once we determine that the chunk is no longer needed (it's become empty), we could store it in a 'free chunk cache' or destroy it. Either way we'd remove it from the beginning of the list. We might even want the chunk size to adapt itself to reduce memory usage while maintaining good data locality - however these concerns are probably beyond the scope of your question.

pop() would now be performed in O(1) time, which for this particular operation would now be (literally) an order of magnitude better.

However, the trade-off would be that random-access operations on your queue (if you need them) would become an order of magnitude worse.

std::deque is the standard multi-purpose queue container. If you look at the documentation you can see the complexity tradeoffs in action. You will also notice that this container does not allow random-access operations.

This suggests that the implementation will be along the lines of what I describe above.

for reference: https://en.cppreference.com/w/cpp/container/deque

\$\endgroup\$
2
\$\begingroup\$

There are a few weaknesses in your code, that @Edward already pointed out, such as using namespace std and, worse, #include <bits/stdc++.h>. But I really like that you tried to rely on std functionalities. Building your queue upon std::vector is almost right.

Delve further into the STL

A queue is a "FIFO" container: the first element in is also the first element out. It means that you won't discard elements from the end you insert them into: so the right container isn't std::vector, which is optimized for insertion/deletion of the last element, but std::deque, which provides fast insertion/deletion at both ends. With std::vector, you need to reallocate memory every time you delete the front member, and that's inefficient.

Make your own deque

Of course, you might not want to use std::deque directly, especially if you're looking for a good exercise. Then I'd suggest you implement your own. As cppreference says:

typical implementations use a sequence of individually allocated fixed-size arrays

So, still relying on the STL, we can use an std::list of std::arrays.

Let's begin with that:

template <typename T, std::size_t N = 5>
// N is the size of the statically allocated arrays
class Queue { 
    using block = std::array<T, N>; // cosmetic alias
    using iterator = typename block::iterator;

    public:
    Queue();
    void push(const T& value);
    void pop();
    T front() const;

    private:
    std::list<block> storage; // our sequence of arrays
    iterator first, last; // pointers to first and last elements
};

So we have a class with two template arguments: the type your deque will contain, and the size of inner arrays. The user might want big arrays if speed is more important than memory, or the opposite. I've chosen a default size without putting much thought into it.

block and iterator are aliases; in this case, I only use them to make the code more readable.

Now let's implement the different functions:

template <typename T, std::size_t N>
Queue<T, N>::Queue() { 
    storage.push_back(block{});
    first = std::begin(*std::begin(storage));
    last  = first; // last == first <=> empty queue
}

No difficulty here, a simple constructor ensures the queue is ready to use by allocating a first array, and initializing the iterators to the first and last element. They're equal, meaning the queue is empty.

template <typename T, std::size_t N>
void Queue<T, N>::push(const T& value) {
    if (last == std::end(*std::rbegin(storage))) { // rbegin!!
        storage.push_back(block{});
        last = std::begin(*std::rbegin(storage));
    }
    *last++ = value;
}

In order to push a new element, you need to be sure that there's some room left. last is increment after every push, so you need to verify it hasn't reached the end of the last allocated array. std::rbegin returns an iterator to the last element (!= std::end, which returns an iterator past the last element).

If there isn't any room left, we add another block to our sequence.

Then pop is a mirror, and front doesn't present any difficulty:

template <typename T, std::size_t N>
void Queue<T, N>::pop() {
    if (++first == std::end(*std::begin(storage))) {
        storage.pop_front();
        first = std::begin(*std::begin(storage));
    }
}

template <typename T, std::size_t N>
T Queue<T, N>::front() const { // const here means you don't modify your object
    return *first;
}

A working example

to toy with:

#include <iostream>
#include <list>
#include <array>

template <typename T, std::size_t N = 5>
class Queue { 
    using block = std::array<T, N>;
    using iterator = typename block::iterator;

    public:
    Queue();
    void push(const T& value);
    void pop();
    T front() const;

    private:
    std::list<block> storage;
    iterator first, last;
};

template <typename T, std::size_t N>
Queue<T, N>::Queue() {
    storage.push_back(block{});
    first = std::begin(*std::begin(storage));
    last  = first;
}

template <typename T, std::size_t N>
void Queue<T, N>::push(const T& value) {
    if (last == std::end(*std::rbegin(storage))) {
        std::cout << "requiring new storage" << '\n';
        storage.push_back(block{});
        last = std::begin(*std::rbegin(storage));
    }
    *last++ = value;
}

template <typename T, std::size_t N>
void Queue<T, N>::pop() {
    if (++first == std::end(*std::begin(storage))) {
        std::cout << "freeing unused memory" << '\n';
        storage.pop_front();
        first = std::begin(*std::begin(storage));
    }
}

template <typename T, std::size_t N>
T Queue<T, N>::front() const {
    return *first;
}

int main() {

    Queue<int> queue;
    queue.push(5);
    queue.push(4);
    queue.push(3);
    queue.push(2);
    queue.push(1);
    queue.push(0);
    queue.push(-1);
    queue.push(-2);
    for (auto x = 0; x < 8; ++x) {
        std::cout << queue.front() << '\n';
        queue.pop();
    }

}
\$\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.