STL

[korg]

Hi,

I had some queries regarding STL. I

1)Is it possible to compare two containers which are different types? i.e a Vector and set ?

2) If i were to compare two vectors or multimaps with custom data types, which operators i would have to overload ?

3)Is there any significance of < operator for sequence containers ??

Thanks!

[magnificence7]

2) You will have to overload the operators you want to use, probably ==, != <, <=, > and >=. The overloaded operators have to take vectors or multimaps as argument if you want to compare that class to a vector or multimap.

[jsmith]

1) You can write your own template function for that.

template< typename Iter1, typename Iter2 >
std::pair< Iter1, Iter2 > find_first_difference( Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2 ) {
    for( ; first1 != last1 && first2 != last2; ++first1, ++ first2 )
        if( *first1 != *first2 )
            return std::pair<Iter1, Iter2>( first1, first2 );
    return std::pair<Iter1, Iter2>( first1, first2 );
}

template< typename Iter1, typename Iter2, typename Comparator >
std::pair< Iter1, Iter2 > find_first_difference( Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, Comparator comp ) {
    for( ; first1 != last1 && first2 != last2; ++first1, ++ first2 )
        if( !comp( *first1, *first2 ) )
            return std::pair<Iter1, Iter2>( first1, first2 );
    return std::pair<Iter1, Iter2>( first1, first2 );
}

// Then:
std::vector<int> v;  // Assume filled out
std::set<int> s;   // Assume filled out

std::pair< std::vector<int>::iterator, std::set<int>::iterator > result = 
    find_first_difference( v.begin(), v.end(), s.begin(), s.end() );
if( result.first == v.end() && result.second == s.end() )
    std::cout << "Containers are the same" << std::endl;

2) All STL containers already implement operator== and operator!=. You just need
to make sure that your contained type is EqualityComparable.

3) The default ordering for sequence containers uses std::less<T>, which uses
T::operator<.

[korg]

correct me if i am wrong , but why is there ordering operator defined for sequence containers ? Or is it just so that it can be used with algorithms??

Shouldn't that be only for sorted associative containers such as map/set & family ?

Thanks for the replies... :)

[jsmith]

Sorry, you're correct. operator< is not used for SequenceContainers, but is for the ones you mentioned.

[kempofighter]

The containers themselves implement operator== and operator!=? That is news to me. I thought that you had to use the algorithm such as equal_range to compare containers. The question results in a fairly complex answer which requires the reader to understand the difference between equivalence and equality.
http://cplusplus.com/reference/algorithm/equal_range/
http://cplusplus.com/reference/algorithm/lexicographical_compare/
http://cplusplus.com/reference/algorithm/set_intersection/
http://cplusplus.com/reference/algorithm/set_difference/
http://cplusplus.com/reference/algorithm/find_first_of/

I recommend that you study those algorithms. They allow partial or full ranges to be compared. Some such as the "set_" algorithms fill new containers after comparing ranges of two existing containers. The operator that you will need in each case depends on whether the algorithm tests for equality (operator==) or equivalence (operator<). Alternatively most algorithms allow user defined functors to be specified which would implement the logic. therefore operator overloading is not always necessary.

[kempofighter]

Just to be clear operator < or some comparison functor is needed for sequence containers if you wish to sort them or use any algorithm that performs equivalence testing on each element.

[kempofighter]

Okay I looked it up in the C++ std. For vector all of these are supported. I did not know that until I looked. I did not see a reference to these on this site. So for any of these to work the underlying container element type has to support them. if you want to use functors then you'd use an algorithm which allows a functor to be specified.

template <class T, class Allocator>
bool operator==(const vector<T,Allocator>& x,
const vector<T,Allocator>& y);
template <class T, class Allocator>
bool operator< (const vector<T,Allocator>& x,
const vector<T,Allocator>& y);
template <class T, class Allocator>
bool operator!=(const vector<T,Allocator>& x,
const vector<T,Allocator>& y);
template <class T, class Allocator>
bool operator> (const vector<T,Allocator>& x,
const vector<T,Allocator>& y);
template <class T, class Allocator>
bool operator>=(const vector<T,Allocator>& x,
const vector<T,Allocator>& y);
template <class T, class Allocator>
bool operator<=(const vector<T,Allocator>& x,
const vector<T,Allocator>& y);

[korg]

Thanks kempfighter, i understand it better now.
A question surrounding the mechanism of algorithms & their use with custom data types. For example associative containers require < to be overloaded for comparison. The sort function above requires the same for sequence containers. etc etc.... So is there a specific subset of operators which almost always should be overloaded while working with custom data types in STL?

[korg]

Also need some help with my function object using an adapter.

