performance and backing of data structures and c++ iterators

In the days that lead up to the test I found that most of my time was spent trying to chase down an off-by-one bug and in class brushing up on data structures and iterators. The earlier problem was resolved by spending roughly 5 hours running through the code inserting statements to help us see how the code was breaking and then exploring how to get GDB working with the eclipse CDT plugin. The latter was an exercise in note taking.

To recap the 5 common C++ iterators and the operators they provide are:

  • Input: !=, ==, *(read only), ++
  • Output: *(write only), ++
  • Forward: all of input’s and it can read or write on *
  • Bidirectional: all of forward’s and —
  • Random Access: all of bidirectional’s and [], +, -, <, >, <=, >=

As such if you want to make a method which accepts the most iterators you should only expect the operators provided by input or output and no others. However, < tends to be more robust as it will terminate in the case of the begining and the end iterator getting mixed up where inputs != won’t.

In the data structures discussed we looked at cost of selecting, removing, and adding elements which belong to various structures…. most of this discussion was review to me but the discussion continued to the different underlying data structures that could be used to build stacks, queues, and priority structures and this was something that I had not thought about. In summary the subcomponents were vectors, linked lists, and tree structures and stacks can use any of these, queues can use any but vectors, and priority queues can use any but linked lists.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s