按子字符串对字符串向量进行排序？

Question

我有一个向量，其中包含一些具有相同形式的字符串：

'12345 QWERTY'
'23456 ASDFGH'
'34567 ZXCVBN'

我需要按照代码（int类型）和名称（string类型）对它们进行排序。我考虑使用 .substr() 函数忽略数字。是否有一种方法可以在 sort 函数内使用它？

一种尝试的方法是创建一个映射函数来补充 'sort()'：

bool mapFunc(string a, string b) 
{
return a.substr(6) < b.substr(6));
}

插入排序功能：

sort(begin, end, mapFunc);

这里的“begin”和“end”都是指向我的向量开头和结尾的迭代器。

如果我犯了任何错误，请纠正我：）

- b._.rett

---

您可以将自定义的函数对象传递给std::sort函数以用于排序，您尝试过这样做吗？ - Algirdas Preidžius

使用带有std::sort的lambda表达式。 - drescherjm

你有没有阅读过 http://en.cppreference.com/w/cpp/algorithm/sort 的示例？ - UKMonkey

最自然的方式是将这些字符串解析为一个 struct { int id; string qwerty;} 的向量，然后你可以轻松地按照需要对它们进行排序。 - 463035818_is_not_a_number

如果整数部分始终具有相同的（已知）长度，则可以使用C++17的std::string_view（如果可用）作为比较函数对象。如果不是这样，每当您想要比较它们时重新解析字符串听起来有点烦人，因此像user463035818建议的那样预先解析它们似乎是最好的选择（即使您必须在之后重建字符串，尽管将记录/元组/...存储为字符串形式真的很难受和不方便:( ）。 - Caninonos

Answer 1

通过向std::sort()传递自定义谓词，您正在正确的轨道上。您只需要更加充实它：

void split(const string &s, int &code, string &name) {
    size_t idx = s.find(' ');
    code = stoi(s.substr(0, idx));
    name = s.substr(idx+1);
}

bool mapFunc(const string &a, const string &b) {
    int code1, code2; 
    string name1, name2; 
    split(a, code1, name1);
    split(b, code2, name2);
    if (code1 == code2)
        return name1 < name2; 
    return code1 < code2;
}

这将首先按其数字代码对向量项进行排序，并仅对具有相同代码值的项按名称排序。

- Remy Lebeau

Answer 2

您可以使用一个函数对象（functor）：

struct Compare_By_Number
{
  bool operator()(const std::string& a, const std::string& b) const
  {
    std::istringstream a_input_stream(a);
    std::istringstream b_input_stream(b);
    int a_value, b_value;
    a_input_stream >> a_value;
    b_input_stream >> b_value;
    return a_value < b_value;
  }
};

您可以像 std::sort 的示例 一样，传递该函数的一个实例。

编辑 1：独立函数
另一种选择是将代码放入一个独立的函数中，并传递该函数：

bool Order_By_Number(const std::string& a, const std::string& b)
{
    std::istringstream a_input_stream(a);
    std::istringstream b_input_stream(b);
    int a_value, b_value;
    a_input_stream >> a_value;
    b_input_stream >> b_value;
    return a_value < b_value;
}

std::vector<std::string> database;
//...
std::sort(database.begin(), database.end(), Order_By_Number);

基本的概念是如果第一个参数在您的排序中位于第二个参数之前，则返回true。

- Thomas Matthews

---

你的函数对象没有跟踪任何状态信息，因此当独立函数足以胜任时，使用函数对象就有些过度了。 - Remy Lebeau

@RemyLebeau: 我修改了独立函数的答案。 - Thomas Matthews

Answer 3

我认为使用std::lexicographical_compare比提取子字符串更有效。

std::lexicographical_compare的作用是就地比较子字符串，因此您不需要支付将它们复制出去的成本。

像这样：

std::vector<std::string> v
{
    "12345 QWERTY",
    "23456 ASDFGH",
    "34567 ZXCVBN",
};

std::sort(std::begin(v), std::end(v), [](std::string const& a, std::string const& b){
    return std::lexicographical_compare(std::begin(a), std::begin(a) + 5, std::begin(b), std::begin(b) + 5);
});

std::cout << "By first column" << '\n';
for(auto const& s: v)
    std::cout << s << '\n';

std::sort(std::begin(v), std::end(v), [](std::string const& a, std::string const& b){
    return std::lexicographical_compare(std::begin(a) + 6, std::end(a), std::begin(b) + 6, std::end(b));
});

如果您需要频繁地进行这种操作，那么您可以将其包装在一个特殊的比较器中，如下所示：

struct substring_compare
{
    std::size_t from;
    std::size_t len;

    substring_compare(std::size_t from, std::size_t len)
    : from(from), len(len) {}

    bool operator()(std::string const& a, std::string const& b) const
    {
        // sanity checks
        assert(from + len <= a.size());
        assert(from + len <= b.size());

        auto beg_a = std::begin(a) + from;
        auto end_a = beg_a + len;

        auto beg_b = std::begin(b) + from;
        auto end_b = beg_a + len;

        return std::lexicographical_compare(beg_a, end_a, beg_b, end_b);
    }
};

int main()
{
    std::vector<std::string> v
    {
        "12345 QWERTY",
        "23456 ASDFGH",
        "34567 ZXCVBN",
    };

    // start at position 0, comparing 5 characters
    std::sort(std::begin(v), std::end(v), substring_compare(0, 5));

    std::cout << "By first column" << '\n';
    for(auto const& s: v)
        std::cout << s << '\n';

    // start at position 6, comparing 6 characters
    std::sort(std::begin(v), std::end(v), substring_compare(6, 6));

    std::cout << "By second column" << '\n';
    for(auto const& s: v)
        std::cout << s << '\n';
}

输出：

By first column
12345 QWERTY
23456 ASDFGH
34567 ZXCVBN

By second column
23456 ASDFGH
12345 QWERTY
34567 ZXCVBN

- Galik

Answer 4

您可以使用现有的功能，即std::pair提供的比较运算符。因此，实现转换函数：

std::pair<int,std::string> convert( const std::string &str )
{
     int id = 0;
     std::string name;
     std::istringstream is( str );
     is >> id >> name;
     return std::make_pair( id, name );
}

然后您的比较函数很简单：

bool compare( const std::string &s1, const std::string &s2 )
{
     return convert( s1 ) < convert( s2 );
}

- Slava

---

只是一个小问题 - operator>> 在遇到空格时停止读取，所以如果字符串中有空格，例如：'12345 ABC DEF'，那么 >> name 将不起作用。 您可以使用 std::getline() 来代替：is >> id >> std::ws; std::getline(is, name); - Remy Lebeau

@RemyLebeau 我认为提供正确的数据示例或在问题中描述数据是OP的工作，我根据现有信息提供了信息。无论如何，这应该足够让OP相应地实现。PS OP说“相同形式的字符串数量”，所以我认为可以假设没有空格。 - Slava

Answer 5

你最好有一个 std::vector<std::pair<int, string>> 来避免这样的复杂情况。 否则，你应该创建一个比较函数并传递子字符串。

- Eduard Rostomyan

---

是的，我很想做这个，但我必须这样做，因为它是我的作业要求的一部分。-(表达遗憾) - b._.rett

@Z.Yang，你的作业有什么禁止你使用pair或vector的规定吗？这将是奇怪的规则（特别是因为你似乎被允许使用std::sort）。 - 463035818_is_not_a_number

我猜这个任务是为了练习使用函数对象或者Lambda表达式（不确定是哪一个）。 - Martin Bonner supports Monica

我认为它主要用于字符串操作，如果没有完整的上下文很难确定。我不知道什么是lambda函数。 - b._.rett

Answer 6

为了设定问题，我们有一个字符串向量：

vector<string>myVec;

vector<string>::iterator vecBegin=myVec.begin(), vecBegin=myVec.end();

一个尝试是创建一个映射函数来补充'sort()':

bool mapFunc(string a, string b) 
{
return a.substr(6) < b.substr(6));
}

插入到排序函数中：

sort(vecBegin, vecEnd, mapFunc);

'vecBegin'和'vecEnd'都是指向我的向量开头和结尾的迭代器。

这将按子字符串对字符串向量进行排序。可以使用迭代器访问该向量：

vector<string>::iterator currentVec;
for (currentVec=vecBegin; currentVec<vecEnd; ++currentVec) 
{
// Do things
}

- b._.rett

---

我在发布问题后立即找到了问题的解决方法（尽管我已经花费了很多小时来解决它）。这确实是答案，因为我编译并运行它时它起作用了。 - b._.rett