iterate from somewhere other than beginning or end of list?
Folks,
I'd really appreciate your help with the following. I am relatively inexperienced in C++, so please excuse me if this problem has an obvious solution that I have overlooked.
As I understand it, the functionality of a list in C++ is implemented, under the hood, using a linked list. With a linked list in C, however, you can begin to iterate from any element in the list, if you have a pointer to that element. I.e., you can do
pointer_to_list_element p;
p = address_of_element_in_middle_of_linked_list;
while (p!=address_of_last_element_in_list) {
p = p->next;
}
In C++, you can get iterate in a forward direction from the beginning of the list, or you can iterate in a reverse direction from the end of the list, but its not clear to me how you can iterate from an element in the beginning of the list. If this is possible, I'd appreciate brief instruction as to how to go about it.
Thanks,
Matthew Fleming
[1006 byte] By [
dermite] at [2007-11-20 11:02:27]
# 1 Re: iterate from somewhere other than beginning or end of list?
In C++, you can get iterate in a forward direction from the beginning of the list, or you can iterate in a reverse direction from the end of the list, but its not clear to me how you can iterate from an element in the beginning of the list.
To clarify, you actually mean: In C++, you can get iterate in a forward direction from the beginning of the list, or you can iterate in a reverse direction from the end of the list, but its not clear to me how you can iterate from an element in the middle of the list.
I would say that it is the same, if you have an iterator to the middle of the std::list. After all, iterating from the beginning or the end implies that after the first or last elements, you are iterating from the middle of the list.
# 2 Re: iterate from somewhere other than beginning or end of list?
Sorry for the typo. Yes, I meant middle of the list.
I don't agree that it is the same in C++. If I have a pointer to an element in the middle of the list, I could iterate from there by getting an iterator from the beginning of the list, using this to iterate until I reach the element in the middle, and then continuing to iterate from there. But with a linked list that I've created myself (rather than relying on the std::list), I can begin iteration at *any* position in the list. Of course, I could manually create a linked list in C++ as well as in C, but it would be nice to be able to use one of the standard containers.
Matthew Fleming
# 3 Re: iterate from somewhere other than beginning or end of list?
But with a linked list that I've created myself (rather than relying on the std::list), I can begin iteration at *any* position in the list.
I admit that I am no expert in algorithms and data structures, but it looks like the linked list you created has capabilities beyond that of a linked list, namely, random access. How can you begin iteration at any arbitrary position in the list?
# 4 Re: iterate from somewhere other than beginning or end of list?
Each element in the list contains a pointer to the next element. So if you have a pointer to an element in the middle of the list, you can go forward from there.
In a doubly linked list, each element contains a pointer to the next element in the list and a pointer to the previous element, so you go forwards or backwards from any element.
# 5 Re: iterate from somewhere other than beginning or end of list?
Each element in the list contains a pointer to the next element. So if you have a pointer to an element in the middle of the list, you can go forward from there.
In a doubly linked list, each element contains a pointer to the next element in the list and a pointer to the previous element, so you go forwards or backwards from any element.
That's right. The question is, how do you, without traversing the list from either the head or the tail, get a pointer to an element in the middle of the list in the first place?
# 6 Re: iterate from somewhere other than beginning or end of list?
I don't agree that it is the same in C++.What is "it" here?If I have a pointer to an element in the middle of the list, I could iterate from there by getting an iterator from the beginning of the list, using this to iterate until I reach the element in the middle, and then continuing to iterate from there.That's doable with C++ std::list as well, provided you have the iterator to the element you want to start from.std::list<T>::iterator it = <somewhere in the list>;
std::list<T>::iterator myListEnd = myList.end();
for (; it != myListEnd; ++it)
{
//do whatever
}This iterates from anywhere from list, whatever the iterator it is initialized with to the end... it is not a circular list hence you don't expect it to reach back to the initial position.But with a linked list that I've created myself (rather than relying on the std::list), I can begin iteration at *any* position in the list. Of course, I could manually create a linked list in C++ as well as in C, but it would be nice to be able to use one of the standard containers.The problem is how do you get to the *any*/<somewhere in the list> position when you create the list. Because, by definition, you would just be having the pointer/iterator to the beginning of the list - the head.
# 7 Re: iterate from somewhere other than beginning or end of list?
I guess what it comes down to is that with a linked list you've created manually, if you have a pointer to an element in the middle of the list you can iterate from it. (Because that item will itself contain a pointer to the next element in the list.) Whereas if using std::list<T>, having a pointer to an element within the list does not allow you to iterate from that element. You need an iterator, and std::list<T> functionality will provide you only with iterators for the beginning and end of the list.
As I've said I'm not too experienced with C++, but I'm not just trying to split hairs. I've written some code where the failure of std::list to provide me with this functionality significantly reduces its usefulness, and I'm thinking of returning to the old fashioned linked list.
Dermite
# 8 Re: iterate from somewhere other than beginning or end of list?
I guess what it comes down to is that with a linked list you've created manually, if you have a pointer to an element in the middle of the list you can iterate from it. (Because that item will itself contain a pointer to the next element in the list.) Whereas if using std::list<T>, having a pointer to an element within the list does not allow you to iterate from that element. You need an iterator, and std::list<T> functionality will provide you only with iterators for the beginning and end of the list.
Ah, now I understand. I was using the terms "pointers" and "iterators" rather loosely as at least conceptually pointers are iterators.
As I've said I'm not too experienced with C++, but I'm not just trying to split hairs. I've written some code where the failure of std::list to provide me with this functionality significantly reduces its usefulness, and I'm thinking of returning to the old fashioned linked list.
Have you considered just using list iterators instead of trying to use pointers?
# 9 Re: iterate from somewhere other than beginning or end of list?
I guess what it comes down to is that with a linked list you've created manually, if you have a pointer to an element in the middle of the list you can iterate from it. (Because that item will itself contain a pointer to the next element in the list.) Whereas if using std::list<T>, having a pointer to an element within the list does not allow you to iterate from that element. You need an iterator, and std::list<T> functionality will provide you only with iterators for the beginning and end of the list.
Dermite
Calling what is in fact a node an element of your list doesn't simplify anything. The iterator type of std::list would effectively be the same as the "item" type of your homebrew list... except much, much better.
# 10 Re: iterate from somewhere other than beginning or end of list?
I guess what it comes down to is that with a linked list you've created manually, if you have a pointer to an element in the middle of the list you can iterate from it.The question is "how do you get this pointer to the middle of the list"? Where did it come from? I don't think you've answered that.
I'll make it simple -- you give me your linked list class, and I want a pointer to the 10th element in the list. How do I get to the 10th element so as to get the pointer to it? You're jumping two steps ahead when you haven't explained the very first step, and that is how you ended up somewhere in the middle of the linked list to start off with.
Do you need to traverse the list to get to the 10th element? If so, how is this any different than how std::list<T> works? It also has to traverse somehow, so how does it do it?
I've written some code where the failure of std::list to provide me with this functionalityWhat functionality is that? If you want to get an iterator to item n, you need to start from the beginning and iterate to it. If you want a pointer to your list's item n, how do you get to item n? Do you also iterate to get there?
Given that you are now at item n, you have a pointer. So, given that the std::list is at item n, you now have an iterator. I fail to see where youre linked list class has any advantage over std::list.
Also, there is the std::advance() function that takes you to any item in std::list, given a starting iterator. Maybe this is what you are missing:
// go to 10th item in linked list:
#include <list>
#include <algorithm>
std::list<int> Test;
//...
int main()
{
//...
// You need to explain how your linked list gets to the 10th element
// in the first place. This is how you do it with std::list
std::list<int>::iterator it = Test.begin();
std::advance(it, 9);
// now "it" is an iterator to the 10th item in the list
// iterate to next item. The "it" will now point to item 11
std::advance(it, 1);
// now point to the 10th item again
std::advance(it, -1);
}
I've just "pointed" to the tenth item, and iterated to the next item, and went back by one item. So how is this different than what you're doing?
Regards,
Paul McKenzie
