Need C++ STL::LIST Container Help...

[quantass]

I'm declaring the following variables:

std::list<int> myVar;
std::list<int>::iterator iter1;

I'm in a situation where to have a list container work best for me I need to store the address to specific elements within the list rather than have to iterate through the list from top to bottom.

Is it possible for me to store the address of specific elements within the list for later direct access and iteration (forwards, backwards) from that point? I would like to store the obtained address as a CHAR * if possible, but not required. Or if this is impossible what would be my best option for getting to list items quickly?

I'm declaring the following variables:

std::list<int> myVar;
std::list<int>::iterator iter1;

I'm in a situation where to have a list container work best for me I need to store the address to specific elements within the list rather than have to iterate through the list from top to bottom.

Is it possible for me to store the address of specific elements within the list for later direct access and iteration (forwards, backwards) from that point? I would like to store the obtained address as a CHAR * if possible, but not required. Or if this is impossible what would be my best option for getting to list items quickly?

I've created a combobox with a number of items within it. Ideally I would like each combo item to know exactly which list container element it is directly related to so that on selection I can directly jump to and iterate from that location.

[Andreas Masur]

'std::list' has no operator '[]' defined so there is not way of directly access a list element.

It might be better if you can use a 'std::map' instead. Then you could use the key as the index and can use the operator '[]' to directly access the appropriate item...

[quantass]

A map would be nice but I also need to have a specific ordering for elements this way after jumping to the certain location i can iterate outward viewing the order citical elements near it. My app will be moving elements from one spot to another to keep a certain order amongst them.

Hmmmm.... Perhaps deque? But because I will be shuffling elements around and inserting/deleting from arbitrary locations I wonder if deque is up to the task?

Any thoughts?

[kuphryn]

Post a list of criteria.

Do you want direct access via [] operator?
Do you want a key/value paradigm?
Do you want to move elements around including delete?

Kuphryn

[quantass]

Ok, here's a criteria list:

- direct access to an entry either through [] or a memory address. To have to iterate through a list that can have over a thousand entries could be deadly.

- i need to insert/delete/move entries from the beginning, end, and middle areas.

- because of the potential for over a thousand entries i dont want a container that allocates memory as one contiguous block. i need to make the most of available memory.

[kuphryn]

Okay. We consider possible candidates.

- map
- set
- deque

How about sorting?
How are the element organized? For example, do you want a search key?

Kuphryn

[Paul McKenzie]

Originally posted by quantass
Ok, here's a criteria list:

- direct access to an entry either through [] or a memory address. To have to iterate through a list that can have over a thousand entries could be deadly.As others have pointed out, [] is not available. However, you can use std::advance to get to the element you want, maybe possibly creating a wrapper for std::list that has an operator [] that calls std::advance.

#include <list>

std::list<int> IntList;

int main()
{
IntList.push_back(1);
IntList.push_back(2);
IntList.push_back(3);
IntList.push_back(4);
std::advance(IntList.begin(), 2); // Go to third item in list
}

Regards,

Paul McKenzie

[quantass]

Having the entries sorted is fine as long as it isnt dealing with thousands of entries each time it sorts -- it just inserts it where it needs to be. I have no problems with a search key as long as the method used isnt unbearable for the potential number of entries.

I would like to have the entries sorted in the same way as it is presented visually on my on screen listbox. This way when the user selects an on screen listitem i use its index in my container and just iterate from that point downward to execute the adjacent entries that are related to the adjacent onscreen items.

If the user moves/deletes a listitem the container entries need to update themselves to retain the linear ordering they have amongst themselves.

[kuphryn]

Okay. I recommend a list container with std::pair elements. The list supports direct access via advance(). std::pair allows for direct key search.

The difficulty in with your problem is twofold. First, the contradiction between direct access and modification anywhere in within the container. A container that supports direct access usually do not work well when you delete elements anywhere else except beginning and end. On the other hand, a list serves this purpose, however, it does not support direct access. The second difficulty lies in data representation. You want the container to store data the same as what the list control presents the data. In other wants, you want sychronization between them. Thus, in general the container should not sort the data. This eliminates the set and map container, which are extremely powerful and quick too because they sort the element.

Kuphryn

[quantass]

kuphryn,

thanks a bunch for the fabulous assistance. I'm curious, whats the use of the typedef: "pointer", "reference" for containers? And does using the Advance() function act exactly like iterating through a FOR statement with Begin()/End() for the container or does it use some kind of optimized method for getting to the entry? I'm just concerned with the number of entries the list can contain and the user's patience. :D

And you mentioned std::p air elements. I'm new to STL. What's its full name again? I'll read up more on the two in my C++ How To Program.

Thanks again.

[kuphryn]

What do you mean pointer and reference for containers?

For direct access iterators such as a vector and a deque, advance() is constant access. For all other iterators, advance() is linear access just as a for loop.

Here is an example of a list of std::pair.


typedef std::pair<std::string, int> pairStringInt;
typedef std::list<pairStringInt> listPSI;

listPSI data;
data.push_back(pairStringInt(TEXT("December"), 2003));


Kuphryn

[jwbarton]

Reposted this as the next message, as it wasn't showing up for some reason...

[jwbarton]

If you want to, you can save iterators to multiple elements within a std::list. This will allow you to access an element starting at a known location without needing to traverse the entire list.

The only problem with this is that you have to know what operations will invalidate an iterator. Once an iterator is no longer valid, you will most likely crash it you try to access the list using that iterator.

Fortunately, iterators in an std::list are invalidated by erasing the element that the iterator represents. Other operations won't invalidate the iterator. So, you can save iterators which refer to specific elements in the list, and as long as you don't erase these elements, the iterators remain valid. This allows you to insert additional elements into the list and sort the list (using the list member sort), without invalidating these saved iterators.

Note: if you are reordering elements in a list manually, you can use the splice method to move the elements to a temporary list, and then use splice to put the elements back into the original list without invalidating the iterators.

Best regards,
John