Append, Merge, & Sort

[therpgking]

So, my assignment is about writing a function to append vector b to the end of vector a into the third vector and follow up by returning the third vector. It offers two examples of completing it:

First example:

vector<int> append(vector<int> a, vector<int> b)
{
    vector<int> c;
    int i;

    for (i = 0; i < a.size(); i++)
        c.push_back(a[i]);

    for (i = 0; i < b.size(); i++)
        c.push_back(b[i]);

    return c;
}

and the second example:

vector<int> append(vector<int> a, vector<int> b)
{
    int n = a.size();
    int m = b.size();
    vector<int> c(n + m);
    int i;

    for (i = 0; i < n; i++)
        c[i] = a[i];

    for (i = 0; i < m; i++)
        c[n + i] = b[i];

    return c;
}

The first part of the assignment asks for us to create a main() to call and test the append(). The main() will prompt the user to enter a (until -1 is entered) and b (also, until -1 is entered). We assume the values will be positive. Then the main() will call the append() and print the results.

The second part of the assignment asks for us to create a function
vector<int> merge(vector<int> a, vector<int> b)
to merge two vectors (a and b) alternating their elements in a third vector. If a vector is shorter than the other, the program will alternate as long as you can and then will append the remaining elements from the longer vector. Then we have to modify the main() to call merge() as well on the same two input vectors.

The third and final part of the assignment asks for us again to create a function
vector<int> merge_sorted(vector<int> a, vector<int> b)
to merge two sorted vectors which will produce a new sorted vector. We have to keep an index into each of the vectors to indicate how much we have processed already. Each time, it will append the smallest unprocessed element and then advance into the index. Our example for this is that we have to sort the two vectors in the main() by using

sort(a.begin(), a.end());
sort(b.begin(), b.end()); 

examples for a would be (1 4 5 7 8 9 16) while the b examples would be (2 3 5 10). Finally, we will modify the main()to call sort() twice and call merge_sorted(). Oh, and we need to include algorithm to use sort().

[helios]

Cool. Any questions?

[therpgking]

How do I write the code for each

[keskiverto]

You could read the reference doc page of std::merge ...

[doug4]

I would start with the first part of the assignment. Don't ever worry about the 2nd and 3rd part until the 1st part is done.

Show us the code you have written and ask questions about the troubles you run into. Nobody here wants to do your homework for you, but we will help you when you get stuck.

Here's a hint You probably want to start with this:

#include <iostream>
#include <vector>

int main()
{
}

[therpgking]

My code is currently this:

#include <iostream>
#include <vector> // to use vectors in the program
#include <algorithm> // to use merge in the program

using namespace std;

vector<int> append(vector<int> a, vector<int> b)
{
    int n = a.size();
    int m = b.size();
    vector<int> c(n + m);
    int i;

    for (i = 0; i < n; i++)
    c[i] = a[i];
    for (i = 0; i < m; i++)
    c[n + i] = b[i];

    return c;
}

vector<int> merge(vector<int> a, vector<int> b)
{
    int n = a.size();
    int m = b.size();
    vector<int> c(n + m);
    int i;

    for (i = 0; i < n; i++)
    c[i] = a[i];
    for (i = 0; i < m; i++)
    c[n + i] = b[i];

    return c;
}

vector<int> merge_sorted(vector<int> a, vector<int> b)
{
    int n = a.size();
    int m = b.size();
    vector<int> c (n + m);
    int i;

    for (i = 0; i < n; i++)
    c[i] = a[i];
    for (i = 0; i < m; i++)
    c[n + i] = b[i];
    return c;
}

