   vector or list for message queue
  Hi! i'm considering using a std::list to hold a queue of message pointers. Is this a bad choice? I've read that lists are faster than vectors if you add/remove elements to/from the beginning or middle. All the messages will be iterated and processed every tick.struct Message{Message(){pMsgData = NULL;pTargetEntity = NULL;}~Message(){if(pMsgData)delete pMsgData;}messageTypemsgType;void*pMsgData;Entity*pTargetEntity;};Message *pMsg = new Message;m_messageQueue.push_front(pMsg);Any tips on this?   
  If you need to add/remove elements at the end use std::vectorIf you need to add/remove elements at both the begining and end use std::dequeIf you need to add/remove elements anywhere use std::listEdit: changed recommendation for ast item from std::deque to std::vector[Edited by - Nitage on June 16, 2006 4:31:10 AM];Quote:Original post by NitageIf you need to add/remove elements at the end use std::dequeDon't you mean std::vector?   ;  Indexing a std::vector is faster than iterating through until finding what your looking for. Or will the vector do this anyway when I index it?Message *pMsg = m_messageQueue[index];orstd::vector<Message*>::iterator iter;for(iter = m_messageQueue.begin(); iter != m_messageQueue.end(); iter++){    Message *pMsg = static_cast<Message*>(*iter);    if(criteriaFound)   return pMsg;};  Why not a std::queue or a std::priority_queue?   ;Quote:Original post by dalleboyWhy not a std::queue or a std::priority_queue?These provide an interface, but underneath use another container to actually hold the data - queue defaults to std::deque and priority_queue defaults to std::vector. So you are still left with the choice of this underlying container. Nitage's advice should be useful.   ;Quote:Original post by DarkZoulzIndexing a std::vector is faster than iterating through until finding what your looking for. Or will the vector do this anyway when I index it?std::vector has to have contiguous storage, which means it's implemented as an array. Which also means that to access an element, you can just use the index. std::vector::iterator is usually optimized away by the compiler and turns it into an array lookup (or incrementing the pointer to the array element) anyway.But in your second example, it'll take O(n) time instead of O(1), which the first would take. So always go for the first when possible when using vectors.   