c++03 STL find_if reverse to find last matching item

phoffric
phoffric used Ask the Experts™
on
Using Visual Studio 2010 Pro at work. That is, using C++03.

In this article https://www.experts-exchange.com/articles/3183/An-Introduction-to-STL-Algorithms.html is the code:
#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>

int main()
{
    std::cout<<"Creating intList with values 0-9.\n";
    std::list<int> intList;
    for (int i = 0; i < 10; ++i)
        intList.push_back(i);
    
    std::cout<<"Displaying values held in list before modification:\n";
    std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " "));
    
    std::cout<<std::endl<<std::endl<<"Using find_if with unary predicate to display odd list items.\n";
    while (true) {
        std::list<int>::iterator found = std::find_if(intList.begin(), intList.end(), std::bind2nd(std::modulus<int>(), 2));    
        if (found != intList.end()) {
            std::cout<<"Found even #: " << *found <<". --> Removing it now"<<std::endl;
            intList.remove(*found);
        } 
        else
            break;
    }
    
    std::cout<<std::endl<<"Displaying values held in list after modification:\n";
    std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " "));
    
    std::cout<<std::endl<<std::endl<<"Replacing values that are divisible by 4 with 99.\n";
    std::replace_if(intList.begin(), intList.end(), std::bind2nd(std::modulus<int>(), 4), 99);
    
    std::cout<<"Displaying values held in list after modification:\n";
    std::copy(intList.begin(), intList.end(), std::ostream_iterator<int>(std::cout, " "));
    
    std::cout<<std::endl<<std::endl;
}

Open in new window


Could someone modify the above program with two little changes:
(1)  Replace std::list<int> intList; with std::list<ActionType*> ActionTypeList; where:
struct ActionType{ int a; int key; };

and
(2) Have the find_if find the last element in the list matching the key.

Here are a couple of incorrect attempts for a different version of the above. (The vector will be replaced by a list. My goal is to understand why I am getting these errors, and how to tweak the code to get it to build/run correctly. I have solved this problem another way at work using another approach, when this approach didn't work.)
https://ideone.com/ZuGkTQ

ActionType* FindLast( std::vector<ActionType*>& actions )    // CASE 1
{
    std::reverse_iterator<ActionType*> p                                                   // compiler error shown below
        = std::find_if( std::reverse_iterator<ActionType*>(actions.end()),
          std::reverse_iterator<ActionType*>(actions.begin()),
          pred);
    return *p;
}

ActionType* FindLast( std::vector<ActionType*>& actions )   // CASE 2
{
    std::reverse_iterator<ActionType*> p 
        = std::find_if( actions.rbegin()),
                        actions.rend()),
                        pred);
    return *p;
}

Open in new window


