Implementing a FIFO with a std vector

[zenith bison]

Hi, during an interview I've been asked to implement a FIFO with a vector
I said I dont think it's a good idea because the complexity of inserting at the front in a std vector is linear
He insisted on using a std vector, so I'm guessing there's a trick I cannot see.

I thought about inserting at the end (push_back) and if i want to delete, i can increment a pointer that points to the beginning of the vector, but I don't have infinite memory
Any ideas ?

[restive arch]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

[open berry]

You could look at what std::deque does. I think the trick is that it uses 2 vectors, one for reading, one for writing. Once the reading vector is out of elements it swaps vectors.

[amber plover]

i thought it was a linked list of small arrays

regardless, i think the "inset at end, increment start pointer" is still a good option (at least in my opinion)

you could maybe run a "cleanup" process when the vector will be reallocated (capacity == size - 1) and create a new buffer with the excess front elements removed

that way, you won't run out of memory (because there will be cleanups), and it will be relatively efficient (because insertion is amortized constant and the memory will be reallocated regardless, and deletion is constant)

the downside is that you aren't really using vector, more like re-implementing it in a way

[fiery pine]

@zenith bison sorry for asking this question , was there any option to implement it with C ? From scratch? I’m asking this cuz I m learning DSA in C and most probably I won’t do dSA again in c++ , pls suggest

[zenith bison]

I see that's a good idea

[zenith bison]

well my interview was in C++, so they asked me to use the STL

I guess you can implement a queue with a vector in C from scratch but you will have to implement your own vector data structure because there's no built-in vector DS in C

[open berry]

That's a bit more complicated in C++ because you need to run the destructor when removing an element, can't just increment a pointer. std::vector already does that.

[open berry]

You should not need to reallocate much because you reuse the existing memory. Sometimes it reallocates because the queue grew bigger than it had memory for, but assuming the queue doesn't grow to infinity it will eventually stop reallocating.

[zenith bison]

but we don't need to remove the element, we can just increment the start index, just to simulate the behavior of a fifo

no ?

[open berry]

No

When I put a Button in the fifo and I do a pop_front and the button doesn't disappear because the fifo didn't delete the Button then I'd call that an incorrect implementation of a fifo.

If you have a queue of ints then it doesn't matter.

[zenith bison]

right, I see your point

[zenith bison]

!solved

[restive arch]

Thank you and let us know if you have any more questions!

[fiery pine]

Yes right. Thanks

[amber plover]

that's true i guess

[zenith bison]

during my interview it was an example of a queue with integers

but yeah I agree, if it's an object then it's not the same thing

[rich lodge]

@zenith bison the traditional method to implement a FIFO if you must use a std::vector as the container would be using a circular buffer, as vaguely described earlier

if you need to support complex types then you need to use a std::vector<std::byte> as just a raw memory container, and construct/destroy objects in it yourself without using push_back etc., the vector is just a memory store

(by that point you're probably better off using a std::unique_ptr instead, because the vector of bytes gets even more complicated due to alignment, but interview Qs are going to interview)