sorting vector of vector of strings in C++

Question

I am having trouble to figure out, how to sort a vector of vector of strings, here is the testing code.

#include <iostream>
#include <vector>
#include <boost/algorithm/string.hpp>

int main(int argc, char** argv) {
  std::vector <std::vector <std::string> > data_var;
  std::vector <std::string> temp;

  std::string str1 = "1,hello3,temp2";
  std::string str2 = "2,hello2,temp1";
  std::string str3 = "3,hello1,temp3";

  boost::split(temp, str1, boost::is_any_of(","));
  data_var.push_back(temp);
  boost::split(temp, str2, boost::is_any_of(","));
  data_var.push_back(temp);
  boost::split(temp, str3, boost::is_any_of(","));
  data_var.push_back(temp);

  // sorting code here...
}

Thanks in advance...

Solution 1

If you only want to sort based on the second column, then you just need to provide a custom comparison operator. Once way to do that is:

struct StringListCompare
{
  bool operator()(const vector<string>& lhs, const vector<string>& rhs)
  {
    // what do we do if lhs or rhs don't have two elements?
    if (lhs.size() < 2 || rhs.size() < 2)
    {
      // ?
    }
    else
    {
      return lhs[1] < rhs[1];
    }
  }
} StringListComparer;

int main()
{
  // ...
  sort(data_var.begin(), data_var.end(), StringListComparer);
}

Edit: If you won't know until runtime which column you'll be sorting on, you can encode that in the sorting object:

class StringListCompare
{
public:
  explicit StringListCompare(int column) : m_column(column) {}
  bool operator()(const vector<string>& lhs, const vector<string>& rhs)
  {
    // what do we do if lhs or rhs don't have (m_column + 1) elements?
    return lhs[m_column] < rhs[m_column];
  }
private:
  int m_column;
};

Notice how we've added a constructor that takes which column it'll act on. You can use it like this:

  // We set it up so the columns are 0-based:
  StringListCompare compare_column_0(0), compare_column_1(1), compare_column_2(2);

  cout << "Original:\n" << data_var << endl;
  sort(data_var.begin(), data_var.end(), compare_column_2);
  cout << "Sorted on column 2:\n" << data_var << endl;
  sort(data_var.begin(), data_var.end(), compare_column_1);
  cout << "Sorted on column 1:\n" << data_var << endl;
  sort(data_var.begin(), data_var.end(), compare_column_0);
  cout << "Sorted on column 0:\n" << data_var << endl;

You don't even need to make the local variable if you don't want to:

  sort(data_var.begin(), data_var.end(), StringListCompare(2));
  cout << "Sorted on 2, no local sort variable:\n" << data_var << endl;

[Code at ideone]

Solution 2

Alright: new -simpler- answer, having learned that vectors are comparable:

//sorting code here...
std::sort(data_var.begin(), data_var.end(), std::greater<std::vector<std::string>>());

Solution 3

I'm going to assume each vector represents an record of some type, and compare the internal strings from left to right. Obviously the sorter() code is easily replaceable. You should to add a sorter() function somewhere to your code, and pass it to the std::sort algorithm.

bool sorter(const std::vector<std::string>& left, const std::vector<std::string>& right)
{
    //go through each column
    for(int i=0; i<left.size() && i<right.size()) {
        // if left is "more" return that we go higher
        if( left[i] > right[i])
            return true;
        // if left is "less" return that we go lower
        else if (left[i] < right[i])
            return false;
    }
    // if left is longer, it goes higher
    if (left.size() > right.size())
        return true;
    else //otherwise, left go lower
        return false;
 }

 int main() {
     std::vector <std::vector <std::string> > data_var;
     //...

     //sorting code here...
     std::sort(data_var.begin(), data_var.end(), sorter);

     //...
 }

Comments

[Benjamin Lindley]

Your 'sorter' comparator is equivalent to the default one.

[Mooing Duck]

@Benjamin Lindley: I'm pretty sure the default comparer is std::less, which defaults to T::operator<(const T&), which is not overloaded for std::vector. Also, we're going for decreasing order (std::more, if it worked on vectors)

[Benjamin Lindley]

You're right, I wasn't reading the signs right. But in fact, operator< is overloaded for vector, as is operator>, so you could use std::greater, or std::less(which would be the default)

[rda3mon]

@Mooing Duck: thanks, but I don't understand 1 thing, you are sending the parameters to std::sort as const right? then how does it modify data_var?

[Mooing Duck]

@Benjamin: well look at that! I never knew it was! msdn.microsoft.com/en-us/library/572x098y(v=VS.71).aspx

[Mooing Duck]

std::sort does the modifications. It uses a helper named "sorter" to tell it the order, but "sorter" doesn't actually need to change anything.

[rda3mon]

i c... Can you point me some link which explains std::sort function? and not cplusplus.com/reference/algorithm/sort

[Mooing Duck]

Since the "fix" is so dramatic, I posted it as a second answer. @Ringo, check out the one-line answer, since Benjamin showed me an easier way.

[rda3mon]

how do I specify sort on which column?

[Mooing Duck]

This will sort by the first column, then second, then third, etc. If you want a specific column, use Bill's answer, or if you want a specific order, customize my first answer or Bill's answer.

[Blastfurnace]

I was going to say the code in sorter could be replaced with std::lexicographical_compare but I checked the MSVC++ headers and the operator< overload already calls std::lexicographical_compare. I did not know that before.

[ildjarn]

You're missing parenthesis after std::greater<std::vector<std::string>> to actually construct the functor.

[rda3mon]

is there anyway I can pass the column as a parameter to the StringListComparer?

[Bill]

@Ringo: It makes the class more complicated, but yes. I'll add a sample.

[Bill]

@Ringo: I've added code so the comparison object knows which column it'll be comparing against. Does that make sense?