C++ code to read, sort, and write data

Question

I had written code in C++ to create transformation filters to get input, sort (custom_sorting and existing sorting routine) and write the output to stdin and file. When I presented it to my teacher, he ran it on a considerably huge file and observed that my custom sorting routine took over 5 minutes to complete. He mentioned that instead of using hash maps to store the input and do the sorting, if I re-wrote the entire code using structs/classes in a more structured oriented way, I could get it to finish sorting within 10 seconds instead of 5 minutes. I am rusty when it comes to following a structured oriented approach. Can anyone help with re-writing the following code in a more structured oriented way using objects and classes/structs in C++?

#include <sstream>
#include <iostream>
#include <algorithm>
#include <string>
#include <unistd.h>
#include <sys/time.h>
#include <getopt.h>
#include <cstdlib>
#include <cctype>
#include <cstring>

#include <vector>
#include <fstream>

#include <map> 
#include <iterator>
#include <tr1/unordered_map>

using namespace std::tr1;
using namespace std;

vector <string> str;

 void
 custom_sort (vector <string> str, int num)
 {
     int round, r, i;
     for (round = 0; round < num; round++) {
         for (i = 0; i < num-1; i++) {
              r = str[i].compare(str[i+1]);
              if (r > 0) {


    string s = "";
                  s = str[i];
                  str[i] = str[i+1];
                  str[i+1] = s;
              }
          }
     }
 }

 string
 getField (string input_str, char ch, int fieldNum)
 {
    istringstream ss(input_str);
    string temp;
    string field;
    int count = 0;
    vector <string> input;
    while(getline(ss,temp,ch)) {
        if(count < fieldNum) {
                input.push_back(temp);
                count++;
        }
    }
    field = input.back();
//cout << "Hey this is the field : " << field << endl;
    return field;
  }

  int
  main(int argc, char** argv)
  {
       int c;
       int items = 0;
       unordered_map<string, vector<string> > output;
       unordered_map<string, vector<string> > custom_output;
       string action_variable = "";
       string input_variable = "";
       string output_variable = "";
       string separation_variable = "";
       int field_variable = 0;
       while(1) {
            int option_index = 0;
            struct option long_options[] = {
                {"action", required_argument, 0, 'a'},
                {"input", required_argument, 0, 'i'},
                {"output", required_argument, 0, 'o'},
                {"separator", required_argument, 0, 's'},
                {"field", required_argument, 0, 'f'},
            };
    c = getopt_long(argc, argv, "a:i:o:s:f:",long_options, &option_index);

    if (c == -1) {
            break;
    }

    switch (c) {
            case 'a':
                    action_variable = optarg;
                    cout << "action :" << action_variable << endl;
                    break;
            case 'i':
                    input_variable = optarg;
                    cout << "input :" << input_variable << endl;
                    break;
            case 'o':
                    output_variable = optarg;
                    cout << "output :" << output_variable << endl;
                    break;
            case 's':
                    separation_variable = optarg;
                    cout << "Separation variable :" << separation_variable << endl;
                    break;
            case 'f':
                    field_variable = atoi(optarg);
                    cout << "Field variable :" << field_variable << endl;
                    break;
            default:
                    cout <<  "Usage: myfilter --input arg  --action arg --output arg" << action_variable << endl;
                    exit(0);
    }
}

string name = "";
char ch = separation_variable[0];
ifstream myfile;
myfile.open (input_variable.c_str());
if (myfile.is_open()) {
        while(getline(myfile,name)) {
                string field = getField(name,ch,field_variable);
                output[field].push_back(name);
                custom_output[field].push_back(name);
                str.push_back(field);
                items++;
        }
        myfile.close();
}
else {
        cout << "Unable to open file. Enter values in the standard input" << endl;
        while (getline(cin,name)) {
                string field = getField(name,ch,field_variable);
                output[field].push_back(name);
                custom_output[field].push_back(name);
                str.push_back(field);
                items++;
        }
}

struct timeval tv1, tv2;
struct timeval qtv1, qtv2;
double start_time = gettimeofday(&tv1, NULL);

vector <string> custom_sort_output;
//sorting = custom sorting routine
custom_sort(str,items);
int strLength = str.size();
for(int i = 0; i < strLength; i++) {
        if(output.find(str[i]) != output.end()) {
                vector <string> temp = output[str[i]];
                int sz = temp.size();
                for(int j = 0; j < sz; j++) {
                        custom_sort_output.push_back(temp[j]);
                }
        }
}
double end_time = gettimeofday(&tv2, NULL);

double q_start_time = gettimeofday(&qtv1, NULL);
//sorting using an ordered_map
map <string,vector<string> > sorted_output(output.begin(), output.end());
double q_end_time = gettimeofday(&qtv2, NULL);
printf ("Total time to read, sort and display from standard input using my sorting routine = %f seconds\n",(double) (tv2.tv_usec - tv1.tv_usec) / 1000000 + (double) (tv2.tv_sec - tv1.tv_sec));
printf ("Total time to read, sort and display from standard input using my sorting routine = %f seconds\n",(double) (qtv2.tv_usec - qtv1.tv_usec) / 1000000 + (double) (qtv2.tv_sec - qtv1.tv_sec));

//printing the output
ofstream outputfile;
outputfile.open(output_variable.c_str());
if (outputfile.is_open()) {
        for( map<string, vector<string> >::iterator it = sorted_output.begin(); it != sorted_output.end(); ++it) {
                int length = it->second.size();
                for(int i = 0; i < length; i++) {
                        outputfile << it->second[i] << endl;
                }
        }
        outputfile.close();
}
else {
        for( map<string,vector<string> >::iterator it = sorted_output.begin(); it != sorted_output.end(); ++it) {
                int length = it->second.size();
                for(int i = 0; i < length; i++) {
                        outputfile << it->second[i] << endl;
                }
        }
}
return 0;
}