Compiler Error for CASE 1:
prog.cpp: In function ‘ActionType* FindLast(std::vector<ActionType*>&)’:
prog.cpp:42:73: error: no matching function for call to ‘std::reverse_iterator<ActionType*>::reverse_iterator(std::vector<ActionType*>::iterator)’
         = std::find_if( std::reverse_iterator<ActionType*>(actions.end()),
                                                                         ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:140:9: note: candidate: template<class _Iter> std::reverse_iterator<_Iterator>::reverse_iterator(const std::reverse_iterator<_Iter>&)
         reverse_iterator(const reverse_iterator<_Iter>& __x)
         ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:140:9: note:   template argument deduction/substitution failed:
prog.cpp:42:73: note:   ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ is not derived from ‘const std::reverse_iterator<_Iterator>’
         = std::find_if( std::reverse_iterator<ActionType*>(actions.end()),
                                                                         ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:132:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator(const std::reverse_iterator<_Iterator>&) [with _Iterator = ActionType*]
       reverse_iterator(const reverse_iterator& __x)
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:132:7: note:   no known conversion for argument 1 from ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ to ‘const std::reverse_iterator<ActionType*>&’
/usr/include/c++/6/bits/stl_iterator.h:127:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator(std::reverse_iterator<_Iterator>::iterator_type) [with _Iterator = ActionType*; std::reverse_iterator<_Iterator>::iterator_type = ActionType*]
       reverse_iterator(iterator_type __x) : current(__x) { }
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:127:7: note:   no known conversion for argument 1 from ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ to ‘std::reverse_iterator<ActionType*>::iterator_type {aka ActionType*}’
/usr/include/c++/6/bits/stl_iterator.h:121:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator() [with _Iterator = ActionType*]
       reverse_iterator() : current() { }
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:121:7: note:   candidate expects 0 arguments, 1 provided
prog.cpp:43:61: error: no matching function for call to ‘std::reverse_iterator<ActionType*>::reverse_iterator(std::vector<ActionType*>::iterator)’
           std::reverse_iterator<ActionType*>(actions.begin()),
                                                             ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:140:9: note: candidate: template<class _Iter> std::reverse_iterator<_Iterator>::reverse_iterator(const std::reverse_iterator<_Iter>&)
         reverse_iterator(const reverse_iterator<_Iter>& __x)
         ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:140:9: note:   template argument deduction/substitution failed:
prog.cpp:43:61: note:   ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ is not derived from ‘const std::reverse_iterator<_Iterator>’
           std::reverse_iterator<ActionType*>(actions.begin()),
                                                             ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:132:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator(const std::reverse_iterator<_Iterator>&) [with _Iterator = ActionType*]
       reverse_iterator(const reverse_iterator& __x)
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:132:7: note:   no known conversion for argument 1 from ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ to ‘const std::reverse_iterator<ActionType*>&’
/usr/include/c++/6/bits/stl_iterator.h:127:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator(std::reverse_iterator<_Iterator>::iterator_type) [with _Iterator = ActionType*; std::reverse_iterator<_Iterator>::iterator_type = ActionType*]
       reverse_iterator(iterator_type __x) : current(__x) { }
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:127:7: note:   no known conversion for argument 1 from ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ to ‘std::reverse_iterator<ActionType*>::iterator_type {aka ActionType*}’
/usr/include/c++/6/bits/stl_iterator.h:121:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator() [with _Iterator = ActionType*]
       reverse_iterator() : current() { }
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:121:7: note:   candidate expects 0 arguments, 1 provided

Open in new window

Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Top Expert 2016

Commented:
you may use a functor

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>

struct ActionType
{  
    ActionType(int n, int k) : num(n), key(k) {}
    int num;
    int key;
};

struct FindActionType
{  
   int key;
   FindActionType(ActionType * find) : key(find->key) {}  
   bool operator()(const ActionType * actionType) 
   { 
       if (actionType == NULL)      { return false; }
       return (key == actionType->key);
   }
};

int main()
{
    std::cout<<"Creating List with values 0-9 and keys 9-0.\n";
    std::list<ActionType *> int2List;
    for (int i = 0; i < 10; ++i)
        int2List.push_back(new ActionType(i, 10-i));
    
    std::cout<<"Displaying pointers held in list before modification:\n";
    std::copy(int2List.begin(), int2List.end(), std::ostream_iterator<ActionType*>(std::cout, " "));
    
    std::cout<<std::endl<<std::endl<<"Using find_if with functor predicate .\n";
    ActionType find(0, 3);
    while (true) {
        std::list<ActionType*>::reverse_iterator found = std::find_if(int2List.rbegin(), int2List.rend(), FindActionType(&find)));    
        if (found != int2List.rend()) {
            std::cout<<"Found #: " << (*found)->key << ". --> " << (*found)->num <<  std::endl;
            int2List.remove(*found);
        } 
        else
            break;
    }
    
    std::cout<<std::endl<<std::endl;
    return 0;
}

Open in new window


Sara

Author

Commented:
Hi Sara,

Your find is a struct with the desired key. My find_if will only be using the key and not the whole struct. The actual struct is larger than the toy example so I'd rather not create a temporary one with the key.

Thanks,
Paul

Author

Commented:
That's why I wrote pred which I would have to use with bind2nd.
Learn SQL Server Core 2016

This course will introduce you to SQL Server Core 2016, as well as teach you about SSMS, data tools, installation, server configuration, using Management Studio, and writing and executing queries.

Top Expert 2016

Commented:
you can change the constructor of the functor class to only take the key

struct FindActionType
{  
   int key;
   FindActionType(int k) : key(k) {}  
   bool operator()(const ActionType * actionType) 
   { 
       if (actionType == NULL)      { return false; }
       return (key == actionType->key);
   }
};

Open in new window


then the find_if would turn to

        int find = 3;
        std::list<ActionType*>::reverse_iterator found = std::find_if(int2List.rbegin(), int2List.rend(), FindActionType(find)));    

