Sort One Vector Based on the Elements of Another Vector With no Class or Struct

Question

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

const int max_applications_num = 1000;

vector<string> vector_authors;
vector<string> vector_titles;
vector<string> vector_venue;
vector<int> vector_year;
vector<string> vector_presentation;

void Tokenize(string line, vector<string> &tokens, string delimiters = "\t ") {
    string token = "";
    string OneCharString = " ";
    for (int i = 0; i < line.size(); i++)
        if (find(delimiters.begin(), delimiters.end(), line[i]) !=
            delimiters.end()) // line[i] is one of the delimiter characters
        {
            if (token != "")
                tokens.push_back(token);
            token = "";
        } else {
            OneCharString[0] = line[i];
            token += OneCharString;
        }

    if (token != "")
        tokens.push_back(token);
}

void SaveApplication(const vector<string> &tokens) {

    string authors = tokens[1];
    string title = tokens[2];
    string venue = tokens[3];
    int year = atoi(tokens[4].c_str());
    string presentation = tokens[5];

    vector_authors.push_back(authors);
    vector_titles.push_back(title);
    vector_venue.push_back(venue);
    vector_year.push_back(year);
    vector_presentation.push_back(presentation);

    // cout << "in save" << endl;
}

void remove_application(int pos) {

    vector_authors.erase(vector_authors.begin() + pos);
    vector_titles.erase(vector_titles.begin() + pos);
    vector_venue.erase(vector_venue.begin() + pos);
    vector_year.erase(vector_year.begin() + pos);
    vector_presentation.erase(vector_presentation.begin() + pos);

    // cout << "in remove" << endl;
}

void sort() {
    for (int j = 0; j <= vector_year.size() - 1; j++) {

        int temp1 = vector_year.at(j);
        int i = j - 1;
        while (i > -1 and vector_year.at(i) > temp1) {
            vector_year.at(i + 1) = vector_year.at(i);
            i = i - 1;
        }
        vector_year.at(i + 1) = temp1;
    }

    for (int j = 0; j <= vector_authors.size() - 1; j++) {
        string temp2 = vector_authors.at(j);
        int i = j - 1;
        while (i > -1 and vector_authors.at(i) > temp2) {
            vector_authors.at(i + 1) = vector_authors.at(i);
            i = i - 1;
        }
        vector_authors.at(i + 1) = temp2;
    }

    for (int j = 0; j <= vector_titles.size() - 1; j++) {
        string temp3 = vector_titles.at(j);
        int i = j - 1;
        while (i > -1 and vector_titles.at(i) > temp3) {
            vector_titles.at(i + 1) = vector_titles.at(i);
            i = i - 1;
        }
        vector_titles.at(i + 1) = temp3;
    }
    for (int j = 0; j <= vector_venue.size() - 1; j++) {
        string temp4 = vector_venue.at(j);
        int i = j - 1;
        while (i > -1 and vector_venue.at(i) > temp4) {
            vector_venue.at(i + 1) = vector_venue.at(i);
            i = i - 1;
        }
        vector_venue.at(i + 1) = temp4;
    }
    for (int j = 0; j <= vector_presentation.size() - 1; j++) {
        string temp5 = vector_presentation.at(j);
        int i = j - 1;
        while (i > -1 and vector_presentation.at(i) > temp5) {
            vector_presentation.at(i + 1) = vector_presentation.at(i);
            i = i - 1;
        }
        vector_presentation.at(i + 1) = temp5;
    }

    // cout << "in sort" << endl;
}

void print() {

    for (int i = 0; i < vector_authors.size(); i++) {
        cout << vector_authors.at(i) << "\t" << vector_titles.at(i) << "\t"
             << "\t" << vector_venue.at(i) << "\t" << vector_year.at(i) << "\t" << vector_presentation.at(i) << endl;
    }
    cout << "\n" << endl;
}

void ExecuteCommands(const char *fname) {
    ifstream inf;
    inf.open(fname);

    string line;
    while (getline(inf, line).good()) {
        vector<string> tokens;
        Tokenize(line, tokens, "\t ");
        if (tokens.size() == 0)
            continue;

        if (tokens[0].compare("save_application") == 0)
            SaveApplication(tokens);

        else if (tokens[0].compare("remove_application") == 0)
            remove_application(atoi(tokens[1].c_str()));

        else if (tokens[0].compare("sort") == 0)
            sort();

        else if (tokens[0].compare("print") == 0)
            print();
    }

    inf.close();
}