#include <iostream>
#include <vector>
#include <iterator>
#include <cassert>
#include <list>
#include <map>
#include <set>
#include  <algorithm>
#include <functional>

using namespace std;

class U
{
    public:
       int data;
        U()
        {
            data = 0;
            //cout<<"Defalt const"<<endl;
        }
        U(int dat)
        {
            data = dat;
            //cout<<"Defalt const"<<endl;
        }
        U(const U& u)
        {
            data = u.data;
            //cout<<"Copy const"<<endl;
        }
        ~U()
        {
            //cout<<"Dest"<<endl;
        }


       friend bool operator<(const U& ip,const U& ip2);
       U& operator=(const U& ip2)
       {
           data = ip2.data;
           return *this;
       }

};

bool operator<(const U& ip,const U& op)
{
    cout<<" ip.data "<< ip.data<<" op.data "<<op.data<<endl;
     return ip.data < op.data;
}


bool myFunction(const U& ip,int comparison)
{
     return (ip.data > 20);
}



class myFun : public binary_function <U&,int,bool>
{
    public :
    bool operator()(U &input,int value)
    {
        return input.data > value;
    }

};




int main ()
{
    U u1(10);
    U u2(12);
    U u3(15);
    U u4(200);

    vector<U> myVec;
    myVec.push_back(u1);
    myVec.push_back(u2);
    myVec.push_back(u3);
    myVec.push_back(u4);
    myFun mfun;

    vector<U> myVec2(4);
http://www.cplusplus.com/forum/general/24934/
    vector<U>::iterator it = remove_copy_if(myVec.begin(),myVec.end(),myVec2.begin(),bind2nd(mfun(),10));
    vector<U>::iterator bit = myVec2.begin();


    while(bit!=it)
    {
        cout<<" "<<bit->data;
        bit++;
    }

     return 0;
}

The compilation is failing with no matching function call mfun()

[jsmith]

mfun

or

myFun()

[korg]

My bad myFun()

[kempofighter]

So is there a specific subset of operators which almost always should be overloaded while working with custom data types in STL?

The one thing that is always necessary is copying ability. Since the default operator= is sometimes good you don't always have to define it. In order to put objects within sequence containers they must be copyable via constructor and assignment. The most commonly overloaded operator that I have used is operator< for equivalence testing. I have rarely ever implemented operator== or any of the others, come to think of it but it would be necessary for things like equal_range or find operations. Just remember that if you are going to compare two vector objects using any relational operator that the underlying type must support it as well. Those operators should be implemented in terms of each other. For instance operator< is the opposite of operator>= therefore you don't write the code for both. You write the code only for one and then negate it within the other.

Keep in mind that technically you never have to overload the relational operators. It is only one option. In fact sometimes it is better to write a functor. For a complex user defined type operator< can only be used for one kind of comparison. So if you want to have the ability to change the sorting criteria and resort then you might need a few functors for your type. It doesn't hurt to have operator< defined so that you have some kind of default sorting criteria but you could handle it entirely with functors if you wish.

[kempofighter]

bool myFunction(const U& ip,int comparison)
{
     return (ip.data > 20);
}

Did you mean for this to compare with the "comparison" value? I think that what you are trying to do is to specify the value to compare against at the time of the algorithm call.

[korg]

Thanks for the reply!

Please disregard that snippet... i was trying to apply adaptors to functions :P

The current problem is only with the functor implementation.

I did not understand the following :
So if you want to have the ability to change the sorting criteria and resort then you might need a few functors for your type.

Are you suggesting that the parameter while defining the container can be done with a functor ?

Cheers!

[kempofighter]

This is long but hopefully proves my point in a variety of ways. This just proves that while the operator< can be used it doesn't have to be used. It also shows that with multiple functors you can resort over and over using different ones. However I don't think that you can change the functor associated with a container instance.

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>

//As we all know, any good Widget has both a speed and a weight property.
//moreover the default method for sorting a Widget container is by weight.
struct Widget
{
    Widget() : speed_(), weight_() {}
    bool operator<(const Widget& rhs)
    {
	return weight_ < rhs.weight_;
    }
    int speed_;  // Kilometers per hour
    int weight_; // Kilograms
};


std::ostream& operator<<(std::ostream& ostr, const Widget& rhs)
{
    ostr << "speed_: " << rhs.speed_ << ", weight_: " << rhs.weight_;
    return ostr;
}

// However - we don't need to use operator < at all.  
struct EvaluateSpeed
{
    bool operator()(const Widget& lhs, const Widget& rhs)
    {
	return lhs.speed_ < rhs.speed_;
    }
};

