C++中对string vector排序：将"NULL"置于末尾并保留其余元素顺序

Your goal is to preserve the original order of non-"NULL" strings while moving all "NULL" entries to the end of the vector. The problem with your initial comparator is twofold:

1. It doesn’t handle the case where both strings are non-"NULL" (leading to undefined behavior).
2. Using std::sort (which isn’t stable) would reorder your non-"NULL" elements, breaking their original sequence.

Here are two reliable approaches to solve this:

Approach 1: Use std::stable_sort with a Custom Comparator #

std::stable_sort maintains the relative order of elements that are considered "equivalent" by your comparator. We can define a comparator that prioritizes non-"NULL" strings over "NULL" ones, and leaves non-"NULL" elements in their original order:

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

bool compareStrings(const std::string& a, const std::string& b) {
    // Non-NULL comes before NULL
    if (a != "NULL" && b == "NULL") {
        return true;
    }
    // For all other cases (both non-NULL, or a is NULL), keep original order
    return false;
}

int main() {
    std::vector<std::string> vec = {"Potato", "NULL", "NULL", "Charmander", "Spaghetti", "NULL"};
    std::stable_sort(vec.begin(), vec.end(), compareStrings);
    
    // Result: {"Potato", "Charmander", "Spaghetti", "NULL", "NULL", "NULL"}
    return 0;
}

Approach 2: Use std::stable_partition (Simpler) #

std::stable_partition is even more straightforward here. It groups elements that satisfy a predicate (non-"NULL") at the start of the vector, while preserving their original order, and moves the rest ("NULL") to the end:

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

int main() {
    std::vector<std::string> vec = {"Potato", "NULL", "NULL", "Charmander", "Spaghetti", "NULL"};
    
    // Partition elements: non-NULL first, in original order
    std::stable_partition(vec.begin(), vec.end(), 
        [](const std::string& s) { return s != "NULL"; });
    
    // Result: {"Potato", "Charmander", "Spaghetti", "NULL", "NULL", "NULL"}
    return 0;
}

Why These Work #

• Both std::stable_sort and std::stable_partition guarantee that the relative order of non-"NULL" elements is preserved.
• The comparator for stable_sort ensures that only non-"NULL" strings are placed before "NULL" ones, leaving other pairs in their original order.
• stable_partition directly separates the vector into two groups (non-"NULL" and "NULL") without reordering elements within each group.

内容的提问来源于stack exchange，提问作者Pol Pera