CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Jun 2001
    Location
    Michigan
    Posts
    2,222

    iterator curiosity

    I've been developing my own stack implementation. data is my main storage mechanism:
    Code:
    template<class T> class Stack
    {
    private:
    	T *data;
    public:
                    typedef T* iter;
    I've supplied all the functionality I need for the stack except for a class iterator to loop through the stack's values. I'm looking to do something like this:
    Code:
    Stack<int> s;
    s.push(1);
    s.push(2);
    s.push(4);
    for(Stack<int>::iter it=s.begin();it!=s.end();it++)
         cout << *it << endl;
    What should I have the begin() and end() functions return? An iterator is basically a pointer to the stack data right? I'm stuck.
    Code:
    inline iter begin()
    {
         iter front= ... //????
         return front;
    }
    Am I on the right track?

  2. #2
    Join Date
    Apr 1999
    Posts
    27,449
    The iterator can be implemented as a pointer. The begin() should point to the first item in the stack, end() points to the item *after* the last available item. So you need a dummy end value so that

    it != s.end()

    works correctly.

    Regards,

    Paul McKenzie

  3. #3
    Join Date
    Jun 2001
    Location
    Michigan
    Posts
    2,222
    Thanks Paul,

    Here's how I returned my begin() and end():
    Code:
    	inline iter begin()
    	{
    		return data-size;
    	}
    
    	inline iter end()
    	{
    		return data;
    	}
    begin() should point to the first item in the stack, end() points to the item *after* the last available item
    The above begin() and end() functions meet these requirements.

    The following code prints out my stack great now!
    Code:
    for(si::iter i=s.begin();i!=s.end();i++) cout << *i << endl;
    So you need a dummy end value so that

    it != s.end()
    Correct me if I'm wrong, but I don't really understand why this is necessary. Even if there is no dummy value at the end, aren't the two pointers pointing to the same data? When i and s.end() are equal the loop will end regaurdless.

    At any rate, I do set a NULL value *after* the last value in the stack just to keep it clean.

    Also, I noticed you stated
    The iterator can be implemented as a pointer.
    if they can be implemented as a pointer, what other ways can they be implemented as?

    Thanks again.
    Last edited by bluesource; February 2nd, 2004 at 05:58 PM.

  4. #4
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    Originally posted by bluesource
    Code:
    	inline iter begin()
    	{
    		return data-size;
    	}
    
    	inline iter end()
    	{
    		return data;
    	}
    I don't see how that can work. data-size would point before the data pointer and hence into unchartered territory. Assuming that you use as a basis a simple c-array, then begin should just return data and end should return data + size.
    if they can be implemented as a pointer, what other ways can they be implemented as?
    An iterator can be any custom class, as long as operator ++ (and -- resp + and -) is implemented. I'll post an article in the next few days which shows a custom iterator class.
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  5. #5
    Join Date
    Jun 2001
    Location
    Michigan
    Posts
    2,222
    I don't see how that can work. data-size would point before the data pointer and hence into unchartered territory. Assuming that you use as a basis a simple c-array, then begin should just return data and end should return data + size.
    Well the way I implemented my stack, data-size points to the beginning of the stack, since after a push or a pop, data points to the item after the last available item. In other words, the end of my c-style pointer array is the top of the stack, and the beginning of the array is the bottom of the stack. That being the case, data-1 points to the end of the stack.

    Are they any advantages to implementing this differently? It seems to be working now and fully functional.
    An iterator can be any custom class, as long as operator ++ (and -- resp + and -) is implemented. I'll post an article in the next few days which shows a custom iterator class.
    Great, I look forward to reading it.

  6. #6
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    Originally posted by bluesource
    Well the way I implemented my stack, data-size points to the beginning of the stack, since after a push or a pop, data points to the item after the last available item. In other words, the end of my c-style pointer array is the top of the stack, and the beginning of the array is the bottom of the stack. That being the case, data-1 points to the end of the stack.
    Oh, I get it. It works, but I guess it's a bit a matter of taking the abstraction too far IMHO. If it doesn't complicate your design, then it's fine. But the internal representation does not matter anyways, since all you present to the external world is your methods to manipulate the stack. But well, it's your decision.

    Are they any advantages to implementing this differently? It seems to be working now and fully functional.
    Well the other obvious implementation is to just keep data fixed and keep track of the topmost element with data + size - 1. There is no obvious advantage either way, just use the one approach that makes the most sense to you.
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  7. #7
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    Just a quick follow-up to let you know that my article has been posted here. The iterator example is at the top of the range_set.h file.
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured