I'm looking for the proper data structure for this scenario. I have boost available to use. The code was originally in C#, and I was using a queue there, but I don't believe that was an appropriate choice, and there isnt a C++ equivalent for C#'s queue as far as I can tell. I'm looking at the following properties in terms of their frequency/importance: Needs to have quick iteration Need to be able to advance the structure quickly (i.e. When i pull an element off the the top, the next element should be the structure head) Will occasionally be cleared then fully repopulated Will occasionally be copied Will not need to be sorted as the elements will be added in the correct order The number of elements will be known at creation time and will be 50 to 200 elements. The structure will never hold more then this, but may occasionally hold less I was considering using std::list, but with the need to clear then repopulate occasionally, this doesn't seem to be a good option. When I create a list with a fixed size, then clear it, it loses the prefixed size doesn't it? Is there some way to always keep the list size so it doesn't have to deallocate/allocate memory? I know boost has a queue data structure, but it isn't iterable, and I'm not sure if it would have the same problem I had with std::list Some suggestion on how to fit std::list into my problem or a more appropriate data structure would be helpful.

Reputation: 2949

What data structure to use

I'm looking for the proper data structure for this scenario. I have boost available to use.

The code was originally in C#, and I was using a queue there, but I don't believe that was an appropriate choice, and there isnt a C++ equivalent for C#'s queue as far as I can tell. I'm looking at the following properties in terms of their frequency/importance:

Needs to have quick iteration
Need to be able to advance the structure quickly (i.e. When i pull an element off the the top, the next element should be the structure head)
Will occasionally be cleared then fully repopulated
Will occasionally be copied
Will not need to be sorted as the elements will be added in the correct order

The number of elements will be known at creation time and will be 50 to 200 elements. The structure will never hold more then this, but may occasionally hold less

I was considering using std::list, but with the need to clear then repopulate occasionally, this doesn't seem to be a good option. When I create a list with a fixed size, then clear it, it loses the prefixed size doesn't it? Is there some way to always keep the list size so it doesn't have to deallocate/allocate memory?

I know boost has a queue data structure, but it isn't iterable, and I'm not sure if it would have the same problem I had with std::list

Some suggestion on how to fit std::list into my problem or a more appropriate data structure would be helpful.

Upvotes: 3

Answers (3)

eevar

Reputation: 3629

Sounds like a ring buffer should work? There is one in boost: boost::circular_buffer.

Upvotes: 2

John

Reputation: 2363

Ring buffer (implemented as static array Foo buffer[200] and two counters), as suggested by eevar would be the best. No need for STL/Boost.

Upvotes: -3

johnsyweb

Reputation: 141790

std::deque seems to meet all of your requirements.

If performance is a real issue for you, you should read GMan's answer to Pre-allocate space for C++ STL queue .

Upvotes: 10

What data structure to use

Answers (3)

Related Questions