使用C++中的sort()函数对二维字符数组进行排序

Question

我有一个二维字符数组（不想使用std::string数组）。如何使用std::sort()按字符串长度升序排序字符串（char*）？

我已经尝试了以下方法。但是它不起作用。

char names[100][30];

bool comp(const char* a, const char* b){
    return strlen(a)<strlen(b);
}

int main(){
    ...
    //I want to sort the first n strings 
    sort(names,names+n,comp); //n<=100
    ...
}

我找到了以下错误：

1>e:\program files (x86) in e\microsoft visual studio 9.0\vc\include\algorithm(3128) : error C2075: '_Val' : array initialization needs curly braces
1>        e:\program files (x86) in e\microsoft visual studio 9.0\vc\include\algorithm(3150) : see reference to function template instantiation 'void std::_Insertion_sort1<_BidIt,bool(__cdecl *)(const char *,const char *),char[30]>(_BidIt,_BidIt,_Pr,_Ty (*))' being compiled
1>        with
1>        [
1>            _BidIt=char (*)[30],
1>            _Pr=bool (__cdecl *)(const char *,const char *),
1>            _Ty=char [30]
1>        ]
1>        e:\program files (x86) in e\microsoft visual studio 9.0\vc\include\algorithm(3270) : see reference to function template instantiation 'void std::_Insertion_sort<_RanIt,bool(__cdecl *)(const char *,const char *)>(_BidIt,_BidIt,_Pr)' being compiled
1>        with
1>        [
1>            _RanIt=char (*)[30],
1>            _BidIt=char (*)[30],
1>            _Pr=bool (__cdecl *)(const char *,const char *)
1>        ]
1>        e:\program files (x86) in e\microsoft visual studio 9.0\vc\include\algorithm(3279) : see reference to function template instantiation 'void std::_Sort<char(*)[30],int,bool(__cdecl *)(const char *,const char *)>(_RanIt,_RanIt,_Diff,_Pr)' being compiled
1>        with
1>        [
1>            _RanIt=char (*)[30],
1>            _Diff=int,
1>            _Pr=bool (__cdecl *)(const char *,const char *)
1>        ]
1>        e:\projects visual studio2008\sample\sample\sorting.cpp(51) : see reference to function template instantiation 'void std::sort<char(*)[30],bool(__cdecl *)(const char *,const char *)>(_RanIt,_RanIt,_Pr)' being compiled
1>        with
1>        [
1>            _RanIt=char (*)[30],
1>            _Pr=bool (__cdecl *)(const char *,const char *)
1>        ]
1>e:\program files (x86) in e\microsoft visual studio 9.0\vc\include\algorithm(3133) : error C2106: '=' : left operand must be l-value
1>e:\program files (x86) in e\microsoft visual studio 9.0\vc\include\algorithm(3140) : error C2106: '=' : left operand must be l-value
1>e:\program files (x86) in e\microsoft visual studio 9.0\vc\include\algorithm(3141) : error C2106: '=' : left operand must be l-value
1>Build log was saved at "file://e:\projects visual studio2008\sample\sample\Debug\BuildLog.htm"
1>sample - 4 error(s), 3 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

- FRR

---

“不起作用”并不是一个错误描述。话虽如此，如果使用std::vector或std::array和std::string，那么它就能正常工作了。 - Ulrich Eckhardt

使用char*，而不是std::vector、std::array或std::string，无法进行排序吗？ - FRR

FRR: 你甚至没有提到错误信息，更别说提供一个最小的示例了。@juanchopanza: 如果我理解得正确的话，那只是一个一维数组的固定长度字符串，鉴于这里提供的有限信息。 - Ulrich Eckhardt

“sort” 将尝试使用 comp 的结果交换 “a” 和 “b”。这在使用 “char[30]” 时不会很好地工作。 - Bo Persson

names 的元素不是指针 (char*)，而是数组 (char[30])。使用 char* names[100] 可以解决问题。 - molbdnilo

Answer 1

如果您的数据在

char names[100][30];

由于该数据结构根本没有指针，只有100*30=3000个字符一个接着一个，因此您无法对“指针”进行排序。因此，要进行排序，您需要实际移动包含所有内容的100行。

std::sort 不能直接使用，因为数据结构是数组的数组，而在C++中，数组是二等公民（例如，您不能将一个数组分配给另一个数组）。

- 6502

Answer 2

std::sort要求其迭代器类型参数必须为：

• ValueSwappable 和 RandomAccessIterator。

迭代器类型的解引用类型必须满足以下要求：

• MoveAssignable 和 MoveConstructible。

不幸的是，数组不能交换（即你不能将一个数组赋值给另一个数组）。因此，你不能使用 std::sort 来对数组进行排序。

你可以使用以下方式来使用 std::array<std::array<char, N>, M>：

template<std::size_t N, std::size_t M>
void custom_sort(std::array<std::array<char, M>, N> &arrs) {
  std::sort(std::begin(arrs), std::end(arrs), [](auto const &a, auto const &b){ return strnlen(a.data(), M) < strnlen(b.data(), M); });
}

实时演示

由于@Jarod42的帮助，代码得到了改进。

- 101010

---

为了避免可能的越界访问，请将 strnlen(a.data(), M) < strnlen(b.data(), M) 进行翻译。 - Jarod42

避免不必要的复制，需要缺失的引用。 - Jarod42

@Jarod42 谢谢，我甚至不知道 strnlen :) - 101010

Answer 3

如已提到的，数组不能被分配。结构体可以被分配，因此这可能接近您想要的。结构体数组可能会为了对齐而填充。在Visual Studio 2015的情况下，结构体数组未被填充，因此内存布局与二维数组相同。

更新 - 更改为使用引用进行比较参数，并按照Jarod42的建议切换到strnlen。

#include <algorithm>
#include <cstring>

using namespace std;

typedef struct
{
    char name[30];
}name;

name names[4] = { { "12345678" },{ "123" },{ "12345" },{ "12" } };

bool comp(const name &a, const name &b)
{
    return strnlen(a.name,30) < strnlen(b.name,30);
}

int main(){
    sort(names, names+4, comp);
    return 0;
}

- rcgldr

Answer 4

你可以尝试这个：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define M 10000

int main()
{
    char names[M][15];
    int n, i;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%s", names[i]);
    qsort(names, n, 15, (int (*)(const void *, const void *))strcmp);

    for(i = 0; i < n; i++)
        printf("%s\n", names[i]);
}

- Sakib Ahammed