Open in new window


actually functors are very mighty and not only can replace any pred function pointer but solely can be parameterized with an arbitrary constructor. you even could use template classes / structs for example to handle different key types.

Sara

Author

Commented:
My workstation is not hooked up on the network. I typed this code as a short sample of what I have already done.
From the OP:  https://ideone.com/ZuGkTQ - I would just like to modify pred to accept a key and to modify the find_if to bind2nd the key to pred().
bool pred( ActionType& element, int key )
{
   if (element.key == key) return true;
   else return false;
}

...

std::reverse_iterator<ActionType*> p 
       = std::find_if( std::reverse_iterator<ActionType*>(actions.end()),
          std::reverse_iterator<ActionType*>(actions.begin()),
          pred);

Open in new window


I was hoping that there would be just a small fix, since I have to take any code here, print it out, and type it in my workstation. (No copy and paste.) :(

If you are telling me that it is not possible to do this in C++, then I will have to accept that as an answer. I thought what I was asking was possible.

Thanks,
Paul

Author

Commented:
Sara,

Please let me know whether I can correct   https://ideone.com/ZuGkTQ with respect to the predicate and/or the find_if statements to get that program to compile and work. If you say that I must use your functors, let me know. I have my program working using other techniques, but I am confused as to why the   https://ideone.com/ZuGkTQ program does not work. I thought there might be a little tweak to get it to work.

If you do not know how to get it to work, let me know.

Thanks,
Paul
Top Expert 2016

Commented:
sorry phoffric, i have no experience with the bind2nd as i always found it unnecessarily complex and couldn't keep it in my mind.

in my opinion the main problem why a pred function couldn't work is that the pred function would try to compare an array element with the key you tried to bind. but the elements are pointers and i don't know a way how to tell the find_if that it has to compare a member of the object the pointer is pointing to with the key given by the bind. exactly this shortcoming is the might of the functor which simply provides an operator() which exactly provides the interface the find_if is expecting and additionally has any thinkable means to provide this comparison with any parameters inclusively that you pass the whole list.

if you still want to use a pred function you may have to use an own smart pointer class which has operator= defined that can do the compare operation. then the list has to use the samrt pointer type as template type.

Sara

p.s.
i remember that i tried to define a global operator= function which takes pointers to class as arguments. but i can't say anymore whether that has worked. probably not, as in general i remember success better than lost battles ;-)
Top Expert 2016

Commented:
bool pred(ActionType& element)

did you try to use ActionType *& as argument for the pred?

Sara

Author

Commented:
ok Sara, forget the bind2nd function. If you just get the pred function to work, I will deal with the bind2nd function either on my own or ask a separate question.

If you can tweak that https://ideone.com/ZuGkTQ program to get it to work with a hard-coded value, I will try it out. On this work computer, I don't even have access to an internal compiler, so I am stuck with that ideone site.

I would like to understand what those compiler error messages are about, and how to fix them.

Author

Commented:
>> did you try to use ActionType *& as argument for the pred?
I tried a number of things and got compiler errors for my efforts. The problem may be as simple as adding a * or & somewhere.
If you want, I think you can "fork" the program if you think you can tweak it. If you succeed, just post the new link for me to run the program. Then, I will try to understand your changes.

Here is what I just tried with a fork: https://ideone.com/o9OF44
bool pred(ActionType*& element)
{
  if (element->key == 30) return true;
  else return false;
}
...
41.    std::reverse_iterator<ActionType*> p 
42.        = std::find_if( std::reverse_iterator<ActionType*>(actions.end()),    // **** error at line 42
43.          std::reverse_iterator<ActionType*>(actions.begin()),
44.          pred);

Open in new window


Here's the error message that refers to line 42:
prog.cpp: In function ‘ActionType* FindLast(std::vector<ActionType*>&)’:
prog.cpp:42:73: error: no matching function for call to ‘std::reverse_iterator<ActionType*>::reverse_iterator(std::vector<ActionType*>::iterator)’
         = std::find_if( std::reverse_iterator<ActionType*>(actions.end()),
                                                                         ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:140:9: note: candidate: template<class _Iter> std::reverse_iterator<_Iterator>::reverse_iterator(const std::reverse_iterator<_Iter>&)
         reverse_iterator(const reverse_iterator<_Iter>& __x)
         ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:140:9: note:   template argument deduction/substitution failed:
prog.cpp:42:73: note:   ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ is not derived from ‘const std::reverse_iterator<_Iterator>’
         = std::find_if( std::reverse_iterator<ActionType*>(actions.end()),
                                                                         ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:132:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator(const std::reverse_iterator<_Iterator>&) [with _Iterator = ActionType*]
       reverse_iterator(const reverse_iterator& __x)
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:132:7: note:   no known conversion for argument 1 from ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ to ‘const std::reverse_iterator<ActionType*>&’
/usr/include/c++/6/bits/stl_iterator.h:127:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator(std::reverse_iterator<_Iterator>::iterator_type) [with _Iterator = ActionType*; std::reverse_iterator<_Iterator>::iterator_type = ActionType*]
       reverse_iterator(iterator_type __x) : current(__x) { }
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:127:7: note:   no known conversion for argument 1 from ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ to ‘std::reverse_iterator<ActionType*>::iterator_type {aka ActionType*}’
/usr/include/c++/6/bits/stl_iterator.h:121:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator() [with _Iterator = ActionType*]
       reverse_iterator() : current() { }
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:121:7: note:   candidate expects 0 arguments, 1 provided
prog.cpp:43:61: error: no matching function for call to ‘std::reverse_iterator<ActionType*>::reverse_iterator(std::vector<ActionType*>::iterator)’
           std::reverse_iterator<ActionType*>(actions.begin()),
                                                             ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:140:9: note: candidate: template<class _Iter> std::reverse_iterator<_Iterator>::reverse_iterator(const std::reverse_iterator<_Iter>&)
         reverse_iterator(const reverse_iterator<_Iter>& __x)
         ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:140:9: note:   template argument deduction/substitution failed:
prog.cpp:43:61: note:   ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ is not derived from ‘const std::reverse_iterator<_Iterator>’
           std::reverse_iterator<ActionType*>(actions.begin()),
                                                             ^
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/char_traits.h:39,
                 from /usr/include/c++/6/ios:40,
                 from /usr/include/c++/6/ostream:38,
                 from /usr/include/c++/6/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:132:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator(const std::reverse_iterator<_Iterator>&) [with _Iterator = ActionType*]
       reverse_iterator(const reverse_iterator& __x)
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:132:7: note:   no known conversion for argument 1 from ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ to ‘const std::reverse_iterator<ActionType*>&’
/usr/include/c++/6/bits/stl_iterator.h:127:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator(std::reverse_iterator<_Iterator>::iterator_type) [with _Iterator = ActionType*; std::reverse_iterator<_Iterator>::iterator_type = ActionType*]
       reverse_iterator(iterator_type __x) : current(__x) { }
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:127:7: note:   no known conversion for argument 1 from ‘std::vector<ActionType*>::iterator {aka __gnu_cxx::__normal_iterator<ActionType**, std::vector<ActionType*> >}’ to ‘std::reverse_iterator<ActionType*>::iterator_type {aka ActionType*}’
/usr/include/c++/6/bits/stl_iterator.h:121:7: note: candidate: std::reverse_iterator<_Iterator>::reverse_iterator() [with _Iterator = ActionType*]
       reverse_iterator() : current() { }
       ^~~~~~~~~~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:121:7: note:   candidate expects 0 arguments, 1 provided

Open in new window

Author

Commented:
This is a partial solution for an C++03 array of pointers to struct.
https://stackoverflow.com/questions/17201522/how-do-you-use-find-if-along-with-reverse-iterator-on-a-c-style-array?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa

But when using a vector or list, I have compiler errors.

Although the ideone code shows a vector being used, that may likely change to a different container. I think I may be able to use the vector's underlying contiguous array to solve this problem, but that is not available in another container. The OP code from the article shows a list which I may use (despite the mantra - do not use lists).

Author

Commented:
Here is the same question with higher priority:
https://www.experts-exchange.com/questions/29096897/c-03-Use-find-if-with-predicate-to-find-last-matching-item.html

You are the first to know about this question.

I will have this one deleted shortly. Thanks for trying on this question.
Top Expert 2016

Commented:
phoffric, i already had a solution to your last request but somehow did not post it.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
 
struct ActionType {
	int a; int b;
	int key;
};
 
ActionType* FindLast( std::vector<ActionType*>& actions );
//bool pred(ActionType& element);
 
bool pred(ActionType * element)
{
	if (element->key == 30) return true;
	else return false;
}
int main() {
	std::vector<ActionType*> actions;
 
	ActionType myS300 = {10,20,30};
	actions.push_back( &myS300 );
 
	ActionType myS40  = {12,13,40};
	actions.push_back( &myS40 );
 
	ActionType myS301 = {11,21,30};
	actions.push_back( &myS301 );
 
	ActionType* pa = FindLast( actions ); // find the last key == 30 (hardcoded)
 
   std::cout << "done" << std::endl;
   std::cout << "pa: " << pa->a << " " << pa->b << " " << pa->key << std::endl;	
	return 0;
}
 
 
ActionType* FindLast( std::vector<ActionType*>& actions )
{
    std::vector<ActionType*>::reverse_iterator p = std::find_if( actions.rbegin(), actions.rend(), pred);
    return *p;
}

Open in new window


the above compiles and runs as expected. the main reason for the errors you had was a wrong forward declaration of the pred function and some kind of mess defining the iterators in the find_if.

probably the bind2nd isn't difficult now. tell me if i should try to get it work with the bind2nd (still think that the functor is much simpler and clean and actually the solution rather than a workaround).

Sara

Author

Commented:
>> in my opinion the main problem why a pred function couldn't work is that the pred function would try to compare an array element with the key you tried to bind. but the elements are pointers and i don't know a way how to tell the find_if that it has to compare a member of the object the pointer is pointing to with the key given by the bind.

Looks like you learned a little more about this subject matter and changed your mind. It may very well be that functors are better as you say, but I just wanted to understand the cause of the error. Your fix works.

>> had was a wrong forward declaration of the pred function.
Definitely.
>> The problem may be as simple as adding a * or & somewhere. (although "adding" should be "adding and/or replacing").

>> and some kind of mess defining the iterators in the find_if.
Also correct, but mess is a little vague for me, so I did a bit of studying.

In FindLast(), I started off with  std::reverse_iterator<... ...
You used another technique which you posted and that is the solution.

Here are two challenges for you (I just got both challenges working after studying reverse_iterators - guess I should have studied it before using it :(
(1) Modify pred() to add a second argument, and use bind2nd to pass in the 2nd argument. The challenge is to do this without explicitly creating another class. Have fun.
(2) The other part of the challenge is to get my code that begins with std::reverse_iterator< working.

I will make this a high priority question. and both challenges are worth 500 points. If you succeed in one challenge, you get an extra 500 points plus a good learning experience. If you get both to work, that's 1000 points. If you do not accept this mission, let me know, and I will post the answer as assists.

Thanks for your help.

Author

Commented:
Are you still thinking about adding on to this thread; or should I post as I have time (maybe this weekend)?
Top Expert 2016

Commented:
I am still thinking but unfortunately i have little time in the moment. i will try the bind2nd today. don't know whether the syntax of the reverse_iterator really is a challenge where I am patient enough to go thru. but i will tell you.

Sara
Top Expert 2016

Commented:
perhaps it is the following you wanted to see ...

ActionType* FindLast( std::vector<ActionType*>& actions );
 
bool pred(ActionType * element, int key)
{
	if (element->key == key) return true;
	else return false;
}

int main() {
	std::vector<ActionType*> actions;
 
	ActionType myS300 = {10,20,30};
	actions.push_back( &myS300 );
 
	ActionType myS40  = {12,13,40};
	actions.push_back( &myS40 );
 
	ActionType myS301 = {11,21,30};
	actions.push_back( &myS301 );
 
	ActionType* pa = FindLast( actions ); // find the last key == 30 (hardcoded)
 
   std::cout << "done" << std::endl;
   std::cout << "pa: " << pa->a << " " << pa->b << " " << pa->key << std::endl;	
	return 0;
}
 
ActionType* FindLast( std::vector<ActionType*>& actions )
{
    std::vector<ActionType*>::reverse_iterator p 
        = std::find_if( std::vector<ActionType*>::reverse_iterator(actions.rbegin()), std::vector<ActionType*>::reverse_iterator(actions.rend()), 
          std::bind2nd(std::ptr_fun(pred), 30));
    return *p;
}

Open in new window


did you?

Sara

Author

Commented:
I am pretty sure that you got the bind2nd work! I also used ptr_fun to avoid having to explicitly write a helper class functor. I believe that in C++11, this code becomes simpler because the pred() function can be replaced inline with a lambda function, which is very nice since the pred() function has little value outside of this find_if statement.

The OP and subsequent posts had a messy error message. (I included the error message in the OP from the OP ideone link.). And the goal is to understand the error message. So this LOC still applies:
    std::reverse_iterator<...> ...; // start off with std::reverse_iterator so that the nature of the error becomes clearer

What I think you did in your last post was to typecast the begin() and end() functions with a type which is actually the same type as the begin() and end() functions. Agree?
http://www.cplusplus.com/reference/vector/vector/rbegin/
Top Expert 2016

Commented:
Line 28: error: cannot convert 'std::reverse_iterator<xyz*>' to 'xyz*' in assignment

ok, now i understand what you were looking for. the error is because a pointer (like ActionType*) can be used instead of a std::iterator or std::const_iterator. therefore you can do like

int arr[5] = { 1, 2, 3, 4, 5 };  
bool found = (std::find(&arr[0], &arr[5], 4) != &arr[5]);

Open in new window


you see that the address of the (invalid) arr[5] was used to find out what end() is and the ++ operator does the same for pointers what it does for iterators including that it is equal to &arr[5] after the final iteration.

that exactly is the problem when you try to make that reverse because if you would do &arr[0]-- you would not get &arr[5] what is the value of rend(). note, using &arr[-1] as rend() is not an option as the index -1 is invalid for arrays per se and also practically invalid for some addresses at the begin of a new (heap or stack) section. so in order to not getting too much troubles with using pointers as iterators where it would fail to recognize the end, the compilers have an implementation of reverse_iterator which doesn't accept a (normal) pointer as rend() iterator.

Sara
Top Expert 2016

Commented:
fyi: early implementations of STL used pointers as substitute for std::vector::iterator.

the iterator simply was defined by a typedef.

Sara
Top Expert 2016

Commented:
with forward iterating you could do without explicit iterators:

ActionType* FindLast( std::vector<ActionType*>& actions, int k );
 
bool pred(ActionType * element, int key)
{
	if (element->key == key) return true;
	else return false;
}

int main() {
	std::vector<ActionType*> actions;
 
	ActionType myS300 = {10,20,30};
	actions.push_back( &myS300 );
 
	ActionType myS40  = {12,13,40};
	actions.push_back( &myS40 );
 
	ActionType myS301 = {11,21,30};
	actions.push_back( &myS301 );
 
	ActionType* pa = FindLast( actions, 31 ); // find the last key == 30 (hardcoded)
 
   std::cout << "done" << std::endl;
   if (pa != NULL)
       std::cout << "pa: " << pa->a << " " << pa->b << " " << pa->key << std::endl;	
   else
       std::cout << " but no match" << std::endl;
	return 0;
}
 

ActionType* FindLast( std::vector<ActionType*>& actions, int k )
{
    ActionType ** pbeg = &actions[0];
    ActionType ** pend = pbeg + actions.size();
    ActionType ** p    = std::find_if(pbeg, pend, std::bind2nd(std::ptr_fun(pred), k));
    return (p != pend)? *p : NULL;
}   

Open in new window


i tried reverse iterating by using a pointer struct and overloaded operators++ (actually doing -- on their member pointer) but failed finally with the bind2nd and ptr_fun as the ptr_fun created a functor which then is ambiguous with my pointer struct.

Sara

Author

Commented:
I believe that you are referring to other programs in some links in this thread. If you want to give another try to fix the OP  problem, I'll wait before giving the solution. In actuality, the solution I have that keeps to the form of the OP is IMO not so nice looking, but it does solve the OP problem.

Prefer not to refer to arr[] or xyz since they are not in the OP.

Not sure if I mentioned this, but I certainly do not want to use the underlying structure of a vector (namely, a contiguous array), because the vector can be changed to one of several other containers. In fact, this weekend I'll change vector to list to verify that my solution still works, and so that we are not tempted to use the simpler plain array organization.

Author

Commented:
This tweaks the find_if statement in the OP and it works with either vector or list.
#include <iostream>
#include <list>
#include <algorithm>
#include <functional>
#include <iterator>

struct ActionType {
	int a; int b;
	int key;
};

ActionType* FindLast( std::list<ActionType*>& actions );
bool pred(ActionType* element);

int main() {
	std::list<ActionType*> actions;
	
	ActionType myS300 = {10,20,30};
	actions.push_back( &myS300 );
	
	ActionType myS40  = {12,13,40};
	actions.push_back( &myS40 );
	
	ActionType myS301 = {11,21,30};
	actions.push_back( &myS301 );
	
	ActionType* pa = FindLast( actions ); // find the last key == 30 (hardcoded)

   std::cout << "done" << std::endl;
   std::cout << "pa: " << pa->a << " " << pa->b << " " << pa->key << std::endl;	
	return 0;
}

bool pred3(ActionType* element, int val)
{
	if (element->key == val) return true;
	else return false;
}

ActionType* FindLast( std::list<ActionType*>& actions )
{

    std::reverse_iterator<std::list<ActionType*>::iterator> p 
        = std::find_if( actions.rbegin(), actions.rend(), std::bind2nd(std::ptr_fun(pred3),30) );
    return *p ; // (p.base() - 1);

// This way also works
//   std::list<ActionType*>::reverse_iterator p =
//       std::find_if(actions.rbegin(), actions.rend(), pred);
//   return *p;
}

Open in new window

Top Expert 2016

Commented:
This tweaks the find_if statement in the OP and it works with either vector or list.

didn't you look for a generic version of FindLast which works with all containers that support reverse iterators?

return *p ;

this statement crashes if the key was not found. i didn't find  a solution to compare p with actions.rend() beside of using a full qualified iterator type.

Sara

Author

Commented:
I knew that. I was only interested in compiler error issues.
Top Expert 2016

Commented:
if you would pass iterators rbeg() and rend() to FindLast as std::reverse_iterator<ActionType*>& you might have better luck.

Sara

Author

Commented:
>> better luck.
What better luck are you referring to?

Author

Commented:
Give yourself 2500 points.
Top Expert 2016

Commented:
What better luck are you referring to?

to make FindLast independent of the container type you would pass a reference of std::reverse_iterator<ActionType*> both for rbegin and rend. then FindLast can compare the returned iterator to find out whether the find was successfull or not.

Sara

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial