Vector MergeSort Template error fixing

gralamin (4)
I have the following code with a few errors (That I do not know how to fix). The code replicates MergeSort for vectors. I know how to use sort() and merge(), but I am trying this method out of interest.

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
 
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;

template <class VectorType>
vector<VectorType> mergeSort(vector<VectorType> v)
{
     vector<VectorType> left;
     vector<VectorType> right;
     if (v.end() <= 1)//ERROR
     {
             return v;
     }
     else
     {
         typename vector<VectorType>::iterator mid; //Makes the complier see this as the whole type.
         typename vector<VectorType>::iterator it;
         mid = (v.end()-v.begin())/2;//ERROR
         
         for(it=v.begin(); it < mid; ++it)
         {
             left.push_back(*it);
         }
         
         for(it=mid; it < v.end(); ++it)
         {
              right.push_back(*it);
         }
         left = mergeSort(left); // Sort left half
         right = mergeSort(right); // Sort right Half
         v = mergeVec(left, right);//ERROR
         return v;
     }
}

template <class VectorType>
vector<VectorType> mergeVec(vector<VectorType> left, vector<VectorType> right)
{
           vector<VectorType> result;
           typename vector<VectorType>::iterator it;
           while ( ( (left.end()-left.begin()) > 0) && ( (right.end()-right.begin()) > 0))
           {
                 if (left.begin() <= right.begin())
                 {
                      result.push_back(left.begin());//ERROR
                      left.erase(left.begin());
                 }
                 else
                 {
                     result.push_back(right.begin());//ERROR
                     right.erase(right.begin());
                 }
           }
           if ( (left.end()-left.begin()) > 0)
           {
                for(it = left.begin(); it < left.end(); ++it)
                {
                       result.push_back(*it);
                }
           }
           if ( (right.end()-right.begin()) > 0)
           {
                for(it = right.begin(); it < right.end(); ++it)
                {
                       result.push_back(*it);
                }
           }
           
           return result;
}

int rInt();

int main()
{
    srand((unsigned)time(0));
    int a;
    
    cout << "Enter size of vector: \n>";
    cin >> a;
    cin.ignore();
    
    vector<int> v(a);
    vector<int>::iterator it;
    
    for (it=v.begin(); it!=v.end(); ++it)
    {
        *it = rInt();
        cout << *it << endl;
    }
    v = mergeSort<int>(v); //ERROR
    
    for (it=v.begin(); it!=v.end(); ++it)
    {
        cout << *it << endl;
    }
    
    system("PAUSE");
    return 0;
}

int rInt()
{
    int low = 1;
    int high = 10000;
    high += 1;
    low -= 1;
    int random, count = 0;
    int range = (high - low) + 1;
    do {
        random = (rand() % high) + low;
    } while (random >= high || random <= low);
    return random;
}


Everywhere there is "//ERROR" is an error I do not know how to fix. A compile log is below:
Compiler: Default compiler
Executing g++.exe...
g++.exe "H:\C++\Mergesort.cpp" -o "H:\C++\Mergesort.exe" -I"H:\Dev-Cpp\lib\gcc\mingw32\3.4.2\include" -I"H:\Dev-Cpp\include\c++\3.4.2\backward" -I"H:\Dev-Cpp\include\c++\3.4.2\mingw32" -I"H:\Dev-Cpp\include\c++\3.4.2" -I"H:\Dev-Cpp\include" -L"H:\Dev-Cpp\lib"
H:\C++\Mergesort.cpp: In function `std::vector<VectorType, std::allocator<_CharT> > mergeSort(std::vector<VectorType, std::allocator<_CharT> >) [with VectorType = int]':
H:\C++\Mergesort.cpp:94: instantiated from here
H:\C++\Mergesort.cpp:13: error: no match for 'operator<=' in '(&v)->std::vector<_Tp, _Alloc>::end [with _Tp = int, _Alloc = std::allocator<int>]() <= 1'

H:\C++\Mergesort.cpp:94: instantiated from here
H:\C++\Mergesort.cpp:21: error: no match for 'operator=' in 'mid = (__gnu_cxx::operator- [with _IteratorL = int*, _IteratorR = int*, _Container = std::vector<int, std::allocator<int> >](((const __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >&)((const __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >*)(&(&v)->std::vector<_Tp, _Alloc>::end [with _Tp = int, _Alloc = std::allocator<int>]()))), ((const __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >&)((const __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >*)(&(&v)->std::vector<_Tp, _Alloc>::begin [with _Tp = int, _Alloc = std::allocator<int>]())))) / 2)'

H:/Dev-Cpp/include/c++/3.4.2/bits/stl_iterator.h:587: note: candidates are: __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >& __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >::operator=(const __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >&)

H:\C++\Mergesort.cpp: In function `std::vector<VectorType, std::allocator<_CharT> > mergeVec(std::vector<VectorType, std::allocator<_CharT> >, std::vector<VectorType, std::allocator<_CharT> >) [with VectorType = int]':
H:\C++\Mergesort.cpp:34: instantiated from `std::vector<VectorType, std::allocator<_CharT> > mergeSort(std::vector<VectorType, std::allocator<_CharT> >) [with VectorType = int]'
H:\C++\Mergesort.cpp:94: instantiated from here
H:\C++\Mergesort.cpp:48: error: no matching function for call to `std::vector<int, std::allocator<int> >::push_back(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >)'
H:/Dev-Cpp/include/c++/3.4.2/bits/stl_vector.h:557: note: candidates are: void std::vector<_Tp, _Alloc>::push_back(const _Tp&) [with _Tp = int, _Alloc = std::allocator<int>]
H:\C++\Mergesort.cpp:34: instantiated from `std::vector<VectorType, std::allocator<_CharT> > mergeSort(std::vector<VectorType, std::allocator<_CharT> >) [with VectorType = int]'
H:\C++\Mergesort.cpp:94: instantiated from here
H:\C++\Mergesort.cpp:53: error: no matching function for call to `std::vector<int, std::allocator<int> >::push_back(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >)'
H:/Dev-Cpp/include/c++/3.4.2/bits/stl_vector.h:557: note: candidates are: void std::vector<_Tp, _Alloc>::push_back(const _Tp&) [with _Tp = int, _Alloc = std::allocator<int>]

