[Home] [Downloads] [Search] [Help/forum]

Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to "verify" your details, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.
 Entire forum ➜ Programming ➜ STL ➜ listContains - Template Function
listContains - Template Function

It is now over 60 days since the last post. This thread is closed.     Refresh page

Posted by David Haley   USA  (3,881 posts)  Bio
Date Wed 23 Jul 2003 12:52 AM (UTC)
Message


Unless I missed something really obvious, there's no one-line way to check if a list contains a given object. So, I wrote a template function for it...


template <class listType, class containedType>
bool listContains( listType & container, containedType item )
{
	typename listType::iterator itor;

	for (itor = container.begin(); itor != container.end(); itor++)
	{
		if ( (*itor) == item )
			return true;
	}
	return false;
};


According to some reference material I read, if you compile in G++, you can't declare the function in one place and then define it (with the body) in another file. You need to have that whole thing in your header file (for me, utility.h). However, MSVC++ apparently will understand, if the declaration, i.e.
template <class listType, class containedType>
bool listContains( listType & container, containedType item );

is in a header file, and the implementation, i.e. the function body, is in a .cpp file.

If anyone sees any errors or improvements to this function, please let me know. :) And if you use it, please put a small mention for my name somewhere. :)
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Nick Gammon   Australia  (23,046 posts)  Bio   Forum Administrator
Date Reply #1 on Wed 23 Jul 2003 02:15 AM (UTC)
Message
I don't like to dampen your enthusiasm, however I think you will find that "find" will do that. :)

Here is the implementation of find from Linux:


template <class _InputIter, class _Tp>
inline _InputIter find(_InputIter __first, _InputIter __last,
                       const _Tp& __val,
                       input_iterator_tag)
{
  while (__first != __last && *__first != __val)
    ++__first;
  return __first;
}


Yours will work, however the general case above uses iterators rather than containers directly. This seems to be a general trend in the way STL is implemented. Also it returns an iterator, whereas your function will only return true or false. What do you do if it is true and you want to use the found value? I suppose you could argue you know what the value is as you have searched for it, but a more general case is to write your own function object to find if (say) a player is in a list of players, and you want to find on player name, but want to know his IP address.

The other useful thing about iterators is you can search a subset, for instance, if you have a vector of 100 numbers, but want to find if the number 5 is in the first 20, then you would use the begin and end range to limit the search.

Finally, the general way STL works is the full implementation has to be in the header file. In fact, STL is really header+implementation, which is why the files have no suffix. eg. <vector> rather than <vector.h>.

You will find, even with the MS C++ that if you try to separate it all out, and have the prototype in a header file, the implementation in a second file, and use it in a third file, that it will compile, but not link. That happened to me until I realised what I was doing.

The reason is that the compiler needs to generate the templated function on-the-fly based on the type information at hand - which is a compilation function - the linker cannot do that.

The example code below - which took a bit of mucking around to get right - demonstrates searching for a more complex thing (a player). I have a separate function object that is called by find_if to search. find_if is related to find, but in this case returns true if the function returns true after being passed a copy of each item in the container.


#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <iostream>

using namespace std;			

class player
  {

  public:

    player (const string name, const int age)
      : m_name (name), m_age (age) {};

    string  m_name;
    int     m_age;

  };  // end of  class player

class player_name_equal 
  {
  public: 

  // constructor remembers target name
  player_name_equal (const string & s) : target (s) {};

  // operator () does the comparison
  bool operator() (const player & p)
    {
    return p.m_name == target;
    };

  private:

    // store the name to search for
    const string target;

  };  // end of class player_name_equal

vector<player> v;

void ShowDetails (vector<player>::const_iterator i)
  {

  if (i == v.end ())
    cout << "not found" << endl;
  else
    cout << "age of " << i->m_name << " = " << i->m_age << endl;

  }  // end of ShowDetails

int main (void)
  {

  v.push_back (player ("Nick", 12));
  v.push_back (player ("Ksilyan", 25));
    
  ShowDetails (find_if (v.begin (), v.end (), player_name_equal ("John")));
  ShowDetails (find_if (v.begin (), v.end (), player_name_equal ("Ksilyan")));
  ShowDetails (find_if (v.begin (), v.end (), player_name_equal ("Nick")));

  return 0;
  } // end of main


Example Output

not found
age of Ksilyan = 25
age of Nick = 12


The other useful thing about having an iterator returned, rather than the found thing itself, is you can then search from that iterator onwards. For example, if I had two players called Nick, I could then search for the second one.

