C++

Forum

 
please explain

zoemayne (15)
multiple perspectives welcome..
i understand this code except for the application of the less and isLessThan
what exactly is going on here?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

template <typename Object, typename Comparator>
void insertionSort( vector<Object> & arr, Comparator isLessThan )
{
    for( int p = 1; p < arr.size( ); p++ )
    {
        Object tmp = arr[ p ];

        int j;
        for( j = p; j > 0 && isLessThan( tmp, arr[ j - 1 ] ); j-- )
        //please explain how can the isLessThan method be used if it is undefined. from my
 //understanding isLessthan is a Comparator variable and isLessThan is being used to compare if 
//tmp is less than arr[j-1]... but it's undefined so how can this be happening?

            arr[ j ] = arr[ j - 1 ];
        arr[ j ] = tmp;
    }
}

template <typename Comparable>
void insertionSort( vector<Comparable> & arr )
{
    insertionSort( arr, less<Comparable>( ) );//please explain
}


I understand everything here except for the isLessThan function.. where is it defined? same goes for the less function?
Last edited on
zoemayne (15)
ok i've searched and I see that less is from the operator class of the functional object but i still can not figure where isLessThan comes from.. please help.
eker676 (427)
There is a user defined typename/class somewhere called "Comparator".

isLessThan is an object/variable of the "Comparator" typename.

Are you sure there are no other files included?
zoemayne (15)
there are no other files included...
1
2
3
4
 
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
is exact. Comparator is only referred to only on the first two lines I've mentioned above specifically 
1
2
 
template <typename Object, typename Comparator>
void insertionSort( vector<Object> & arr, Comparator isLessThan )


