   an ADT that can...
  Is there an ADT (from STL lib) where items can be popped out from anywhere, then the whole list is shifted. but items pushed must go to the back?edit: oh wait...does std::list do this...? let's see.[edited by - alnite on February 4, 2004 12:20:17 AM]
  No. std::list you can push items on the front or back or insert in the middle. I don''t think any of the standard library classes do what you want. That is none of them support your "only push on the back" requirement and the "erase anywhere" requirement at the same time. ;  well, if they support push_back and push_front doesn't matter, I can use only push_back. but erase anywhere is the most important.I'll try using vector, but how do I erase an item?   [edited by - alnite on February 4, 2004 12:27:49 AM];  vector::erase() ;quote:Original post by SiCrane   vector::erase()   sorry for the stupid question. I shouldn't ask. thanks. but here's what I got after searching on the net:from gcc.gnu.orgquote:Note This operation could be expensive and if it is frequently used the user should consider using std::list.expensive. that's scary. I might be using this a lot. I look at std::list, it does have the same function, but I need to iterate through the list to get there.so, which one is faster, std::list::erase() with iteration (it's not a huge list, only about 12 items maximum), or std::vector::erase() ?   [edited by - alnite on February 4, 2004 12:35:02 AM];  It really depends on your usage pattern. I can think of patterns where list would be faster and I can think of patterns where vector would be faster. Why not try them out and see for yourself? ;  maybe it's not that important which one is faster. there are only 12 items maximum anyway, but there will be about 7 lists. And it is very   unlikely that all items get deleted.I'll use list. since erase() requires an iterator, and I have no idea how to obtain the iterator of any given position, so I'll end up traversing the list anyway.edit:I figured it out. thanks Xai, you gave me some insight on how to do it.  [edited by - alnite on February 5, 2004 1:10:01 AM];  you should never use a vector if you plan to insert or remove often ... and DEFINATELY not if you plan to insert or remove from anywhere but the back often ...The vector is for most efficient random access.The deque is for really efficient random access, plus good efficiency adding / removing from either end.The list is for most efficient adding / removing from anwhere, but least efficent random access or finding / sorting.All 3 elements has very efficient linear access, with the vector''s being slightly more efficient (at least 1 lookup less per step - IF you use iterators).P.S.  Always use iterators if you need really efficient sequential access .. NOT integer indexes - although usually this difference doesn''t matter enough to care. ;  i wouldn''t expect to find abstract data types in the stl....you''ll have more luck with concrete data types there =) 