3 ms·

For the record, I did read the entire article. And I admittedly dismissed most of it when you stated "This is not a tested theory, just simple speculation." As

For the record, I did read the entire article. And I admittedly dismissed most of it when you stated "This is not a tested theory, just simple speculation." As you discovered, your implementation was effectively a deque. I don't really consider keeping an in place iterator around any kind of "fundamental" optimization, hence my reply. Anyway, feel free to pontificate all you want about my answer in your blog, however it wasn't my intention to get in to a pissing match about it, it was instead just to point out that I felt misled by the title of the original post.

NathanKP 17y ago
Okay, I understand your take on it. Whether or not my optimization ideas were "fundamental" is up for interpretation. From my point of view I used the word "fundamental" in that my ideas build upon the basic format and operation of the linked list. They may not be major but they are enough to make the class considerably faster than STL classes including the deque class. And if my response to your comment took a pontificate form it was only because I was slightly disappointed that you passed off my idea as a "doubly linked list" when it was actually considerably more than that.
- ismarc 17y ago
  You should fix your code for testing the speed of the STL implementation. You intentionally chose to implement it in a scenario that discarded any previous results. The most common usage is for (std::list<x>::iterator it = list.begin(); it != list.end(); it++); Using your naive approach, of course the list is going to be slow to access each element. Keeping a single pointer in memory is much more efficient than spending clock cycles going back over elements you've already seen. If you need the random access, or 32 bits is excessive to keep in memory (for whatever reason), a deque exists specifically for the purpose.

3 ms·

For the record, I did read the entire article. And I admittedly dismissed most of it when you stated "This is not a tested theory, just simple speculation." As

by squidbot 17y ago

NathanKP 17y ago
Okay, I understand your take on it. Whether or not my optimization ideas were "fundamental" is up for interpretation. From my point of view I used the word "fundamental" in that my ideas build upon the basic format and operation of the linked list. They may not be major but they are enough to make the class considerably faster than STL classes including the deque class. And if my response to your comment took a pontificate form it was only because I was slightly disappointed that you passed off my idea as a "doubly linked list" when it was actually considerably more than that.
- ismarc 17y ago
  You should fix your code for testing the speed of the STL implementation. You intentionally chose to implement it in a scenario that discarded any previous results. The most common usage is for (std::list<x>::iterator it = list.begin(); it != list.end(); it++); Using your naive approach, of course the list is going to be slow to access each element. Keeping a single pointer in memory is much more efficient than spending clock cycles going back over elements you've already seen. If you need the random access, or 32 bits is excessive to keep in memory (for whatever reason), a deque exists specifically for the purpose.