Appropriate DS for implementing worklist

Hi,

I am writing an analysis which requires creating worklist of basic blocks. The worklist should be in FIFO order. I checked SmallVector (and similar others) and found out this is working in LIFO order when I use the functions push_back and pop_back_val to insert and delete elements in the worklist.

Can someone suggest an appropriate DS to implement my worklist. Note: I am not concerned about efficiency here.

If you don’t care about efficiency you can push (or at least insert) at the front of a(small or otherwise) vector.

Thank you David for prompt reply.

I tried with SmallVector. I inserted elements with push_back().

But when I retrieve elements using pop_back_val the elements are returned in reverse order of insertion (I mean like LIFO order).

I need this to be FIFO order. How to achieve that?

Regards,
Rekha

Thank you David for prompt reply.

I tried with SmallVector. I inserted elements with push_back().
But when I retrieve elements using pop_back_val the elements are returned
in reverse order of insertion (I mean like LIFO order).
I need this to be FIFO order. How to achieve that?

push_back and pop_back both act on the "back" or "end" of the vector, so
you'll get LIFO behavior if you use them in that way

For LIFO you need to either insert at the front and pop from the back or
insert at the back and pop from the front.

You can insert at the front using the insert member function (
http://llvm.org/docs/doxygen/html/classllvm_1_1SmallVectorImpl.html#af622128e353515efebccad40eae495cb)
and passing the begin iterator.

How about a std::deque? push_back(), front(), pop_front() are what you need. They're also very efficient.

It worked.

Thank you :slight_smile:

Rekha