Here is an example - if you add this to just before the return statement:


  // add a 2nd Nick
  v.push_back (player ("Nick", 100));

  // an iterator
  vector<player>::iterator i;
  
  // find first Nick
  i = find_if (v.begin (), v.end (), player_name_equal ("Nick"));

  // find next Nick
  if (i != v.end ())
    i = find_if (++i, v.end (), player_name_equal ("Nick"));
  
  ShowDetails (i);


Example Output

not found
age of Ksilyan = 25
age of Nick = 12
age of Nick = 100

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #2 on Wed 23 Jul 2003 02:34 AM (UTC)
Message
Oh, right. So that's where it was hiding. I didn't realize there was an external function for it (my STL documentation is the MSDN which is rather poor). I figured that since "string" had a find as a member function, the list class would too... and since it didn't, I (too rapidly) assumed there wasn't one. *bonk self*

Like you said the built-in function is simply better. I just needed something quick to return true or false (in fact my true or false version is more useful in my immediate case because the whole point was to be short, and fit in one little line), but in the general case the STL version is (of course) better.

Ah well, there goes my shot at fame! :P
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Nick Gammon   Australia  (23,046 posts)  Bio   Forum Administrator
Date Reply #3 on Wed 23 Jul 2003 03:22 AM (UTC)

Amended on Wed 23 Jul 2003 03:37 AM (UTC) by Nick Gammon

Message
In fact, a shorter version which uses operator== and straight find (not find_if) is below ...


#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <iostream>

using namespace std;			

class player
  {

  public:

    player (const string name, const int age)
      : m_name (name), m_age (age) {};

    bool operator== (const string & name) const { return m_name == name; };

    string  m_name;
    int     m_age;

  };  // end of  class player


vector<player> v;

void ShowDetails (vector<player>::const_iterator i)
  {

  if (i == v.end ())
    cout << "not found" << endl;
  else
    cout << "age of " << i->m_name << " = " << i->m_age << endl;

  }  // end of ShowDetails

int main (void)
  {

  v.push_back (player ("Nick", 12));
  v.push_back (player ("Ksilyan", 25));
    
  ShowDetails (find (v.begin (), v.end (), "John"));
  ShowDetails (find (v.begin (), v.end (), "Ksilyan"));
  ShowDetails (find (v.begin (), v.end (), "Nick"));

  return 0;
  } // end of main


Example Output

not found
age of Ksilyan = 25
age of Nick = 12

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Nick Gammon   Australia  (23,046 posts)  Bio   Forum Administrator
Date Reply #4 on Wed 23 Jul 2003 03:26 AM (UTC)

Amended on Wed 23 Jul 2003 03:38 AM (UTC) by Nick Gammon

Message
And, if you overload operator== in different ways you can compare for a name or an age (in the case of a MUD you might want a name or vnum), simply like this:


#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <iostream>

using namespace std;			

class player
  {

  public:

    player (const string name, const int age)
      : m_name (name), m_age (age) {};

    bool operator== (const string & name) const { return m_name == name; };
    bool operator== (const int & age) const { return m_age == age; };

    string  m_name;
    int     m_age;

  };  // end of  class player


vector<player> v;

void ShowDetails (vector<player>::const_iterator i)
  {

  if (i == v.end ())
    cout << "not found" << endl;
  else
    cout << "age of " << i->m_name << " = " << i->m_age << endl;

  }  // end of ShowDetails

int main (void)
  {

  v.push_back (player ("Nick", 12));
  v.push_back (player ("Ksilyan", 25));
  v.push_back (player ("Meerclar", 42));
    
  // search for name
  ShowDetails (find (v.begin (), v.end (), "John"));
  ShowDetails (find (v.begin (), v.end (), "Ksilyan"));
  ShowDetails (find (v.begin (), v.end (), "Nick"));

  // search for age
  ShowDetails (find (v.begin (), v.end (), 42));

  return 0;
  } // end of main


Example Output

not found
age of Ksilyan = 25
age of Nick = 12
age of Meerclar = 42

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Nick Gammon   Australia  (23,046 posts)  Bio   Forum Administrator
Date Reply #5 on Wed 23 Jul 2003 03:33 AM (UTC)
Message
Quote:

I figured that since "string" had a find as a member function, the list class would too...


The general rule is that the algorithms (look up algorithm in MSDN) are the general cases which can be used with practically any container - excepting the limitations, eg. that you need random-access containers for sorting.

