Re: Variable objects and STL containers

[Vladimir Prus <ghost@cs.msu.su>]

On Sunday 17 February 2008 22:54:49 you wrote:
>  > > Actually it looks doable for lists, maps etc if the children of a variable
>  > > object were stored as a list rather than a vector.  This is so that a new
>  > > child can be added, or an old one deleted, at any point in the list.
>  > > 
>  > > Ironically, the children were previously stored in a linked list and I
>  > > guess vectors were used because Nathan Sidwell has created an API in C for
>  > > them.  There doesn't appear to be a similar API for lists, but since they
>  > > are more flexible, would it be possible to revert var->children to a
>  > > linked list?
>  > 
>  > I'm afraid I don't see any such flexibility. Can you clarify? The vectors
>  > were used because they allowed to eliminate lots of custom list handling
>  > code, and I'm reluctant to go back.
> 
> I can understand that you are reluctant to go back but I'm surprised that you
> don't see the convenience.  Until now the number of children has been fixed, so
> vectors are probably a natural choice.  With STL containers the number changes
> and and it becomes advantageous to use lists.  Taking maps, for example, they
> appear to be stored as binary trees and GDB can traverse the tree (inorder) to
> examine all the nodes.  When it finds a new one, it needs to create a new child
> *at that point* in the sequence of children.  A vector can't do that.  It can
> only add or remove them at the end, so a list must be used.

To be picky, vector can insert and remove elements in the middle, but that's O(N)
operation. But in fact, that only matters if you happen to already know that
an element was added at a certain position in the middle, which I think we don't.
Instead, we get to traverse the list, and then construct a sequence of values, then
compare the changes and report them. Suppose the old values were:

	1   2   3  4

and new values are 

	1   2   5  3  4

We can either report that varobj 2 changed value from 3 to 5, that varobj 3
changed value from 4 to 3 and that new varobj was added at end. In this case,
using vector is not a problem at all.

Or we can report that new varobj was added at position 5. This sounds more 
attractive, but it's harder to properly detect minimal changes, and it's
harder to communicate such change to gdb. And, it seems like a simple
algorithm to detect changes will work just fine with vectors.

- Volodya