Concept: use a templated events to create list-like container access methods

[jetimms]

I am going through "Accelerated C++" working on the chapter where you roll your own containers (chap 11).

I tried modifying a simplified vector-like container that I built in an earlier exercise, but I realized all I had was a vector container disquised as a list.

The question remained, what's the best approach.

I ran across this FAQ while searching the web and in particular would like to know what it means to create a templated atomic event for each iteration.

Excerpt from http://parashift.com/c++-faq-lite/containers.html section [34.5]:
"[3] Consider the entire iteration as an atomic event, and create a class template that embodies this event. This enhances performance by allowing the public access member functions (which may be virtual functions) to be avoided during the access, and this access often occurs within an inner loop. Unfortunately the class template will increase the size of your object code, since templates gain speed by duplicating code. For more, see [Koenig, "Templates as interfaces," JOOP, 4, 5 (Sept 91)], and [Stroustrup, "The C++ Programming Language Third Edition," under "Comparator"]."

Now here's my take on it:
I create a stand-alone generic function that acts on the container object for each access/insert/delete that I wish to do to the container.

That's fairly understandable, although not fully.

Question 1) What does that excerpt actually mean?

Here's another source of confusion:

For the vector-like class (Vec), I used three pointers: the head of the data, the end of the used data, and the end of the allocated data.

For the list, I know I need a Node (prev*/data*/next*) type of structure, however, I also know that lists allow you to dereference the iterator just like other containers. It looks like this:

// sorry for simple example
list<int> ages(3, 0);
...
list<int>::iterator ageIter = ages.begin();

int currentAge = *ageIter;

not this:

list<int> ages(3, 0);
...
list<int>::iterator ageIter = ages.begin();

int currentAge = ageIter->data;

Question 2) Do I overload operator * for the customer list class iterator to further dereference the current nodes data member value?

Feel free to answer either. Thanks.

[kbw]

1. Excerpt?
http://www.merriam-webster.com/dictionary/excerpt

I'm not sure what the confusion is you mentioned as you are correct in what you've said.

2. You don't need to overload operator*. Each iterator is defined seperately for each container to provide the behaviour you'd expect.

[Hammurabi]

Question 1) What does that excerpt actually mean?

It depends on what "entire iteration" means. The only sense I can make of it is an operation on the entire list (iterating over the list). If such an operation is "atomic" it means that you don't have to access the list through public members (since the iteration class would be a friend, it can access the data members of the list directly).

Question 2) Do I overload operator * for the customer list class iterator to further dereference the current nodes data member value?

What does your list iterator class look like so far? You must, of course, overload * in that class. It is not necessary (or useful) to overload it in the list class.

int currentAge = ageIter->data;

This seems to be assuming that ageIter is a simple pointer. That is not going to be the case with a list iterator. You want something like this (which would be a friend of ListNode):

template <typename T>
class ListIterator {
  ListNode<T>* pNode;
public:
  T& operator*() const {
    return pNode->data;
  }
  // etc.
};

[jetimms]

On the first question, I was just looking for confirmation of my understanding.

As for the second, if I have the class with the doubly linked list as a member variable, how do I get the derefrencing of one of the iterator's for an object to show the data member's address's value?

* by the way, "customer" should have been "custom" in the original 2nd question.

For (a very far from complete) example:

template <typename T>
class Lst
{
public:
  typedef T* pointer;
  typedef LstNode* iterator;
  // constructors, deconstructors, assignment method here
  ...
  iterator begin() const {return dataHead;}
  ...
private:
  iterator dataHead;  // initialized to 0 in constructor
  iterator dataTail;  // initialized to 0 in constructor
  ...
  struct LstNode {
    LstNode* prev;
    pointer data;
    LstNode* next;
  ...
  }
};

If I had it set up this way with one element in the list then to access a Lst object's first element value, I would have to do the following:

Lst<int> ages(3, 0);
...
int soAndSosAge = (*(ages.begin())).data; // would work but not STL coding standard
int sameAge = *(ages.begin()); // would not compile 

Where if I used a list object, the second option would work, instead:

list<int> eggs(3, 5);
...
int firstBasket = *(eggs.begin());
...

Sorry if my questions are unclear and thanks for the feedback.

[Hammurabi]

On the first question, I was just looking for confirmation of my understanding.

Your understanding was incorrect.

For (a very far from complete) example

Did you read my response? You cannot use a simple pointer for a list iterator. How would you implement operator++?

[jetimms]

Ah, I wasn't considering using a class for the iterator. That makes sense.

Also, I haven't had much dealings with friend classes up to this point, so I will look into them to get an understanding before trying this further.

Thanks for the explanation!

[jetimms]

Sorry Hammurabi, I was replying to kbw in my second post. I had just submitted it when I read your reply.

My example was a intentionally very broken attempt at showing the skeleton so I could further illustrate my question. That was not a first attempt (yikes!), by any means.

Thanks for your help (both) and input.