However in some cases, the container itself has its own function of the same name, which, if it exists, is generally more efficient.

Thus, maps have find, which find using their knowledge of the the structure of maps, and work in logarithmic time, however you could also use the general case (algorithm) find, however as the general case doesn't know it has a map (as you only pass the iterator, not the container) they would work in linear time (ie. do a linear search).

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Nick Gammon   Australia  (23,046 posts)  Bio   Forum Administrator
Date Reply #6 on Wed 23 Jul 2003 06:09 AM (UTC)
Message
I have been trying to get mem_fun_ref to work as advertised in the book and various web pages, but are hitting snags. For the record, this works under Linux but won't compile under MS VC++:


#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <iostream>

using namespace std;

class player
  {

  public:

    player (const string name, const int age)
      : m_name (name), m_age (age) {};

    bool IsName (const char * name) { return name == m_name; };

    string  m_name;
    int     m_age;

  };  // end of  class player


vector<player> v;

void ShowDetails (vector<player>::const_iterator i)
  {

  if (i == v.end ())
    cout << "not found" << endl;
  else
    cout << "age of " << i->m_name << " = " << i->m_age << endl;

  }  // end of ShowDetails

int main (void)
  {

  v.push_back (player ("Nick", 12));
  v.push_back (player ("Ksilyan", 25));

  ShowDetails (find_if (v.begin (), v.end (),
               bind2nd ( mem_fun_ref (&player::IsName), "Nick")));


  return 0;
  } // end of main


Example Output

age of Nick = 12


I am attempting to get STL to use a member function (IsName), use bind2nd to find an actual name (Nick) and use that in find_if.

Either my technique is wrong, and gcc shouldn't compile, or (more likely) the MS compiler does not support that level of sophistication in template instantation (is that a word?).
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Nick Gammon   Australia  (23,046 posts)  Bio   Forum Administrator
Date Reply #7 on Thu 24 Jul 2003 01:54 AM (UTC)

Amended on Thu 24 Jul 2003 02:00 AM (UTC) by Nick Gammon

Message
After about 2 days of research I have finally worked out how to make the above examples more general. :)

What I disliked about my earlier examples of finding a player by name was you had to use one of:


  • A specially-constructed function object (player_name_equal) whose only job was to test if a player name equalled something; or

  • An operator== which looks a bit weird, and in any case would only allow for one sort of thing to be tested (eg. if you had 10 integer types (as member values), overloading operator== (int) would only work for one of them); or

  • A member function (IsName) which was only added to the class to find if a name equalled something.



I thought all of the above lacked generality, and also couldn't be used - without more work - to find other things (eg. all players with age < 22).

The example below compiles and runs, with a couple of caveats. ;)

The Microsoft Visual C++ version 6 compiler, as shipped, did not support the use of mem_fun_ref in the way I wanted to use it (kept giving compiler errors) and did not have support for compose1, which was also needed.

I eventually did what was recommended in Scott Meyers' book "Effective STL" and download the SGI version of STL from:


http://www.sgi.com/tech/stl/


I then changed the MS compiler's include path to look first in the SGI STL directory, and then its normal directories (Tools menu -> Options -> Directories).

This then allowed the program below to compile. However under gcc on Red Hat Linux it did not support compose1 (although the other parts worked) because that was an STL extension. Thus, the code below has the appropriate template hard-coded into it. You could avoid that by, for instance, using the SGI version of STL under Linux as well.



How it works

The line that took a long time to get working is this one:


  ShowDetails (find_if (v.begin (), v.end (),
                compose1 (bind2nd (equal_to<string> (), "Nick"), 
                          mem_fun_ref ( &player::GetName ))
               ));


I wanted to be able to find anything (in this case "Nick") using any member function (in this case GetName) and use that in any comparison (in this case equal_to).

The line could be simplified a bit to be this:


vector<player>::const_iterator i;

i = find_if (v.begin (), v.end (),
             compose1 (bind2nd (equal_to<string> (), "Nick"), 
                       mem_fun_ref ( &player::GetName ))
            );


The important part is the predicate (something returning true or false) that is passed to find_if. That is:



compose1 (bind2nd (equal_to<string> (), "Nick"), 
          mem_fun_ref ( &player::GetName ))


What we need here are two function calls:


  • GetName - to get each player's name
  • equal_to - to compare it to our target name


mem_fun_ref makes a temporary function object which allows us to call the member function by reference (as opposed to by a pointer) hence its name.

