Store STL iterator in CListBox

[LionAM]

In principle, I have a CListBox object and an STL list<...> object. The items in the list<...> should be reflected in the CListBox. When I remove any item from the CListBox, it should be removed from the list<...>, too. Therefore, I stored the (raw data of the) iterator to the corresponding list<...> item within the CListBox item. This was no problem in Visual C++ 6 as

sizeof(list<...>::iterator) == sizeof(void*)

However, this is not the case in Visual C++ 2008. Together with the pointer to the node, the pointer to the list (_Mycont) and some other pointer (_Mynextiter) are stored inside the iterator. You can, in principle, construct a new iterator knowing only the pointer to the node (iter._Ptr) and the pointer to the parent list. However, I cannot convert from void* back to list<...>::_NodePtr:

void* data = listBox.GetItemData(index);
iter.Ptr = (list<...>::_NodePtr)data; //Error: list<...>::_NodePtr is protected

Alex

[Lost User]

I have not used list but it may be that it is not the best container for this situation; perhaps a map would provide what you want.

Unrequited desire is character building. OriginalGriff I'm sitting here giving you a standing ovation - Len Goodman

[LionAM]

Everything was working as expected under Visual C++ 6. For Visual C++ 2008, I found a (not very elegant) workaround. As I cannot directly convert to _NodePtr, I take another iterator, write the data to the memory position of the _NodePtr member and create a new iterator:

list<...>::iterator temp;
*(void**)&temp._Ptr = listBox.GetItemDataPtr(index);
iter = list<...>::iterator(temp._Ptr, &stl_list);

Alex

[Lost User]

LionAM wrote:

Everything was working as expected under Visual C++ 6.

That may have been luck; you should never rely on an object being the same size as a pointer.

Unrequited desire is character building. OriginalGriff I'm sitting here giving you a standing ovation - Len Goodman

[LionAM]

I did not rely on it - I had checked this with a STATIC_ASSERT(...) macro. But when I tried to compile the program with VC2008, this failed. (indeed, if I hadn't used the STATIC_ASSERT, I would perhaps still wonder why the program does not work as expected...) Alex

[Lost User]

My statement was made as a general statement of principle: pointers (which have a constant size) are not the same as objects (whose size may change).

Unrequited desire is character building. OriginalGriff I'm sitting here giving you a standing ovation - Len Goodman

[_Superman_]

All keywords that begin with and underscore followed by a capital letter (_Nodeptr) are reserved for use internally by the standard C++ library and must not be used. Also, it is not a good idea to store iterators because they will be invalidated whenever the any change happens to the container. So, for example, if one item is deleted from the list, some of the iterators will become invalid.

«_Superman_»  _I love work. It gives me something to do between weekends.

_Microsoft MVP (Visual C++)

Polymorphism in C

[Orjan Westin]

Don't store iterators, it's not a good idea. I'd say that you should take the opportunity to refactor the code a bit. If you're not going to remove or add elements inside the list (I assume not, since that could invalidate iterators), you could use a std::vector instead, and store the indices in the listbox. This would also give constant-time access, just like having an iterator already. If you are going to add or remove in the middle of the list, use a std::map with an autoincrementing unsigned int as a key, and store that key in the listbox. Both of these solutions are safe in the face of change.

[LionAM]

Thank you for your answer. Surely, I am adding and removing elements from the STL (doubly linked) list. That is the purpose of the CListBox control. The STL list lives, in principle, for the whole program lifetime. If I want to change the contents of the list, I create a child window with the CListBox control and populate it with the items of the list (together with the iterator). To add a new item before/after the currently selected item in the CListBox control, I use the iterator to find the corresponding item in the STL list. When I want to delete an item, its the same. This works, as the iterators of the STL list are guaranteed to be valid as long as you don't delete the corresponding item. For my case, a map would not work as it does not remember the ordering of the items. To store the indices of the vector would not make sense as these change if one item is inserted or removed. The doubly linked list seems, in principle, to be the best choice due to the constant insert/remove time. Alex

[LionAM]

I agree that these internal members may change for different STL versions. But, at least for STL list, all iterators remain valid as long as you do not remove the corresponding item from the list. This is guaranteed by the standard. Have you a better idea how to store a reference to some item of a doubly linked list within the CListBox, so that I can add another item before/after the selected item or to remove the corresponding item from the STL list? Alex

[Orjan Westin]

In that case, you could store a pointer rather than an iterator to the element, by taking the address of the value the iterator points to.

int* pointer_in_listbox = &(*it);
listBox.SetItemDataPtr(index, pointer_in_listbox);

This would require an extra step to retrieve the iterator, using a custom predicate:

struct ptr_cmp
{
// Pointer we're looking for
const int* ptr;

// Constructor
ptr_cmp(const int* p)
: ptr(p)
{}

// Predicate function
bool operator()(const int& i)
{
return (&i == ptr);
}
};

This lets you use the std::find_if algorihtm (remember to #include <algorithm>):

// Declare a predicate with the item we're looking for
int* pointer_from_listbox = static_cast(listBox.GetItemDataPtr(index));
ptr_cmp comparer(pointer_from_listbox);

// Find the corresponding iterator
std::list::iterator it = std::find_if(l.begin(), l.end(), comparer);

That ought to work. It is slower than direct access via the iterator, but should not be noticeable in a GUI context.

[LionAM]

Cool Cow Orjan wrote:

It is slower than direct access via the iterator, but should not be noticeable in a GUI context.

In my case, you are surely right. Inserting/removing items into/from the CListBox is much slower than iterating over the items int the STL list. However, in this case I could also use a vector. The index of the CListBox would directly correspond to the index of the vector. Although inserting an item in the middle of the vector is no constant time operation, it would not be noticeable within the GUI. Just curios: Is there any container concept with raw access by index (not by Key) and at least logarithmic insertion/removal time? Alex

[Emilio Garavaglia]

The iterator members aren't granted to remain the same, and the iterator itself can be wider than just a pointer (it may have some other members for checkup). The standard grants that list::itrerator will always be valid until the element they refer remain in the list. An list grants that the element retain their placement in memory until they remain in the list. Instead of store the iterator, store the pointer to the value the iterator refers to:

SetItedDataPtr(&*iter);

You can -at this pioint- access the element directly through the pointer. Just make sure to update the list and the list-box coherently. (Note: if *iter has a unary-& overload, just use std::address_of(*iter) )

2 bugs found. > recompile ... 65534 bugs found. :doh:

[nv3]

You might also consider working with a vector and storing the index values. Vectors are not all that bad as their reputation. See this recent article for an interesting comparison to linked lists: Number-crunching-Why-you-should-never-ever-EVER-us With an index value you definitely know that it will always fit into the data cell of a list box.

[LionAM]

Thank you for your answer and the interesting article. However, as I mentioned, I am doing insertions within the middle of the list - so the indices change and it does not make any sense to store them in the data cell. Additionally: Your article assumes that I would have to find the right insert position and therefore the vector would be faster - but if it would have been possible to store the iterator inside the data cell, I would immediately start at the right position of my linked list. It would still be nice to have a data structure allowing access by index (not Key!) while beeing able to insert/remove elements in logarithmic time. Alex