struct EvaluateWeight
{
    bool operator()(const Widget& lhs, const Widget& rhs)
    {
	return lhs.weight_ < rhs.weight_;
    }
};

int main()
{
    std::vector<Widget> widgets(10);
    for(int i = 0, size = widgets.size(); i < size; ++i)
    {
	widgets[i].speed_ = rand() % 100 + 1;
	widgets[i].weight_ = rand() % 100 + 1;
    }
    // print
    std::ostream_iterator<Widget> out_it (std::cout,"\n");
    std::copy ( widgets.begin(), widgets.end(), out_it );
    std::cout << std::endl;

    // sort default and print
    std::sort(widgets.begin(), widgets.end());
    std::copy ( widgets.begin(), widgets.end(), out_it );
    std::cout << std::endl;
    
    // sort speed with functor and print
    std::sort(widgets.begin(), widgets.end(), EvaluateSpeed());
    std::copy ( widgets.begin(), widgets.end(), out_it );
    std::cout << std::endl;

    // sort weight with functor and print - this proves that you never really needed
    // operator< at all.
    std::sort(widgets.begin(), widgets.end(), EvaluateWeight());
    std::copy ( widgets.begin(), widgets.end(), out_it );
    std::cout << std::endl;

    // one more thing.  Now create a std::set using the functor.  operator< is not
    // used at all by the set.  This is proven by fact that the set is sorted
    // by weight.  Notice that functor is specified as the sorter.
    std::set<Widget, EvaluateSpeed> widgetset(widgets.begin(), widgets.end());

    std::cout << "printing widget set" << std::endl;
    std::copy ( widgetset.begin(), widgetset.end(), out_it );
    std::cout << std::endl;

    return 0;
}

[kempofighter]

The current problem is only with the functor implementation.

It wasn't clear to me whether your example worked for you. I didn't try to compile it. Looks like you are trying to use bind to do something else with remove_copy_if. But that just uses operator< on int types so I am not sure what you are doing there. that might be a different problem with the proper usage of bind.

[korg]

Thats a wonderful example kempo. I'll agree with the fact that the sorting criteria for associative containers cannot be changed.

Let me clean up the code ;)

#include <iostream>
#include <vector>
#include <iterator>
#include <cassert>
#include <list>
#include <map>
#include <set>
#include  <algorithm>
#include <functional>

using namespace std;

class U
{
    public:
       int data;
        U()
        {
            data = 0;
            //cout<<"Defalt const"<<endl;
        }
        U(int dat)
        {
            data = dat;
            //cout<<"Defalt const"<<endl;
        }
        U(const U& u)
        {
            data = u.data;
            //cout<<"Copy const"<<endl;
        }
        ~U()
        {
            //cout<<"Dest"<<endl;
        }


       friend bool operator<(const U& ip,const U& ip2);
       U& operator=(const U& ip2)
       {
           data = ip2.data;
           return *this;
       }

};

bool operator<(const U& ip,const U& op)
{
    cout<<" ip.data "<< ip.data<<" op.data "<<op.data<<endl;
     return ip.data < op.data;
}


bool myFunction(const U& ip)
{
     return (ip.data > 20);
}



class myFun : public binary_function <U&,int,bool>
{
    public :
    bool operator()(U &input,int value)
    {
        return input.data > value;
    }

};




int main ()
{
    U u1(10);
    U u2(12);
    U u3(15);
    U u4(200);

    vector<U> myVec;
    myVec.push_back(u1);
    myVec.push_back(u2);
    myVec.push_back(u3);
    myVec.push_back(u4);
    myFun mfun;

    vector<U> myVec2(4);

    //vector<U>::iterator it = remove_copy_if(myVec.begin(),myVec.end(),myVec2.begin(),bind2nd(mfun,10));
    vector<U>::iterator it = remove_copy_if(myVec.begin(),myVec.end(),myVec2.begin(),myFunction);
    vector<U>::iterator bit = myVec2.begin();


    while(bit!=it)
    {
        cout<<" "<<bit->data;
        bit++;
    }

     return 0;
}

Here i am trying to achive the same thing which works with myFunction , which is a unary predicate. With the binary predicate , i am trying to pass the value against which it will be compared, since the algorithm accepts only unary functions, i am using a binder to pass it a value against which it will be compared.

I.e more flexibility of the function.

Cheers!

[jsmith]

If you can use boost, there is a one line solution:

#include <boost/bind.hpp>
#include <iterator>

vector<U>::iterator it = remove_copy_if( myVec.begin(), myVec.end(),
    std::back_inserter( myVec ), boost::bind( &U::data, _1 ) < 20 );

[korg]

Thanks jsmith! I am just trying to work out how custom functors are written with standard lib.... :)