from iterator to data structure?

This is a discussion on from iterator to data structure? within the C++ Programming forums, part of the General Programming Boards category; Hi, Is there a way to go from the iterator to the data structure? I.e. if Code: std::vector<int> v; std::vector<int>::iterator ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    6

    from iterator to data structure?

    Hi,

    Is there a way to go from the iterator to the data structure? I.e. if

    Code:
    std::vector<int> v;
    std::vector<int>::iterator i;
    
    i = v.begin();
    Is there a way for going back from i to v somehow?

    Why would I want to do this?

    I have a method which accepts an iterator and does something with the object inside the collection (i.e. the object the iterator is pointing to). However, the iterator can also be v.end().
    I don't want to check for v.end() everytime but prefer letting the method check it. This method, as mentioned already, only gets the iterator delivered.

    So is this possible?

    Rephrased: Can you detect if an iterator equals vector.end() without having access to vector or getting vector.end() delivered additionally?

    Sebastian
    Last edited by seson; 07-24-2008 at 02:42 PM.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    You could take a pointer, and pass either &*i (?), or NULL. That's probably the easiest way to pass a parameter that could be invalid.

    Alternatively . . . you could pass a reference to the vector and a size_type index instead of an iterator.
    Last edited by dwks; 07-24-2008 at 02:17 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,691
    I don't get it, you want to set the vector's starting memory address to i?
    A class that doesn't overload all operators just isn't finished yet. -- SmugCeePlusPlusWeenie
    A year spent in artificial intelligence is enough to make one believe in God. -- Alan J. Perlis

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    I think this is the situation.
    Code:
    std::vector<int> v;
    std::vector<int>::iterator i = v.begin();
    
    // ...
    function(i);
    
    void function(std::vector<int>::iterator i) {
        if(i == ***.end()) {
            // it's invalid . . .
        }
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Registered User
    Join Date
    Jul 2008
    Posts
    6
    Ok, for clarification.

    Code:
    void do_sth(vector<int>::iterator i) {
        if (i != i.vector_it_belongs_to.end())
            std::cout << *i;
    }
    This is just an example method. It should basically check if the iterator is valid and doesn't point to the end of the vector. I just want to be able to call do_sth() with an iterator without having to check if the iterator is valid where I call it. I'd prefer checking it inside.


    dwks: Yes, this is what I mean. But with &*i (?), or NULL I'd have to check it from where I call it, because you cannot dereference v.end()

    Sebastian
    Last edited by seson; 07-24-2008 at 02:22 PM. Reason: dwks' example was quicker

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Right. Here are two ways I might do this.

    The easiest way is to pass a pointer to the function, instead of an iterator.
    Code:
    void func(int *i) {
        if(i == NULL) // invalid
    }
    
    std::vector<int>::iterator i = v.begin();
    func(&(*i));
    func(NULL);
    Or you can pass a size_type, an index into the vector. (You know, like the way you address arrays.) You can turn an iterator into an index, if you want to, by using subtraction.
    Code:
    std::vector<int> v(10);
    std::vector<int>::iterator i = v.begin();
    i ++;
    i ++;
    
    std::cout << i - v.begin() << '\n';
    And I think you can use (size_t)-1 or something like that to indicate an invalid index . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Jul 2008
    Posts
    6
    dwks:

    The first one won't work. My intention is that I can pass any valid iterator (which includes v.end()) to the function and it can find out wether this iterator is pointing to something or not (if it's pointing to end()). But there's no way I can call end() because I don't have a reference to v inside the method.
    And &(*v.end()) doesn't yield NULL, as *v.end() is impossible.

    Sebastian

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    As far as I know, given an iterator you can't find out which container it belongs to. The iterator itself doesn't know that. A vector::iterator is little more than a pointer to the value type. Basically what you want: given an arbitrary pointer you want to be able to find out where the range ends that the pointer points into.

    That's why algorithms normally take a start and an end iterator.

    Of course, you could create your own iterator that does store a reference to the container, but what's the point?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #9
    Registered User
    Join Date
    Jul 2008
    Posts
    6
    Well, I can call ++ on the iterator as long as it's valid. As soon as the iterator is container.end() I cannot call iterator++ without getting an error. So it should know where the end is.

    I just don't want to deliver the end iterator additionally. I'd like the method to detect if the iterator is inside bounds.

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    >> I just don't want to deliver the end iterator additionally.
    Unfortunately that's just how it's done. I do believe there will be support for iterator ranges that make it so you don't have to pass both separately, but I'm not sure what the status is on those changes.

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Well, I can call ++ on the iterator as long as it's valid. As soon as the iterator is container.end() I cannot call iterator++ without getting an error. So it should know where the end is.
    It is the same with plain pointer into array. As long as your pointer stays within bounds, everything is OK. If you increment the pointer (more than one) past the end of the array you get undefined behaviour. This doesn't mean that the pointer knows where the end of the array is.

    It is also possible that you are using VC++ which indeed seems to store some additional information in the iterator if range-checks for iterators are not turned off. However, this is not required by the standard and this compiler-specific knowledge is not something you should try to use for your purposes.

    There are also Boost libraries, which through some template magic seem to manage to detect whether something is a STL-compliant container, an array or a null-terminated C-style string (given a container, array or C style string).

    But the simplest and most idiomatic thing to do: pass two iterators to delimit the range.
    Last edited by anon; 07-24-2008 at 05:03 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. pthread question how would I init this data structure?
    By mr_coffee in forum C Programming
    Replies: 2
    Last Post: 02-23-2009, 12:42 PM
  2. Data structure implementation
    By fkheng in forum C Programming
    Replies: 3
    Last Post: 07-31-2003, 08:44 AM
  3. can't insert data into my B-Tree class structure
    By daluu in forum C++ Programming
    Replies: 0
    Last Post: 12-05-2002, 06:03 PM
  4. Tab Controls - API
    By -KEN- in forum Windows Programming
    Replies: 7
    Last Post: 06-02-2002, 10:44 AM
  5. Dynamic Data Structure -- Which one is better?
    By Yin in forum C++ Programming
    Replies: 0
    Last Post: 04-11-2002, 12:38 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21