int main()
{
    cout << "Please, give the number(s) to be evaluated(enter -1 to end program): " << endl;
    vector<int> a;

    bool number = true;
    while (number)
    {
       int n;
       cin >> n;
       if (n == -1)
           number = false;
       else
           a.push_back(n);
    }

    cout <<" Please, give the other number(s) to be evaluated(enter -1 to end program): " << endl;
    vector<int> b;

    number = true;
    while (number)
    {
       int m;
       cin >> m;
       if (m == -1)
           number = false;
       else
          b.push_back(m);
    }

    vector<int> x = append (a,b);//reads appended numbers to user
    {
        int i;
        cout << "Appended numbers: ";
        for (i = 0; i < x.size(); i++)
        cout << x[i] << " ";
        cout << endl;
    }

    vector<int> y = merge (a,b);//reads merged numbers to user
    {
       //int i;
       cout << "Merged numbers: ";

       //for (i = 0; i < y.size(); ++i)
       //{
           //merge(a.begin(), a.end(), b.begin(), b.end(), y.begin());
       //}
       //cout << y[i] << " ";

       sort (a.end(), a.begin());
       sort (b.end(), b.begin());
       merge(a.end(), a.begin(), b.end(), b.begin(), y.begin());

       for (std::vector<int>::iterator it = y.begin(); it! = y.end(); ++it)
       cout << " " << *it << endl;
    }

    vector<int> z = merge_sorted(a,b);
    {
        a.insert (a.end(), b.begin(), b.end());
        sort (a.begin(), a.end());
        cout << "Sorted numbers: ";

        for (vector<int>::iterator it = a.begin(); it! = a.end(); ++it)
        cout << " " << *it << endl;
    }
}

As soon as I run it, a bunch of error messages appear for the bottom half of my code and I don't know how to fix it.

$ g++ -c AppendMergeSort.cpp
AppendMergeSort.cpp: In function ‘int main()’:
AppendMergeSort.cpp:112:56: error: could not convert ‘it’ from ‘std::vector<int>::iterator {aka __gnu_cxx::__normal_iterator<int*, std::vector<int> >}’ to ‘bool’
        for (std::vector<int>::iterator it = y.begin(); it! = y.end(); ++it)
                                                        
AppendMergeSort.cpp:112:58: error: expected ‘;’ before ‘!’ token
        for (std::vector<int>::iterator it = y.begin(); it! = y.end(); ++it)
                                                          
AppendMergeSort.cpp:112:60: error: expected primary-expression before ‘=’ token
        for (std::vector<int>::iterator it = y.begin(); it! = y.end(); ++it)
                                                            
AppendMergeSort.cpp:112:69: error: expected ‘)’ before ‘;’ token
        for (std::vector<int>::iterator it = y.begin(); it! = y.end(); ++it)
                                                                     
AppendMergeSort.cpp:112:73: error: name lookup of ‘it’ changed for ISO ‘for’ scoping [-fpermissive]
        for (std::vector<int>::iterator it = y.begin(); it! = y.end(); ++it)
                                                                         
AppendMergeSort.cpp:112:73: note: (if you use ‘-fpermissive’ G++ will accept your code)
AppendMergeSort.cpp:112:75: error: expected ‘;’ before ‘)’ token
        for (std::vector<int>::iterator it = y.begin(); it! = y.end(); ++it)
                                                                           
AppendMergeSort.cpp:122:52: error: could not convert ‘it’ from ‘std::vector<int>::iterator {aka __gnu_cxx::__normal_iterator<int*, std::vector<int> >}’ to ‘bool’
         for (vector<int>::iterator it = a.begin(); it! = a.end(); ++it)
                                                    
AppendMergeSort.cpp:122:54: error: expected ‘;’ before ‘!’ token
         for (vector<int>::iterator it = a.begin(); it! = a.end(); ++it)
                                                      
AppendMergeSort.cpp:122:56: error: expected primary-expression before ‘=’ token
         for (vector<int>::iterator it = a.begin(); it! = a.end(); ++it)
                                                        
AppendMergeSort.cpp:122:65: error: expected ‘)’ before ‘;’ token
         for (vector<int>::iterator it = a.begin(); it! = a.end(); ++it)
                                                                 
AppendMergeSort.cpp:122:69: error: name lookup of ‘it’ changed for ISO ‘for’ scoping [-fpermissive]
         for (vector<int>::iterator it = a.begin(); it! = a.end(); ++it)
                                                                     
AppendMergeSort.cpp:122:71: error: expected ‘;’ before ‘)’ token
         for (vector<int>::iterator it = a.begin(); it! = a.end(); ++it)
                                         