Answer 1

Your code doesn't seem to work. However, let's break down just the sort routine, since that's what you seem to think is the bottleneck.

using namespace std;

Get in the habit of not using namespace anything. Then you won't have to deal with reviewers incessantly telling you you're wrong for doing so.

---

vector <string> str;

 void
 custom_sort (vector <string> str, int num)

Red flag: You have a global variable named str, and then you have a function that takes an unrelated parameter named str. If the function is supposed to act on the global, then it shouldn't take any parameter. If the function is not supposed to act on the global, then its parameter shouldn't have the same name as the global.

One easy way to keep yourself from getting confused here is to always name your globals g_whatever. So,

std::vector<std::string> g_str;

void custom_sort(std::vector<std::string> str, int num)

Notice also the fully qualified names (no using namespace std!) and the whitespace placement (we're writing C++, not HTML).

---

void custom_sort(std::vector<std::string> str, int num)

Red flag number 2: Your custom_sort function takes a vector by value. This will be very inefficient (because it has to copy the whole vector). It also raises my original red flag — the reason I said your code doesn't work — because this is a void-returning function that takes no reference parameters and modifies no globals — in other words, this function has no side effects and returns no value. It's a complete no-op!

Knowing that, we don't even have to inspect the implementation of your sorting routine (which is basically bubblesort, which even Barack Obama knows is a bad idea). We know it can't be doing anything.

So what would we expect custom_sort to look like? Well, it should look something like this:

void custom_sort(std::vector<std::string>& str) {
    std::sort(str.begin(), str.end());
}

This might have been what your teacher was getting at (although since he didn't immediately notice that your code doesn't work, frankly I bet he's not the greatest or subtlest of teachers). In C++, we try to use existing algorithms, or build them up from smaller algorithms, as much as possible.

Another example of "building larger algorithms up from smaller algorithms" shows up inside your custom_sort routine (the routine we just completely replaced with std::sort). We can take this little piece of it—

    string s = "";
    s = str[i];
    str[i] = str[i+1];
    str[i+1] = s;

and replace it with a call to a routine that describes what it's actually trying to do — swap two objects.

    std::swap(str[i], str[i+1]);

(std::swap will also be much much faster than what you wrote.)

---

Furthermore, consider your code

              int r;
              r = str[i].compare(str[i+1]);
              if (r > 0) {

We can rewrite this as

              if (str[i] > str[i+1]) {

and eliminate the local variable r.

---

In general, you seem to be writing C89 code. As of C99 and C++98, you're allowed to write variable declarations at their point of initialization; as in, where you wrote

 int round, r, i;
 for (round = 0; round < num; round++) {
     for (i = 0; i < num-1; i++) {
          r = str[i].compare(str[i+1]);

a C++ programmer would write

 for (int round = 0; round < num; ++round) {
     for (int i = 0; i < num-1; ++i) {
          int r = str[i].compare(str[i+1]);

This style helps to make sure that you never use a variable that remained uninitialized by accident. In fact, if you initialize every variable to its actual useful value, then you basically never need mutation at all. You could equally well make everything const!

          const int r = str[i].compare(str[i+1]);

But it's typically idiomatic to leave off the const; I've only seen a few codebases that apply const rigorously to local variables.

---

This doesn't address your main routine at all, but I imagine that if you take these rules and apply them throughout your code, you'll be able to cut your main routine in half.

Also, please get a copy of The Elements of Programming Style and read it in your spare time! It will show you how to improve your code in the way I just did; and it works no matter whether you're programming in Fortran, PL/I, C, C++, Java, or Ruby. The fundamentals don't change.

Answer 2

custom_sort(str,items);
int strLength = str.size();
for(int i = 0; i < strLength; i++) {
        if(output.find(str[i]) != output.end()) {
                vector <string> temp = output[str[i]];
                int sz = temp.size();
                for(int j = 0; j < sz; j++) {
                        custom_sort_output.push_back(temp[j]);
                }
        }

As Quuxplusone pointed out, the first line, custom_sort(str,items) doesn't produce any result. It just spins for O(n²) time and discards the work done. So there’s a useless time sink right there.

Then, you have a loop that goes over the str collection badly. To iterate over the entire collection, you should use the range-for loop.

for (const auto& item : str) {

You refer to str[i] more than once, which duplicates work. Now, item is an alias to that so you can use it easily.

So what’s it do? It should not be a puzzle! Look for the item in output, and only if it is found then ???

    vector <string> temp = output[str[i]];

Given that you defined

unordered_map<string, vector<string> > output;
unordered_map<string, vector<string> > custom_output;

Looking up the key will give the current value, which you copy (the entire vector of strings) into temp.

    int sz = temp.size();
    for(int j = 0; j < sz; j++) {
            custom_sort_output.push_back(temp[j]);

You iterate over that vector (again, see note from outer loop) and add each string to custom_sort_output.

So, nothing in there does any sorting. Given that output is already populated, it selects only those items listed in str and joins all of them together.

Looking back, I see where they are populated:

    while(getline(myfile,name)) {
            string field = getField(name,ch,field_variable);
            output[field].push_back(name);
            custom_output[field].push_back(name);
            str.push_back(field);
            items++;

For each name read from the file, find out what field it belongs to and store it in that slot in output. And, keep track of all field values in str.

I see what you intended now: if you had sorted str in-place, then you would be listing the fields’ contents in that order.

Note that if you used a regular std::map for output, then just iterating over it would already be in order.

---

Things to work on

First, write smaller functions! Don’t meander all over the place. A function does one thing; has one responsibility. In your main there are clearly different zones where you could just cut it apart into different functions.

Second, declare variables where used (and initialized). This will go a long way to being able to see if you have things unused or mixed up, and easily find what is being worked on in a short passage.

Third, understand how to use the collections in the standard library. Know about iterators and algorithms.

if(output.find(str[i]) != output.end()) {
            vector <string> temp = output[str[i]];

You look it up, then ignore the result if found, then look it up again in the next line! What is the return value from find? The thing it found!

auto& temp = output.find(str[1]);
if (temp == output.end())  continue;  // not expecting this to happen

Good luck — Keep studying and asking for critical feedback outside of class!!

Answer 3

Summary of improvements to my code (from other answers):

To run the following code, do the following:

1. g++ -c program_name.cpp 
   

2. g++ program_name.o -o program_name
   

3. ./program_name -–input input.txt --action sort --output output.txt -s , -f 1 2.
   

---

#include <sstream>
#include <iostream>
#include <algorithm>
#include <string>
#include <unistd.h>
#include <sys/time.h>
#include <getopt.h>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <vector>
#include <fstream>
#include <iterator>

using namespace std;

struct SortNode{
        string field1;
    string field2;
        string sentence;
};

vector <SortNode> str;
vector <SortNode> custom_str;

bool 
field1compare(const SortNode &a, const SortNode &b)
{
    return a.field1 < b.field1;
}

bool 
field2compare(const SortNode &a, const SortNode &b) 
{
    return a.field2 < b.field2;
}

void
custom_sort (int which_variable, int beginning, int end)
{
    int num = custom_str.size();
    int round, r, i;
    for (round = beginning; round < end; round++) {
        for (i = beginning; i < end-1; i++) {
        if (which_variable == 1) {
                    r = custom_str[i].field1.compare(custom_str[i+1].field1);
        }
        else {
            r = custom_str[i].field2.compare(custom_str[i+1].field2);
        }
                if (r > 0) {
                    swap(custom_str[i], custom_str[i+1]);
        }
        }
    }
}

void 
sort_again (int field_variable2) {
    int numItems = str.size();
        int count = 1;
        int track = 0;
        int beg = 0;
    if(field_variable2 != 0) {
                while (track < numItems-1) {
                        while ( (track < numItems - 1) && str[track].field1 ==  str[track+1].field1) {
                                if (count == 1) {
                                        beg = track;
                                }
                                count++;
                                track++;
                        }
                        sort(str.begin() + beg, str.begin() + beg + count, field2compare);
            custom_sort(2,beg,beg + count);
                        count = 1;
                        track++;
                }
        }
}


string
getField (string input_str, char ch, int fieldNum)
{
        istringstream ss(input_str);
        string temp;
        string field;
        int count = 0;
        vector <string> input;
        while(getline(ss,temp,ch)) {
                if(count < fieldNum) {
                        input.push_back(temp);
                        count++;
                }
        }

        field = input.back();
        return field;
}

void
getInput(char ch, string input, int field_variable1, int field_variable2) 
{
    string name = "";
    ifstream myfile;
    myfile.open(input.c_str());
    if (myfile.is_open()) {
        while (getline (myfile,name)) {
            SortNode snode;
            snode.field1 = getField(name,ch,field_variable1);
            if (field_variable2 != 0) {
                snode.field2 = getField(name,ch,field_variable2);
            }
            else {
                snode.field2 = "";
            }
            snode.sentence = name;
            str.push_back(snode);
            custom_str.push_back(snode);
        } 
        myfile.close();
    }
    else {
        cout << "Not a file or unable to open a file. Enter values in the standard input" << endl;
        while (getline(cin,name)) {
                        SortNode snode;
                        snode.field1 = getField(name,ch,field_variable1);
                        if (field_variable2 != 0) {
                                snode.field2 = getField(name,ch,field_variable2);
                        }
                        else {
                                snode.field2 = "";
                        }
                        snode.sentence = name;
                        str.push_back(snode);
                        custom_str.push_back(snode);
        }
    }
}

void writeOutput (string output) {
    int items = str.size();
    ofstream outputfile;
    outputfile.open(output.c_str());
    if (outputfile.is_open()) { 
        for (int i = 0; i < items; i++) { 
            outputfile << "Field 1: " << custom_str[i].field1 << " Field 2: " << custom_str[i].field2 << " Sentence is :" << custom_str[i].sentence << endl;
        }   
    outputfile.close();   
    }
    else {
        for (int i = 0; i < items; i++) {
                        cout << "Field 1 : " << str[i].field1 << " Field 2: " << str[i].field2 << " Sentence is :" << str[i].sentence << endl;
                }
    }
}

int
main (int argc, char** argv) 
{
    int c;
        string action_variable = "";
        string input_variable = "";
        string output_variable = "";
        string separation_variable = "";
        int field_variable = 0;
    int field_variable2 = 0;
        while(1) {
                int option_index = 0;
                struct option long_options[] = {
                        {"action", required_argument, 0, 'a'},
                        {"input", required_argument, 0, 'i'},
                        {"output", required_argument, 0, 'o'},
                        {"separator", required_argument, 0, 's'},
                        {"field", required_argument, 0, 'f'},
                };

                c = getopt_long(argc, argv, "a:i:o:s:f:",long_options, &option_index);

                if (c == -1) {
                        break;
                }

                switch (c) {
                        case 'a':
                                action_variable = optarg;
                                cout << "action :" << action_variable << endl;
                                break;
                        case 'i':
                                input_variable = optarg;
                                cout << "input :" << input_variable << endl;
                                break;
                        case 'o':
                                output_variable = optarg;
                                cout << "output :" << output_variable << endl;
                                break;
                        case 's':
                                separation_variable = optarg;
                                cout << "Separation variable :" << separation_variable << endl;
                                break;
                        case 'f':
                                field_variable = atoi(optarg);
                if(argv[optind])
                    field_variable2 = atoi(argv[optind++]);
                                cout << "Field variable :" << field_variable << endl;
                cout << "Field variable 2: " << field_variable2 << endl;
                                break;
            default:
                 cout <<  "Usage: myfilter --input arg  --action arg --output arg" << action_variable << endl;
                                exit(0);
        }   
    }

    //Get the input in a vector
    char ch = separation_variable[0];
    getInput(ch, input_variable, field_variable, field_variable2);  

    //Sort the input
    struct timeval tv1, tv2;
    //my sorting routine
    double start_time = gettimeofday(&tv1, NULL);
    custom_sort(1, 0, custom_str.size());
    double end_time = gettimeofday(&tv2, NULL);


    printf ("Total time to read, sort and display from standard input using my sorting routine = %f seconds\n",(double) (tv2.tv_usec - tv1.tv_usec) / 1000000 + (double) (tv2.tv_sec - tv1.tv_sec));

    //sort method
    struct timeval qtv1, qtv2;
    double q_start_time = gettimeofday(&qtv1, NULL);
    sort(str.begin(), str.end(), field1compare);
    double q_end_time = gettimeofday(&qtv2, NULL);

    //sorting by the second field_variable 
    sort_again(field_variable2);
    printf ("Total time to read, sort and display from standard input using my sorting routine = %f seconds\n",(double) (qtv2.tv_usec - qtv1.tv_usec) / 1000000 + (double) (qtv2.tv_sec - qtv1.tv_sec));

    //Write the output to stdin/file
    writeOutput(output_variable);
    return 0;
}