int main(int argc, char **argv) {
    if (argc != 2) {
        cout << "usage: executable.o command.txt\n";
        return 1;
    }

    ExecuteCommands(argv[1]);
    return 0;
}

So, here is my code for a lab I am doing at school. We are supposed to put certain elements in a vector, print those vectors, order them, print them again, remove a vector, print them one last time. For our sort, we need to order them based on the year of publication.

"authors_list1" "title1" "conference1"  2016    "poster"
"authors_list3" "title3" "conference2"  2010    "oral"
"authors_list2" "title2" "journal1" 2015    "none"

So, when I sort, I get this:

"authors_list1" "title1" "conference1"  2010    "none"
"authors_list2" "title2" "conference2"  2015    "oral"
"authors_list3" "title3" "journal1" 2016    "poster"

This is the expected output:

"authors_list3" "title3"    "conference2"   2010    "oral"
"authors_list2" "title2"    "journal1"  2015    "none"
"authors_list1" "title1"    "conference1"   2016    "poster"

The order of the years are correct, but the orders of everything else are not. I need my other elements to follow suit with the years. Is there any way to do that?

P.S. For this lab, we are not allowed to use classes or structs. This is all the code I have.

Unrelated to your question, but instead of multiple vectors, why don't you use a *structure* and a single vector to contain it? Might make sorting a little easier actually. — Some programmer dude, Oct 03 '17 at 00:12
We are not allowed. The lab specifies no structs or classes. — J.Khelly, Oct 03 '17 at 00:14
Depending on how closely you feel like following the letter of the law vs the spirit, you could use tuples. — Mike Precup, Oct 03 '17 at 00:15
And please *edit your question* to include the expected (as well as the actual) output. Or other crucial or relevant details. — Some programmer dude, Oct 03 '17 at 00:16
You see below the tags of your question, there's a line containing the word `edit`? Click it that word. — Some programmer dude, Oct 03 '17 at 00:19
@J.Khelly [Please read this answer](https://stackoverflow.com/questions/46382252/sort-array-by-first-item-in-subarray-c/46382976#46382976). Your data falls in the "clumsy" category. All you need is an array of indices. No struct or class is needed. — PaulMcKenzie, Oct 03 '17 at 00:26
@J.Khelly Read the answer. All you need is an array of integers initially numbered from 0 to `n-1`. Sort **that** array based on the criteria, not 5 separate arrays. It's probably the trick that you're teacher is looking for, and I almost feel bad giving the answer away. — PaulMcKenzie, Oct 03 '17 at 00:34
So i sort one array, and use those positions as the ones for my vectors? — J.Khelly, Oct 03 '17 at 00:39
@J.Khelly - after you create and sort an array or vector of indices according to one of the vectors, it is then possible to sort the vectors in place according to the array or vector of sorted indices, with time complexity O(n). See [this complete example](https://stackoverflow.com/questions/40392384/sorting-three-vectors-based-on-the-arrangement-of-one-with-duplicates/40392827#40392827) . — rcgldr, Oct 03 '17 at 00:40
@J.Khelly - Exactly. Think about it -- you're using the index array to tell you where the sorted first element is, second element, etc. — PaulMcKenzie, Oct 03 '17 at 00:42
Although i have the rough idea, i'm still unclear on how it gets implemented into my code. i know if i see it, i'd understand — J.Khelly, Oct 03 '17 at 00:50
@J.Khelly -- So basically `if myVector[index[i]] > myVector[index[i+1]] then swap index[i] with index[i+1]`. What you wind up with after the sort is an index array that tells you the position of each of the elements in the sorted list without really sorting the list. See the answer that sehe below posted. It is a little different but is essentially doing what I mentioned -- not sorting the original data, and only sorting a list of numbers telling you how to traverse your arrays in a sorted manner. Imagine you had 50 arrays instead of 5. You wouldn't think of swapping 50 items, right? — PaulMcKenzie, Oct 03 '17 at 00:53

sehe · Accepted Answer · 2017-10-03T00:55:17.247

You can fake a non-clumsy data structure with

vector<vector<string> > database;

Where vector<string> is a single record. To make it "manageable" I'd use some aliases, accessor functions and this enum:

enum { AUTHOR, TITLE, VENUE, YEAR, PRESENTATION };

The code becomes a lot shorter:

Live On Coliru

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

const int max_applications_num = 1000;

enum { AUTHOR, TITLE, VENUE, YEAR, PRESENTATION };

vector<vector<string> > database;

void Tokenize(string line, vector<string> &tokens, string delimiters = "\t ") {
    string token = "";
    string OneCharString = " ";
    for (size_t i = 0; i < line.size(); i++)
        if (find(delimiters.begin(), delimiters.end(), line[i]) !=
            delimiters.end()) // line[i] is one of the delimiter characters
        {
            if (token != "")
                tokens.push_back(token);
            token = "";
        } else {
            OneCharString[0] = line[i];
            token += OneCharString;
        }

    if (token != "")
        tokens.push_back(token);
}

void SaveApplication(const vector<string> &tokens) {
    database.emplace_back(tokens.begin()+1, tokens.end());
}

void remove_application(size_t pos) {
    assert(pos < database.size());
    database.erase(database.begin()+pos);
}

int year_of(vector<string> const &record) { return stoi(record[YEAR]); }
int year_of(int i) { return year_of(database.at(i)); }

void sort() {
    for (size_t j = 0; j <= database.size() - 1; j++) {

        vector<string> tmp = database.at(j);

        int tmp_year = year_of(tmp);

        int i = j - 1;
        while (i > -1 and year_of(i) > tmp_year) {
            database.at(i + 1) = database.at(i);
            i = i - 1;
        }

        database.at(i + 1) = tmp;
    }
}

void print() {
    for (size_t i = 0; i < database.size(); i++) {
        cout 
            << database.at(i)[AUTHOR] << "\t"
            << database.at(i)[TITLE]  << "\t"
            << database.at(i)[VENUE]  << "\t"
            << database.at(i)[YEAR]   << "\t"
            << database.at(i)[PRESENTATION] 
            << endl;
    }
    cout << "\n" << endl;
}

void ExecuteCommands(const char *fname) {
    ifstream inf;
    inf.open(fname);

    string line;
    while (getline(inf, line).good()) {
        vector<string> tokens;
        Tokenize(line, tokens, "\t ");
        if (tokens.size() == 0)
            continue;

        if (tokens[0].compare("save_application") == 0)
            SaveApplication(tokens);

        else if (tokens[0].compare("remove_application") == 0)
            remove_application(atoi(tokens[1].c_str()));

        else if (tokens[0].compare("sort") == 0)
            sort();

        else if (tokens[0].compare("print") == 0)
            print();
    }

    inf.close();
}

int main(int argc, char **argv) {
    if (argc != 2) {
        cout << "usage: executable.o command.txt\n";
        return 1;
    }

    ExecuteCommands(argv[1]);
}

For the input

save_application "authors_list1"    "title1" "conference1"  2016    "poster"
save_application "authors_list3"    "title3" "conference2"  2010    "oral"
save_application "authors_list2"    "title2" "journal1" 2015    "none"
print
sort
print
remove_application 0
print

Prints

"authors_list1" "title1"    "conference1"   2016    "poster"
"authors_list3" "title3"    "conference2"   2010    "oral"
"authors_list2" "title2"    "journal1"  2015    "none"


"authors_list3" "title3"    "conference2"   2010    "oral"
"authors_list2" "title2"    "journal1"  2015    "none"
"authors_list1" "title1"    "conference1"   2016    "poster"


"authors_list2" "title2"    "journal1"  2015    "none"
"authors_list1" "title1"    "conference1"   2016    "poster"

Why `vector` of `vector` rather than `vector` of `tuple`? `tuple` is fixed size (by templated type) and heterogeneous; it's designed to represent a single "record" like this; doing it with `vector`+`enum`s (which can't store `int` for one field and `string` for another, and can't use stuff like `std::tie` for simple unpacking) seems masochistic, unless you're completely unable to use C++11 or higher for some reason. — ShadowRanger, Oct 03 '17 at 01:48
@ShadowRanger vector was already in use. So it has implicit green light. If you're gonna use a tuple, just use a struct here. I was merely showing how to defy silly constraints imposed by profs without stepping over the line. — sehe, Oct 03 '17 at 02:10
structy sample (also revamped tokenization to honour quotes): [live on Coliru](http://coliru.stacked-crooked.com/a/b845ae80792a387c) /cc @ShadowRanger — sehe, Oct 03 '17 at 02:26
You compiled it wrong. The beauty of online compilers is that you can see exactly how to compile/use it (in this case, [c++11 was enough](http://coliru.stacked-crooked.com/a/faea2be5338d300e) and two tiny tweaks make it [c++03 compatible](http://coliru.stacked-crooked.com/a/91e305a18d28ea1e)) — sehe, Oct 03 '17 at 06:58
for our class, we usually compile like this: "g++ -o file.o file.cpp". and to run it, we do this: "./file.o input.txt". is that how you would compile it too? — J.Khelly, Oct 03 '17 at 08:35
if i were to compile your code like i usually do, would it work? or do i need to specify certain things first? — J.Khelly, Oct 03 '17 at 08:37
Have you tried? Because if you have, and you have trouble figuring out what the difference is, just post a question. Don't be a [help vampire](https://meta.stackoverflow.com/questions/258206/what-is-a-help-vampire). Here's a hint: http://coliru.stacked-crooked.com/a/3f85712d9f5bbcce (There's an edit button) — sehe, Oct 03 '17 at 08:47
Of course I tried. How else would I know that it gave errors when I compiled? — J.Khelly, Oct 03 '17 at 09:18
I dunno. [You](https://stackoverflow.com/questions/46535399/sort-one-vector-based-on-the-elements-of-another-vector-with-no-class-or-struct/46535687?noredirect=1#comment80034804_46535687) didn't [tell](https://stackoverflow.com/questions/46535399/sort-one-vector-based-on-the-elements-of-another-vector-with-no-class-or-struct/46535687?noredirect=1#comment80034905_46535687). In that case I suggest asking a question. Be sure to include relevant details (like, you know, the fact that you get an error, and maybe what the error reads) — sehe, Oct 03 '17 at 09:20
I already asked and the most frequent answer was that my compiler was simply outdated. — J.Khelly, Oct 03 '17 at 09:23
Sorry, I didn't see that particular question. I'll look for it now. [Answered](https://stackoverflow.com/a/46541276/85371). — sehe, Oct 03 '17 at 09:26

score 0 · Answer 2 · answered Oct 03 '17 at 01:01

0

Why dont you use parallel vectors, and when you order the years vector, if you swap position i with position j, do it on every vector.

answered Oct 03 '17 at 01:01

Carlos A. Jimenez Holmquist

554
4
15

That is not a good solution. If you had 100 vectors, you need to write 100 swaps just for one element. – PaulMcKenzie Oct 03 '17 at 01:02
1

@PaulMcKenzie - This could be handled using an array or vector of pointers to the vectors. At some point, the code is going to have to deal with all the vectors. I'm wondering if using an array of indices to help with the sort is going to seem like too much help was received for this assignment. – rcgldr Oct 03 '17 at 01:28
@rcgldr *I'm wondering if using an array of indices to help with the sort is going to seem like too much help* -- I was wondering the same thing. Didn't want to write out the answer here -- however the "answer" more or less is already in the public domain here, just like many other homework answers. I hope the OP doesn't just copy it verbatim. – PaulMcKenzie Oct 03 '17 at 01:32
sehe's answer is essentially what I was suggesting, using a vector of vectors versus my suggestion of a vector of pointers to a vector. Still even that seems beyond what is probably being expected for this lab. – rcgldr Oct 03 '17 at 01:36
No, actually we were told that we could use a vector of vectors. It didn't really matter how we coded the program, as long as we didn't have any classes or structs. – J.Khelly Oct 03 '17 at 03:32
@J.Khelly write it in python :) – sehe Oct 03 '17 at 06:54

Sort One Vector Based on the Elements of Another Vector With no Class or Struct

2 Answers2

Linked