How to sort vector of objects by a private string variable alphabetically

Question

I cannot figure out how to sort a vector of objects by one of the member variables called VIN, which is of data type string. I am to either perform a bubble sort or a selection sort. I am most familiar with a bubble sort, so that's the direction I attempted to take. However, I am aware that I need to compare both of the strings by either making them all uppercase or lower case. Keep in mind, the strings also will have number characters in them as well.

So my question is: 1) How to I convert a string either all lowercase or all ASCII numbers and 2) What data type should the temp variable be (data type of the class or some other data type).

Here is the (incomplete) code I have so far:

    void sortInventory(vector<Vehicle> &carList)
    {
        bool swap; 
        string temp; 
        do
        {
            swap = false;

            for (int count = 0; count < carList.size(); count++)
            {
                if (carList[count].getVIN() > carList[count + 1].getVIN())
                {
                    temp = carList[count].getVIN();                                 
                    carList[count].getVIN() = carList[count + 1].getVIN();          
                    carList[count + 1].getVIN() = temp;                      
                    swap = true;                                               
                }
            }

        } while (swap);
}

Here is my class declaration:

class Vehicle
{
private:
    string VIN;

public:
    string getVIN();
    void   setVIN(string);

};

Here is my class implementation:

string Vehicle::getVIN()
{   return VIN;     }

void Vehicle::setVIN(string input)
{   VIN = input;    }

Thanks!

score 2 · Accepted Answer · edited May 23 '17 at 12:09

You can do std::sort(carList.begin(),carList.end(),vehicleCompare) where vehicleCompare is a comparison function that you define. See sort documentation. Then, to uppercase you can use std::toupper, as shown in this guide.

std::string myToUpper(std::string in) {
    std::transform(in.begin(), in.end(),in.begin(), ::toupper);
    return in;
}

So the comparison operator^(*) will be:

bool vehicleCompare (const Vehicle a, const Vehicle b) {
    const std::string a_name = myToUpper(a.getVIN());
    const std::string b_name = myToupper(b.getVIN());
    return (a_name < b_name);
    }

Useful reading about string comparison operator.

By the way, your string getVIN() method should be const, that is you should change its declaration to string getVIN() const.

If you want to keep your sorting function, the point is that in any case you'll have to define a proper comparison operator, as the one shown here.

To specifically answer to your second question, temp could be auto in C++11, or simply std::string. Then the way you are trying to assign your VIN value is wrong. Given the interface you have given, it should be:

auto temp = carList[count].getVIN();                                 
carList[count].setVIN(carList[count + 1].getVIN() );          
carList[count + 1].setVIN(temp);

Although it still might get nasty when you start to have more than one member variable to copy: you should instead build a copy constructor and change your code to:

auto temp = carList[count]; //you can use Vehicle instead of auto as type
carList[count] = carList[count + 1];          
carList[count + 1] = temp;

The copy constructor will be:

Vehicle(const Vehicle& in) 
  : VIN(in.getVIN() ) 
  {}

And, at that point, you'll also want a constructor from string, and an empty constructor.

Vehicle(std::string& inVIN) 
  : VIN(inVIN) 
  {}

Vehicle(const Vehicle& in) 
  {} //All input members get initialized through the default constructor.

_{(*) Note that this comparison method wouldn't be the most efficient, as it makes uppercase the whole string while the first few characters are normally sufficient to decide their order. So a more efficient way would be to uppercase one character at the time and compare it before deciding if to uppercase another character.}

That's an awfully expensive comparison function for something that could often be determined after comparing the first character. — Benjamin Lindley, Apr 27 '15 at 23:10
@BenjaminLindley True, but I think OP's level is far from being ready for optimizations. I believe it's more important to first show him how to divide and conquer his problem. In any case, I have added a note to the answer. — Antonio, Apr 27 '15 at 23:16

score 1 · Answer 2 · answered Apr 27 '15 at 22:41

1

Answer to question 1: You can make a simple function that converts a std::string to upper.

void string_to_upper(string &s) {
  for(int l = 0; l < s.length(); ++l) {
     s[l] = toupper(s[l]);
  }
}

answered Apr 27 '15 at 22:41

anakin

551
4
12

score 1 · Answer 3 · edited May 23 '17 at 11:53

First, your Vehicle::getVIN() method should be marked as const, to implement proper const-correctness:

string Vehicle::getVIN() const
{
    return VIN;   
}

Then, note that you don't need to reinvent the wheel and reimplement a sorting algorithm from scratch in production code in C++ (unless this is a learning exercise/homework about writing sorting code).

You can simply use the standard std::sort() algorithm implemented in the STL, and customize the comparison criteria using a convenient C++11 lambda, e.g.:

// std::vector<Vehicle> carList;

std::sort(carList.begin(), carList.end(), 
    [](const Vehicle& v1, const Vehicle& s2)
    {
        /* Code implementing custom Vehicle comparison */
    }
);

Your code in the lambda could be something like this:

    [](const Vehicle& v1, const Vehicle& s2)
    {
        // Use stricmp() to compare strings in a case insensitive way
        return (stricmp(v1.getVIN().c_str(), v2.getVIN().c_str()) < 0);
    }

Instead of calling stricmp(), you can use boost::to_upper(), or some other method among the ones showed e.g. in this thread on StackOverflow:

Case insensitive string comparison in C++

How to sort vector of objects by a private string variable alphabetically

3 Answers3

Linked