I do have 2 seperate files called funObject1 and funObject2 which both defines isLessThan but its not referred to at all unless using namespace std refers to it (I'm not sure what using namespace std does).
Last edited on
zoemayne (15)
your right but I dont see where comparator is defined. heres the whole program.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

template <typename Object>
void printVector( const vector<Object> & s )
{
    for( int i = 0; i < s.size( ); i++ )
        cout << s[ i ] << " ";
    cout << endl;
}

template <typename Pointer>
void printVectorPtr( const vector<Pointer> & s )
{
    for( int i = 0; i < s.size( ); i++ )
        cout << *s[ i ] << " ";
    cout << endl;
}

template <typename Object, typename Comparator>
void insertionSort( vector<Object> & arr, Comparator isLessThan )
{
    for( int p = 1; p < arr.size( ); p++ )
    {
        Object tmp = arr[ p ];

        int j;
        for( j = p; j > 0 && isLessThan( tmp, arr[ j - 1 ] ); j-- )
            arr[ j ] = arr[ j - 1 ];
        arr[ j ] = tmp;
    }
}

template <typename Comparable>
void insertionSort( vector<Comparable> & arr )
{
    insertionSort( arr, less<Comparable>( ) );
}

class Shape
{
  public:
    virtual ~Shape( ) { }
    virtual double area( ) const = 0;
    virtual void print( ostream & out = cout ) const = 0;
};

ostream & operator<< ( ostream & out, const Shape & s ) 
{
    s.print( out );
    return out;
}

class Circle : public Shape
{
  public:
    explicit Circle( double r = 0.0 ) : radius( r )
    {
    }

    double area( ) const
    {
        return 3.14 * radius * radius;
    }

    void print( ostream & out = cout ) const
    {
        out << "[Circle with radius " << radius << "]";
    }

    bool operator< ( const Circle & rhs ) const
    {
        return radius < rhs.radius;
    }

  private:
    double radius;
};

class Rectangle : public Shape
{
  public:
    explicit Rectangle( double len = 0.0, double wid = 0.0 ) : length( len ), width( wid )
    {
    }

    double area( ) const
    {
        return length * width;
    }

    void print( ostream & out = cout ) const
    {
        out << "[Rectangle " << length << "-by-" << width << "]";
    }

  private:
    double length;
    double width;
};

class OrderShapeByArea
{
  public:
    bool operator() ( const Shape & lhs, const Shape & rhs ) const
    { return lhs.area( ) < rhs.area( ); }
};

class OrderShapePtrByArea
{
  public:
    bool operator() ( const Shape * lhs, const Shape * rhs ) const
    { return lhs->area( ) < rhs->area( ); }
};

int main( )
{
    vector<Circle> v1;
    v1.push_back( Circle( 3 ) );
    v1.push_back( Circle( 8 ) );
    v1.push_back( Circle( 4 ) );

    printVector( v1 );
    insertionSort( v1 );
    printVector( v1 );
    cout << endl;

    vector<Rectangle> v2;
    v2.push_back( Rectangle( 3, 5 ) );
    v2.push_back( Rectangle( 1, 10 ) );
    v2.push_back( Rectangle( 2, 7 ) );

    printVector( v2 );
    insertionSort( v2, OrderShapeByArea( ) );
    printVector( v2 );
    cout << endl;


    vector<Shape *> v3;
    v3.push_back( new Rectangle( 2, 3 ) );
    v3.push_back( new Circle( 1 ) );
    v3.push_back( new Rectangle( 1, 2 ) );
    printVectorPtr( v3 );
    insertionSort( v3, OrderShapePtrByArea( ) );
    printVectorPtr( v3 );
    cout << endl;

    for( int i = 0; i < v3.size( ); i++ )
        delete v3[ i ];
        std::cout << "Press ENTER to continue...";
        std::cin.ignore( std::numeric_limits<std::streamsize>::max(), '\n' );
    return 0;
}
guestgulkan (2942)
What you are seeing here is the use of function objects.
less is an example of function object and is one of many used in the C++ STL.
zoemayne (15)
i understand that but how is isLessThan being used here if it is not in the C++ STL and it is not being defined by the user.
guestgulkan (2942)
isLessThan is just a templatetypename in the sameway that Object
is just a typename.
he could just have used the name XXXX
zoemayne (15)
correct i meant to ask where is the comparator type defined. i know its user defined function cause its not in the stl
eker676 (427)
Comparator is just another name (same as what guestgulkan posted)

Look in this line
template <typename Object, typename Comparator>

Comparator could be any name.
Duthomhas (13200)
When you want to give a new name to some type of thing, for example:
1
2
 
typedef unsigned int uint;
// the type 'unsigned int' is now also known by the alias 'uint'

it can be done. The typedef statement has a global effect -- everything after it recognizes the new type name as an alias for the other type.

In generic programming, the idea is to extend this power in two ways:
1. make a typedef local to a specific construct (or function)
2. make it work on multiple types

To explain those, here is a simple example:
1
2
3
4
5
6
7
8
9
10
 
// A handy function to add a vector of integers
//
int SumIntVector( const vector <int> & v )
  {
  vector <int> ::const_iterator i;
  int result = 0;
  for (i = v.begin(); i != v.end(); ++i)
    result += *i;
  return result;
  }

However, suppose we have a vector of floats that we wish to sum? We'd have to write yet another function:
1
2
3
4
5
6
7
8
9
10
 
// A handy function to add a vector of floats
//
float SumFloatVector( const vector <float> & v )
  {
  vector <float> ::const_iterator i;
  float result = 0.0;
  for (i = v.begin(); i != v.end(); ++i)
    result += *i;
  return result;
  }

You'll notice that there are only two things different between the functions: the type of the thing being summed (int or float), and the literal constant used as the initial value (line 6).

Consider that this function might be useful to sum a vector of chars, or any other type where addition is defined on it. To do this, we can create a template function that has the type of object it operates over automatically typedefed:
1
2
3
4
5
6
7
8
9
 
template <typename Summable>
Summable SumVector( const vector <Summable> & v )
  {
  typename vector <Summable> ::const_iterator i;
  Summable result = Summable();
  for (i = v.begin(); i != v.end(); i++)
    result += *i;
  return result;
  }

The type 'Summable' doesn't actually exist. It is typedefed when used (condition 2). And it is only typedefed in the definition of the template function (condition 1).

In fact, the function itself doesn't exist until it is used. Hence, it is a template used by the compiler to create a function when needed.


So, in your above posting, the Comparable type is an alias for some type of thing that can be compared (using the less template function, which is a fancy way of writing the < operator); and the Comparator type is an alias for a function that compares two Objects. Such function must exist when you call (and thus cause the compiler to create) the two-argument insertionSort() function.

Hope this helps.
Topic archived. No new replies allowed.