Thread: Using reverse iterators in algorithms

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    173

    Using reverse iterators in algorithms

    Hey, I've been having some trouble with getting reverse iterators to work along with the standard algorithms. Since they only accept a normal iterator I can't do any computation using a reverse iterator unless I can somehow "convert" them. I tried using .base() but it didn't work out quite well. So to try and "emulate" reverse iterators I assigned a normal iterator to the end of a vector and minus 1 (which is a bit hackish and not to my liking). Is there a way to make a reverse iterator work with the algorithms? The code below is trying to implement a "stack" LIFO structure that also allows me to pop by position.

    Code:
    std::string CompressStack::pop(int pos)
    {
    	std::vector<std::string>::iterator iter = wordStack.end()-1;
    	int cnt = 1;
    
    	if (pos >= wordStack.size()) {
    		std::cerr << "Invalid size.";
    		std::string str("NULL");
    		return str;
    	}
    
    	while (cnt < pos) {
    		iter--;
    		cnt++;
    	}
    	
    
    	std::string str(*iter);
    	/* a bit hackish but still works */
    	std::cerr << "Deleting: " << *iter << std::endl;
    	wordStack.erase(iter);
    //	wordStack.erase(std::find(wordStack.rbegin(),wordStack.rend(),*iter).base());
    	return str;
    }
    I originally had something like:
    Code:
    std::vector<std::string>::reverse_iterator iter = wordStack.rbegin();
    Obviously I used the increment operator instead of the decrement operator in the while loop. And I tried using the commented out statement which didn't seem to function as I intended. It would find the first instance from the "front" of the stack that matched the value. Having 2 values that are the same and wanting to delete the "second" similar value causes incorrect behaviour since it would delete the first instance instead of the second.

    Any feedback would be great! Thanks
    The cost of software maintenance increases with the square of the programmer's creativity.

  2. #2
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    I've been having some trouble with getting reverse iterators to work along with the standard algorithms. Since they only accept a normal iterator
    Huh? Here's three that seem to work pretty well with reverse iterators:
    Code:
    vector<int> v;
    for(int i=0; i<9; i++)
    {
    	v.push_back(i);
    }
    
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout<<endl;
    
    copy(v.rbegin(), v.rend(), ostream_iterator<int>(cout, " "));
    cout<<endl;
    
    v.push_back(0);
    copy(v.rbegin(), v.rend(), ostream_iterator<int>(cout, " "));
    cout<<endl;
    
    vector<int>::reverse_iterator pos = find(v.rbegin(), v.rend(), 0);
    cout<<distance(v.rbegin(), pos)<<endl;
    Is there a way to make a reverse iterator work with the algorithms?
    Which algorithm? If you want to use erase(), you can do this:
    Code:
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main(void)
    {
    	vector<int> v;
    	for(int i=0; i<9; i++)
    	{
    		v.push_back(i);
    	}
    
    	v.push_back(0);
    	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    	cout<<endl;
    
    	vector<int>::reverse_iterator pos = find(v.rbegin(), v.rend(), 0);
    	v.erase((++pos).base());
    	copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    	cout<<endl;
    		
    	return 0;
    }
    The way I understand it, a reverse iterator and an iterator both point to the same place, but a reverse iterator's value is defined to be one ahead of where it is pointing i.e. closer to the front of the container. For example, with an iterator, end() points to one past the last element, and if you dereference end() you will access memory that is out of bounds. For a reverse iterator, you might expect that rbegin() points to the last element(vs. one past the last element), but rbegin() also points to the one past the last element. However, if you dereference rbegin(), you get the last element--not the illegal memory one past the last element that rbegin() is pointing to. In a similar fashion, begin() and rend() both point to the first element.

    If you convert a reverse iterator to an iterator using base(), the value switches from the value that's one ahead of where the reverse iterator is pointing--> to the value at the position the reverse iterator is pointing. In the example, pos is physically pointing to one past the end, but since it is a reverse iterator, when you dereference it, you get the value one ahead of where the reverse iterator is pointing, which is the last element. If you convert that reverse iterator to an iterator with base(), then since it is now a regular iterator, when you dereference it, you will get the value where the iterator is pointing, and that is one past the end, which is out of bounds. So, to use erase(), I advanced the pointer one spot and then converted it to a regular iterator.

    I really have no idea if that is at all helpful because I have no idea what your question is.
    Last edited by 7stud; 02-27-2006 at 04:59 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. algorithms over vector: offsets or iterators for speed?
    By pheres in forum C++ Programming
    Replies: 2
    Last Post: 04-09-2009, 02:23 AM
  2. Problem with my reverse function and its output!
    By Matus in forum C Programming
    Replies: 4
    Last Post: 04-29-2008, 08:33 PM
  3. Utilizing genetic algorithms for reverse engineering
    By Imagine in forum C++ Programming
    Replies: 1
    Last Post: 01-07-2008, 03:58 AM
  4. gethostbyaddr() reverse lookups failing (???)
    By Uncle Rico in forum C Programming
    Replies: 9
    Last Post: 08-19-2005, 09:22 AM
  5. Replies: 7
    Last Post: 03-18-2003, 03:32 PM