We then need to call equal_to<string> (to compare two strings) taking the returned name, and comparing it to "Nick".

bind2nd binds the word "Nick" as the 2nd argument to equal_to.

Finally, compose1 takes two functions, it calls the second function first (ie. GetName) and then passes the result of it to the first function (equal_to).

The net result is that we compare each name in the vector and find a result.

Now to demonstrate how it can be more generally used the next line finds by a different criteria ...


  ShowDetails (find_if (v.begin (), v.end (),
                compose1 (bind2nd (equal_to<int> (), 88), 
                          mem_fun_ref ( &player::GetAge ))
               ));


This uses the same general idea, but now it calls GetAge to find the player's age, and equal_to<int> to do the comparison.

Finally the remove_copy_if line demonstrates how you can apply a test over a range, and display the results:


  remove_copy_if (v.begin(), v.end(), 
                  ostream_iterator<player>(cout), 
                  not1 (
                    compose1 (bind2nd (greater<int> (), 25), 
                              mem_fun_ref ( &player::GetAge ))
                       )
                  );


This time we are looking for ages greater than 25, hence the function greater<int> is used. However because remove_copy_if copies everyone *except* those matching, we need to negate the sense of the test by throwing in another function adapter - not1. This negates a unary argument.

Have fun playing with this - I hope it is helpful to someone, as it took a lot of work to research. :)


// disable warnings about long names
#ifdef WIN32
  #pragma warning( disable : 4786)
#else
  #include <iostream>  // seems to clash on Windows
#endif

#include <string>
#include <algorithm>
#include <functional>
#include <iterator>
#include <vector>

using namespace std;			

// SGI extension for Linux etc.

#ifndef WIN32


  // unary_compose (extension, not part of the standard).

  template <class _Operation1, class _Operation2>
  class unary_compose
    : public unary_function<typename _Operation2::argument_type,
                            typename _Operation1::result_type>
  {
  protected:
    _Operation1 _M_fn1;
    _Operation2 _M_fn2;
  public:
    unary_compose(const _Operation1& __x, const _Operation2& __y)
      : _M_fn1(__x), _M_fn2(__y) {}
    typename _Operation1::result_type
    operator()(const typename _Operation2::argument_type& __x) const {
      return _M_fn1(_M_fn2(__x));
    }
  };

  template <class _Operation1, class _Operation2>
  inline unary_compose<_Operation1,_Operation2>
  compose1(const _Operation1& __fn1, const _Operation2& __fn2)
  {
    return unary_compose<_Operation1,_Operation2>(__fn1, __fn2);
  }



#endif

class player
  {

  public:

    player (const string name, const int age)
      : m_name (name), m_age (age) {};

    // get player details
    string GetName () const { return m_name; };
    int    GetAge () const { return m_age; };

  private:

    string  m_name;
    int     m_age;

  };  // end of  class player

// ostream iterator for player class
ostream& operator<< (ostream& os, const player & p)
 {
 os << p.GetName () << ", age " << p.GetAge () << endl;
 return os;
 };  // end of ostream& operator<<

vector<player> v;

void ShowDetails (vector<player>::const_iterator i)
  {

  if (i == v.end ())
    cout << "not found" << endl;
  else
    cout << *i;

  }  // end of ShowDetails

int main (void)
  {

  v.push_back (player ("Nick", 12));
  v.push_back (player ("Ksilyan", 25));
  v.push_back (player ("Meerclar", 88));
  v.push_back (player ("Magnum", 42));

  // do a search based on the name (using GetName)
  ShowDetails (find_if (v.begin (), v.end (),
                compose1 (bind2nd (equal_to<string> (), "Nick"), 
                          mem_fun_ref ( &player::GetName ))
               ));
  
  // do a search based on the age (using GetAge)
  ShowDetails (find_if (v.begin (), v.end (),
                compose1 (bind2nd (equal_to<int> (), 88), 
                          mem_fun_ref ( &player::GetAge ))
               ));
  
  // display players in a range of ages
  cout << "players > 25 years old" << endl;
  remove_copy_if (v.begin(), v.end(), 
                  ostream_iterator<player>(cout), 
                  not1 (
                    compose1 (bind2nd (greater<int> (), 25), 
                              mem_fun_ref ( &player::GetAge ))
                       )
                  );

  return 0;
  } // end of main


Example Output

Nick, age 12
Meerclar, age 88
players > 25 years old
Meerclar, age 88
Magnum, age 42
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

20,849 views.

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum

[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

[Home]