[keskiverto]

Compare these:
! =
and
!=

[therpgking]

I made the change to my code and was able to get the .o file for it and ran the program yet I am now getting a segmentation fault (core dumped) after it Appends the numbers. Here is the code:

#include <iostream>
#include <vector> // to use vectors in the program
#include <algorithm> // to use merge in the program

using namespace std;

vector<int> append(vector<int> a, vector<int> b)
{
    int n = a.size();
    int m = b.size();
    vector<int> c(n + m);
    int i;

    for (i = 0; i < n; i++)
    c[i] = a[i];
    for (i = 0; i < m; i++)
    c[n + i] = b[i];

    return c;
}

vector<int> merge(vector<int> a, vector<int> b)
{
    int n = a.size();
    int m = b.size();
    vector<int> c(n + m);
    int i;

    for (i = 0; i < n; i++)
    c[i] = a[i];
    for (i = 0; i < m; i++)
    c[n + i] = b[i];

    return c;
}

vector<int> merge_sorted(vector<int> a, vector<int> b)
{
    int n = a.size();
    int m = b.size();
    vector<int> c (n + m);
    int i;

    for (i = 0; i < n; i++)
    c[i] = a[i];
    for (i = 0; i < m; i++)
    c[n + i] = b[i];

    return c;
}

int main()
{
    cout << "Please, give the number(s) to be evaluated(enter -1 when complete): " << endl;
    vector<int> a;

    bool number = true;
    while (number)
    {
       int n;
       cin >> n;
       if (n == -1)
           number = false;
       else
           a.push_back(n);
    }

    cout <<" Please, give the other number(s) to be evaluated(enter -1 when complete): " << endl;
    vector<int> b;

    number = true;
    while (number)
    {
       int m;
       cin >> m;
       if (m == -1)
           number = false;
       else
          b.push_back(m);
    }

    vector<int> x = append (a,b);//reads appended numbers to user
    {
        int i;
        cout << "Appended numbers: ";
        for (i = 0; i < x.size(); i++)

        cout << x[i] << " ";
        cout << endl;
    }

    vector<int> y = merge (a,b);//reads merged numbers to user
    {
       int i;
       cout << "Merged numbers: ";

       for (i = 0; i < y.size(); ++i)
       {
           merge(a.begin(), a.end(), b.begin(), b.end(), y.begin());
       }
       cout << y[i] << " ";

       sort (a.end(), a.begin());
       sort (b.end(), b.begin());
       merge(a.end(), a.begin(), b.end(), b.begin(), y.begin());

       for (std::vector<int>::iterator it = y.begin(); it != y.end(); ++it)
       cout << " " << *it << endl;
    }
  
    vector<int> z = merge_sorted(a,b);//reads sorted numbers to user
    {
        a.insert (a.end(), b.begin(), b.end());
        sort (a.begin(), a.end());
        cout << "Sorted numbers: ";

        for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)
        cout << " " << *it << endl;
    }
}

[doug4]

What development environment are you using? A debugger will help you figure out where the code is core dumping, and if you stop execution right before the problem line, you can see what the variables' values are.

You are having a few issues with unnecessary scoping. You don't need curly braces around 83 - 90, 93 - 109 and 112-119. Those braces are benign (unless I'm missing something), and they make it look like you have a flow control construct or a function definition. You can declare a for loop counter like this:

for (int i = 0; i < max; ++i)

The value of i is available only within the for loop.

Again, I would suggest you look at 1 section at a time. Verify that you have append working. Comment out everything after append and see if you get the output you expect in lines 87 and 88. Then add in merge and see if that's working correctly. Last, add in merge_sorted and see if that's working correctly.

I strongly recommend using curlies on every if, else or loop block (even if it is only 1 line) so you know for sure what's being done in those cases. For instance, only line 88 is being iterated in the line 86 loop. Is that what you want? It might be, but adding curlies around the loop statements makes it easier to follow.

When you get there, line 99 looks really ugly. It says you are going to call std::merge on a and b for every element in y (which was created from the merged a and be by your function). I don't think that's what you really want to do. I suspect line 101 is what you want inside the loop.