Execution terminated



Thanks for the help!
Last edited on
Zaita (2770)
Line 13: Try if ( (int)v.size() < 1) { }
Line 21: You are trying to divide the result of a -. Try something like:
1
2
 
         unsigned int midCount = (unsigned int)(v.size() / 2);
         mid = v.begin() + midCount;

Line 48 & 53: Escape your iterator with (*X.begin())

That now compiles on my system. Didn't test it's functionality.

Compiled with Eclipse CDT and MingW GCC 3.4.5
gralamin (4)
Thanks, I'll give that a try.
gralamin (4)
Right, I get a segfault somewhere in the mergesort or mergeVec templates. Can anyone see where?
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
 
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;

template <class VectorType>
vector<VectorType> mergeSort(vector<VectorType> v)
{
     vector<VectorType> left;
     vector<VectorType> right;
     if ( (int)v.size() < 1)
     {
             return v;
     }
     else
     {
         typename vector<VectorType>::iterator mid; //Makes the complier see this as the whole type.
         typename vector<VectorType>::iterator it;
         unsigned int midCount = (unsigned int)(v.size() / 2);
         mid = v.begin() + midCount; 
         
         for(it=v.begin(); it < mid; ++it)
         {
             left.push_back(*it);
         }
         
         for(it=mid; it < v.end(); ++it)
         {
              right.push_back(*it);
         }
         left = mergeSort(left); // Sort left half
         right = mergeSort(right); // Sort right Half
         v = mergeVec(left, right);
         return v;
     }
}

template <class VectorType>
vector<VectorType> mergeVec(vector<VectorType> left, vector<VectorType> right)
{
           vector<VectorType> result;
           typename vector<VectorType>::iterator it;
           while ( ( (left.end()-left.begin()) > 0) && ( (right.end()-right.begin()) > 0))
           {
                 if (left.begin() <= right.begin())
                 {
                      result.push_back(*left.begin());
                      left.erase(left.begin());
                 }
                 else
                 {
                     result.push_back(*right.begin());
                     right.erase(right.begin());
                 }
           }
           if ( (left.end()-left.begin()) > 0)
           {
                for(it = left.begin(); it < left.end(); ++it)
                {
                       result.push_back(*it);
                }
           }
           if ( (right.end()-right.begin()) > 0)
           {
                for(it = right.begin(); it < right.end(); ++it)
                {
                       result.push_back(*it);
                }
           }
           return result;
}

int rInt();

int main()
{
    srand((unsigned)time(0));
    int a;
    
    cout << "Enter size of vector: \n>";
    cin >> a;
    cin.ignore();
    
    vector<int> v(a);
    vector<int>::iterator it;
    
    for (it=v.begin(); it!=v.end(); ++it)
    {
        *it = rInt();
        cout << *it << endl;
    }
    cout << "\n\nAbout to Mergesort.\n";
    system("PAUSE");
    
    v = mergeSort<int>(v);
    cout << "Mergesort Succesful.\n";
    system("PAUSE");
    
    cout << "Now outputting sorted values.\n";
    for (it=v.begin(); it!=v.end(); ++it)
    {
        cout << *it << endl;
    }
    
    system("PAUSE");
    return 0;
}

int rInt()
{
    int low = 1;
    int high = 10000;
    high += 1;
    low -= 1;
    int random, count = 0;
    int range = (high - low) + 1;
    do {
        random = (rand() % high) + low;
    } while (random >= high || random <= low);
    return random;
}
Zaita (2770)
MergeSort.

If you look at your code. It's not doing anything but making the vector smaller and smaller. Until the size becomes 1, and at this point it's in an infinite loop.

if ( (int)v.size() < 1) will never trigger, because your vector is never going to be smaller than 1.

The code you are populating your left/right is incorrect. 
1
2
3
4
 
     for(it=v.begin(); it < mid; ++it)
     {
         left.push_back((*it));
     }

Populate the left vector with HALF of the records that were passed into this function. Thats fine.

left = mergeSort(left); // Sort left half
Err... Pass our Left (Half the current) back into the function. Which will half it again, and re-cursively do this until the size is 1. Because wen you try to half 1 you get 0. So the left vector can never become .size() of 0.

:) You need to do more in MergeSort than just continually half the vectors.
gralamin (4)
Problem was with if ( (int)v.size() < 1). Changing it to if ( (int)v.size() <= 1) fixed it. Now I just need to figure out why it merged backwards.
And fixed by changing this from mergeVec if (left.begin() <= right.begin()) to if (*left.begin() <= *right.begin())
Last edited on
Zaita (2770)
For your escaping. You may prefer to use:
 
 
if ( (*left.begin()) <= (*right.begin()) )


instead of
if (*left.begin() <= *right.begin())
to make it clearer your escaping.
Last edited on
Topic archived. No new replies allowed.