Quote:Original post by crucifer
I am currently coding in C++ and I need some storage solution (list/vector/queue ... etc) that can do :
-inserts values at random locations
-read values at random locations
-pop of the first or last values
Preferably, if I could do any of these operations in O(1), I would be glad.
Anybody has a guess ?
You want a deque. You are incorrect is calling it a "list that's bidirectional", list is a linked list that is bidirectional ("doubly linked" is the more common term). slist, which isn't standard, is a single direction list ("singly linked" is the more common term). deque is a "double ended queue". It's usually pronounced "deck" and that's how you should think of it, like a deck of cards. Each card is an array of elements. If you want to insert at a random location, you pick the card with the location you need and add the element to that array. If that card is full, you just insert another card. If you want to read values at random locations, you go to the card with that location and read it. Popping a first or last value is easy, just move the "begin" pointer one element forward (pop_front) or the "end" pointer one element back (pop_back). It's designed to do what you want. Granted, not O(1), but I believe it's amortized behavior is O(1).
So, why vector and list? Because they have smaller constants. Where the constant dominates, or where you have only need of one of those behaviors, they will outperform deque.
By the way, are you sure it'll make a difference? Most people asking about such things are using such small collections that it won't make a noticeable difference.
