What data structure to use

Question

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.

What does *quick iteration* mean? Do you have a benchmark? – Sam Miller Jun 05 '11 at 01:04 — Sam Miller, Jun 05 '11 at 01:04

score 10 · Accepted Answer · edited May 23 '17 at 10:34

10

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 .

edited May 23 '17 at 10:34

Community

1
1

answered Jun 05 '11 at 00:58

johnsyweb

136,902
23
188
247

6

@Downvoter: Please explain what it is that is wrong with this answer. – johnsyweb Jun 05 '11 at 02:15

score 2 · Answer 2 · edited Jun 05 '11 at 02:33

2

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

edited Jun 05 '11 at 02:33

R. Martinho Fernandes

228,013
71
433
510

answered Jun 05 '11 at 00:59

eevar

3,519
1
19
9

There's a circular list in Boost, but not in STL. – greyfade Jun 05 '11 at 02:13

score -3 · Answer 3 · answered Jun 05 '11 at 01:18

-3

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.

answered Jun 05 '11 at 01:18

John

2,295
1
20
25

3

"*No need for STL/Boost.*" Why do you say this like it's a good thing, or even noteworthy? – ildjarn Jun 05 '11 at 01:27
Because adding complexity with no real value added is bad. – John Jun 05 '11 at 01:28
5

Writing your own implementation of something that is already written, well documented, well maintained, and well supported is adding complexity... – ildjarn Jun 05 '11 at 01:37
For such a simple data structure, I'd probably implement it in less time than OP needed to write his question. And the nearest STL equivalent (in terms of performance) is std::deque with custom allocator which is *way* more complex than simple array. – John Jun 05 '11 at 01:40
[Boost.CircularBuffer](http://www.boost.org/doc/libs/release/libs/circular_buffer/index.html) – ildjarn Jun 05 '11 at 15:44

What data structure to use

3 Answers3