CODEWITHSUNDEEP
c++stringsortingvector
Pol Pera
Pol Pera

Reputation: 11

Sorting a string vector in C++ with a special value to place at the end

I'm trying to make a function that sorts a vector of strings with this criteria:

All strings= "NULL" must go to the end of the vector and decreasing from there. The rest of the strings must keep their order.

For example given:

{"Potato", "NULL", "NULL", "Charmander" , "Spaghetti", "NULL"}

the output should be:

{"Potato","Charmander","Spaghetti","NULL","NULL","NULL"}

I tried with this but it did not quite work:

bool comp(string i, string j){
    if(i=="NULL"){return i>j;}
     if (j=="NULL") {return i<j;}

Thanks in advance

Upvotes: 0

Views: 448

Answers (3)

Temple
Temple

Reputation: 1631

You can write your own version of function that puts some strings to the end i.e:

namespace myAlgo {
        template<typename ForwardIter, class T >
        ForwardIter moveToEnd(ForwardIter first, ForwardIter last, const T& value) {
            if (first == last) {
                return first;
            }
            ForwardIter fasterFirst = first;
            //Shift strings that do not match value to the left in stable manner
            while (++fasterFirst != last) {
                if (*fasterFirst != value) {
                    *++first = *fasterFirst;
                }
            }
            ForwardIter pivot = first;
            //Fill rest with value
            while (first != last) {
                *++first = value;
            }
    return pivot;
    }
}

Then just:

myAlgo::moveToEnd(vec.begin(), vec.end(), "NULL");

Upvotes: 0

Marko Tunjic
Marko Tunjic

Reputation: 1889

You can use partition algorithm: 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[]) {

    vector<string> vec {
        "Potato", "NULL", "NULL", "Charmander" , "Spaghetti", "NULL"
    };

    partition(begin(vec), end(vec), // Partition the values
               [](const string& s) { return s != "NULL"; });


    copy(begin(vec), end(vec), ostream_iterator<string>{cout, " "});
    cout << endl;

    return 0;
}
// RESULT: Potato Spaghetti Charmander NULL NULL NULL

NOTE: If you need to maintain relative ordering use stable_partition instead.

Upvotes: 1

einpoklum
einpoklum

Reputation: 132350

You could do one of two things:

  1. First take care of the "NULL"s, then sort the other strings the naive way we regularly would
  2. Sort all string using the more complex ordering you defined

Handling "NULL"s first

The standard library has a "partition" algorithm, which will move all elements matching a certain criterion to the end of the string.

std::vector<string> vec {
    "Potato", "NULL", "NULL", "Charmander" , "Spaghetti", "NULL"
};
auto is_not_null = [](const std::string& s) { return s != "NULL"; } 
auto nulls_start = std::partition(vec.begin(), vec.end(), is_not_null);
auto non_nulls_end = nulls_start;
std::sort(vec.begin(), non_nulls_end);

Sort with a complex comparison

std::vector<string> vec {
    "Potato", "NULL", "NULL", "Charmander" , "Spaghetti", "NULL"
};
auto comparator = 
    [](const std::string& lhs, const std::string& rhs)
    {
        return rhs == "NULL" or lhs <= rhs; 
    };
std::sort(vec.begin(), vec.end(), comparator);

Note the difference between the comparison here and your comp() function. The comparator answers question "should the first string I got come before the second string?" - and your comp() function just doesn't give an answer that corresponds to your requirement.

Upvotes: 1

Related Questions