Sign in to follow this  

vector or list for message queue

This topic is 4197 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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;
	}

	messageType		msgType;
	void			*pMsgData;
	Entity			*pTargetEntity;
};

Message *pMsg = new Message;
m_messageQueue.push_front(pMsg);


Any tips on this?

Share this post


Link to post
Share on other sites
If you need to add/remove elements at the end use std::vector
If you need to add/remove elements at both the begining and end use std::deque
If you need to add/remove elements anywhere use std::list

Edit: changed recommendation for ast item from std::deque to std::vector

[Edited by - Nitage on June 16, 2006 4:31:10 AM]

Share this post


Link to post
Share on other sites
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];



or


std::vector<Message*>::iterator iter;
for(iter = m_messageQueue.begin(); iter != m_messageQueue.end(); iter++)
{
Message *pMsg = static_cast<Message*>(*iter);
if(criteriaFound)
return pMsg;
}


Share this post


Link to post
Share on other sites
Quote:
Original post by dalleboy
Why 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.

Share this post


Link to post
Share on other sites
Quote:
Original post by DarkZoulz
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?
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.

Share this post


Link to post
Share on other sites

This topic is 4197 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this