pri*_*ime 9 c++ arrays sorting
我有一个像下面这样的2D数组.(array[5][2])
20 11
10 20
39 14
29 15
22 23
排序后应该如下所示.
10 20
20 11
22 23
29 15
39 14
这意味着应该对数组进行排序,仅比较第一列值.
在Java中,有一个内置的功能来实现这一点.如下.
Arrays.sort(a, new Comparator<Long[]>() {
@Override
public int compare(Long[] o1, Long[] o2) {
Long t1 = o1[1];
Long p1 = o1[0];
Long t2 = o2[1];
Long p2 = o2[0];
if (t1 == t2) {
return (p1 > p2 ? 1 : (p1 == p2 ? 0 : -1));
} else {
return (t1 < t2 ? -1 : 1);
}
}
});
那么有没有C++内置的功能来做这些东西或者我怎么能用C++(最快的实现)呢？
提前致谢 :)
Who*_*aig 10
我提供这件事只因为它是为数不多的事情之一std::qsort确实也说std::sort根本没有,就是那种多列固定阵列:比较是三元语句的字符串,而应该是足够清晰的,如果你盯着它长足够:
#include <iostream>
#include <random>
#include <algorithm>
int main()
{
int ar[10][2];
// populate with random data
std::random_device rd;
std::default_random_engine rng(rd());
std::uniform_int_distribution<> dist(1,20);
std::for_each(std::begin(ar), std::end(ar),
[&](int (&ar)[2]){ ar[0] = dist(rng); ar[1] = dist(rng); });
std::cout << "Before Sort..." << '\n';
std::for_each(std::begin(ar), std::end(ar),
[](const int(&ar)[2]) { std::cout << ar[0] << ',' << ar[1] << '\n';});
std::qsort(ar, 10, sizeof(*ar),
[](const void *arg1, const void *arg2)->int
{
int const *lhs = static_cast<int const*>(arg1);
int const *rhs = static_cast<int const*>(arg2);
return (lhs[0] < rhs[0]) ? -1
: ((rhs[0] < lhs[0]) ? 1
: (lhs[1] < rhs[1] ? -1
: ((rhs[1] < lhs[1] ? 1 : 0))));
});
std::cout << "After Sort..." << '\n';
std::for_each(std::begin(ar), std::end(ar),
[](const int(&ar)[2]) { std::cout << ar[0] << ',' << ar[1] << '\n';});
return 0;
}
样品运行(显然会有所不同)
Before Sort...
2,11
18,4
20,20
14,6
8,10
17,8
14,14
3,10
20,14
19,19
After Sort...
2,11
3,10
8,10
14,6
14,14
17,8
18,4
19,19
20,14
20,20
注意:这特别使用严格值比较而不是比较器中的减法快捷方式,以避免潜在的下溢问题.如果在受限制的数据空间中这不是问题,那么您可以轻松地使该比较器更加简单.
C和C++的内置数组非常不灵活,除其他外,它们无法分配.
您最好的选择是来自C++标准库的'array'类,至少对于内部维度:
array<int, 2> a[5] = { { 20, 11 },
{ 10, 20 },
{ 39, 14 },
{ 29, 15 },
{ 22, 23 } };
sort( a, a + 5 );
这里我们使用std :: array的属性,默认情况下,'<'按字典顺序比较它们,即从第一个元素开始.为了对事物进行不同的排序,我们必须提出一个比较器对象,因此如果要将第二列用作排序键,则必须执行以下操作:
auto comp = []( const array<int, 2>& u, const array<int, 2>& v )
{ return u[1] < v[1]; };
sort( a, a + 5, comp );
正如第一条评论中提到的那样,sort(a, a+5 ...对于清洁工而言,这只是一个丑陋的简短形式sort(std::begin(a), std::end(a) ...
首先，如果您给出的vector<vector<int>> array话，只需使用即可排序：sort(begin(array), end(array))因为vector定义了字典比较函数：http ://en.cppreference.com/w/cpp/container/vector/operator_cmp
也就是说，使用 a vector-of- vectors 也有缺点：向量的向量有哪些问题？这显然不是你想要的。鉴于int array[5][2]尝试使用sort将产生：
错误 C3863：数组类型“int [2]”不可分配
我们不需要使用swap来交换 2 int[2]s，我们只需要交换 的字节sizeof(*array)，这可以使用WhozCraig 的答案qsort建议来完成，但我们可以对此进行改进，使我们的比较器能够处理任何大小的子数组。给定或任何所需的尺寸我们可以写：int array[5][2]
static const auto SIZE = size(*array);
qsort(array, size(array), sizeof(*array), [](const auto lhs, const auto rhs) {
const auto first = reinterpret_cast<const int*>(lhs);
const auto last = next(first, SIZE);
const auto its = mismatch(first, last, reinterpret_cast<const int*>(rhs));
if (its.first == last) {
return 0;
} else if (*its.first < *its.second) {
return -1;
} else {
return 1;
}});
快速注释array不应用作变量名称，因为它定义了标准类型，通过此更改，您可以在此处找到示例： http: //ideone.com/87AoIr
老实说，因为你ints的第二维只有两个，我会用一个对的数组来代替，它们有自己的内置比较函数。使用类似pair<int,int> arr[200]，您将能够调用内置的 sort 函数sort(arr, arr + 200)，该函数将按第一个元素对数组进行排序，然后按第二个元素排序。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
// pair of integers
pair<int, int> arr[1000];
// fill array with random numbers
random_device rd;
mt19937 rng(rd());
uniform_int_distribution<int> uni(0,1000);
for(int i = 0; i < 10; i++) {
// make_pair(x, y) creates a pair with two integers x and y
arr[i] = make_pair(uni(rng), uni(rng));
}
// prints out initial array
cout << "BEFORE ARRAY..." << endl;
for(int i = 0; i < 10; i++) {
// .first and .second call the first and second ints in the pair respectively
cout << arr[i].first << " " << arr[i].second << endl;
}
cout << endl;
// sort the array by calling built in sort function
sort(arr, arr + 10);
// prints out array
cout << "FINAL ARRAY..." << endl;
for(int i = 0; i < 10; i++) {
cout << arr[i].first << " " << arr[i].second << endl;
}
cout<<endl;
}
运行此程序时，您会看到数组现在已排序：
BEFORE ARRAY...
726 562
916 348
594 6
515 872
976 960
662 169
529 317
789 702
74 255
330 574
FINAL ARRAY...
74 255
330 574
515 872
529 317
594 6
662 169
726 562
789 702
916 348
976 960
注意第二个元素也是如何排序的，但次于
如果最终容器不重要，那么使用地图怎么样？
#include<map>
std::map<int, int> m;
for(std::size_t i = 0; i < 5; ++i )
m[array[i][0]] = array[i][1] ;
您现在可以复制m回您的array
std::size_t i=0;
for(const auto& x:m)
{
array[i][0] = x.first ;
array[i++][1] = x.second ;
}