gpt4 book ai didi

c++ - 通过 std::sort 对 C 二维数组进行排序

转载 作者:塔克拉玛干 更新时间:2023-11-03 00:42:27 26 4
gpt4 key购买 nike

我有一个二维数组a[][40]。我正在尝试通过调用 std::sort 对其进行排序,并且我已经编写了 Compare 函数。但是,C++ 希望我有一个要排序的 std::vector,而不是一个简单的数组,我希望排序后的数组是 a本身,我不想创建另一个数组并将排序结果保存在那里。似乎有很多方法可以实现这一目标。我可以想到五种方法,但似乎没有一种有效且有效。

1)

Directly use std::sort(std::begin(a), std::begin(a) + something, cmp);

它不起作用,因为 std::begin 不知道如何指向二维数组的开头。此外,即使编译它也会排序不正确,因为二维数组不是对数组的引用的数组,而是连续的数组(与 Java 不同)

Playground :https://godbolt.org/g/1tu3TF

2)

std::vector<unsigned char[40]> k(a, a + x);
std::sort(k.begin(), k.end(), cmp);

Then copy everything back to a

它不起作用,因为它是一个二维数组,并且不能使用 std::sort 这样排序。与第一个试验相比,这个试验使用两倍的内存,并将所有内容复制两次(如果有效的话)!

Playground :https://godbolt.org/g/TgCT6Z

3)

std::vector<int> k(x);
for (int i = 0; i < x; k[i] = i, i++);
std::sort(k.begin(), k.end(), cmp2);

Then change the order of a to be the same of k;

The idea is simple, create a vector of representative "pointers", sort them (as the cmp2 function secretly accesses a and compares the values), then make a have the same order with k.

最终,重新排序循环将非常复杂,需要一个大的临时变量。此外,对于 cmp2 访问 a 的值,必须创建一个指向 a 的全局变量指针,这是“不好的”代码。

Playground :https://godbolt.org/g/EjdMo7

4)

For all unsigned char[40], a struct can be created and their values can be copied to structs. Comparison and = operators will need to be declared. After sorted, they can be copied back to a.

如果不必将数组复制到结构体以使用结构体的运算符,那将是一个很好的解决方案,但它们需要被复制,因此所有值将被复制两次,并且需要两倍的内存被使用。

5)

For all unsigned char[40], a struct that has a pointer to them can be created. They can be sorted by the pointed values, and the result can be saved to a pointer array.

这可能是最好的选择,尽管结果是一个指针数组而不是 a。它之所以好的另一个原因是它不移动数组,而是移动指针。

总而言之,我需要通过std::sort对二维数组a[][40]进行排序,但我还没有决定最好的方法.似乎有一种我想不到的“最好的方法”。你能帮帮我吗?

编辑:为了澄清,我希望 {{3,2}{1,4}} 成为 {{1,4}{3, 2}}

最佳答案

问题不在于迭代二维数组。如果列大小是 constexpr 值,则指向数组的指针是很好的迭代器。

但是所有 C++ 排序(或变异)算法都要求基础类型是可移动构造和可移动赋值的,而数组是不可赋值的。但是包装底层数组就足够了:

template <class T, int sz>
class wrapper {
T* base;
bool own; // a trick to allow temporaries: only them have own == true
public:
// constructor using a existing array
wrapper(T* arr): base(arr), own(false) {}

~wrapper() { // destructor
if (own) {
delete[] base; // destruct array for a temporary wrapper
}
}
// move constructor - in fact copy to a temporary array
wrapper(wrapper<T, sz>&& src): base(new T[sz]), own(true) {
for(int i=0; i<sz; i++) {
base[i] = src.base[i];
}
}
// move assignment operator - in fact also copy
wrapper<T, sz>& operator = (wrapper<T, sz>&& src) {
for(int i=0; i<sz; i++) {
base[i] = src.base[i];
}
return *this;
}
// native ordering based on lexicographic string order
bool operator < (const wrapper<T, sz>& other) const {
return std::char_traits<char>::compare(base, other.base, sz) < 0;
}
const T* value() const { // access to the underlying string for tests
return base;
}
};

然后,您可以使用任何 C++ 排序算法对 C 兼容的二维数组进行排序:

std::vector<wrapper<char, 40> > v { &arr[0], &arr[sz] };  // pointer are iterators...
std::sort(v.begin(), v.end()); // and that's all!

for (int i=0; i<sz; i++) { // control
std::cout << arr[i] << std::endl;
}

开销是一个包含指针和bool的结构 vector ,但排序的实际上是原始的二维数组。

当然,由于可以从 C++ 访问 C 库,因此 qsort 对于 C 兼容二维数组的排序肯定会更容易。但是这种方式允许使用 stable_sortpartial_sort 如果它们是相关的。

关于c++ - 通过 std::sort 对 C 二维数组进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50792843/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com