结构数组的 C++ 新顺序

Question

我有一个结构数组，其中每个结构都有一个 id (int) 和一个名为 aktiv (boolean) 的值。我想将结构数组传递给对结构进行排序的函数。数组中 aktiv 值为 0（假）的结构应该在我的数组末尾。

我以为我创建了第二个数组，在其中临时保存我的值，然后将第二个数组中的所有内容再次放入第一个数组中，但它起作用了。我做错了什么或者我应该改变什么。提前致谢。我的代码：

void naende(Item itf[], int dim) { 
Item* temp_arr = new Item[dim]{};
int temp = 0;
for (int i = 0; i < dim; i++) {
    if (itf[i].aktiv == 0) {
        temp_arr[dim - i].id = itf[i].id;
        temp_arr[dim - i].aktiv = itf[i].aktiv;
        //cout << temp_arr[i].id << endl;
    }
    else if (itf[i].aktiv == 1) {
        temp_arr[temp].id = itf[i].id;
        temp_arr[temp].aktiv = itf[i].aktiv;
        temp++;
    }
}

for (int j = 0; j < dim; j++) {
    itf[j] = temp_arr[j];
}
}

Answer 1

根据您发布的内容，如果目标是将所有 aktiv 为 0 的项目移动到数组的后面，则可以使用 std::partition。

#include <algorithm>

void naende(Item itf[], int dim) 
{ 
   std::partition(itf, itf + dim, [&](const Item& it) { return it.aktiv == 1; });
}

上面的代码将所有等于 1 的 aktiv 条目放在数组的左侧，所有 aktiv 等于 0 的条目放在数组的右侧。

如果需要保持相对顺序，那么可以使用std::stable_partition：

#include <algorithm>

void naende(Item itf[], int dim) 
{ 
   std::stable_partition(itf, itf + dim, [&](const Item& it) { return it.aktiv == 1; });
}

上面代码的重点是强调有STL算法或一组STL算法函数可以用来做很多通常需要手动编码解决方案的工作（这将不得不如有错误进行调试）。使用上述函数，如果给定有效参数，STL 算法函数不会失败。

现在假设您不能使用 std::partition，并且不需要保留顺序。如果是这种情况，那么实现这一点的方法可以是简单地拥有两个指针，并在关键时刻循环调用 std::swap。

它的工作方式是您将有一个在数组中向前的索引，以及另一个从数组末尾开始并向后移动的索引。第一个索引的递增，结束索引的递减，以及对 std::swap 的调用将以这种方式完成：

#include <algorithm>
#include <iostream>

struct Item
{
    int id;
    int aktiv;
};

void naende(Item itf[], int dim)
{
    int leftpos = 0;
    int rightpos = dim - 1;
    while (leftpos < rightpos)
    {
        if (itf[leftpos].aktiv == 0)
        {
            std::swap(itf[leftpos], itf[rightpos]);
            --rightpos;
        }
        else
            ++leftpos;
    }
}

int main()
{
    Item item[] = { {1,1},{2,0},{34,0},{32,1},{12,0},{12,1},{21,1} };
    naende(item, 7);
    for (int i = 0; i < 7; ++i)
        std::cout << item[i].id << " " << item[i].aktiv << "\n";
}

输出：

如果我们检测到 aktiv 值为 1，我们基本上只用左边的索引前进。如果它不是 1，那么我们通过交换将那个项目放在后面后面的项目，然后我们减少后面的项目索引。

对于稳定的物品，我会把它留作练习。

Answer 2

这是我没有 std::partition 的实现。

#include <iostream>

struct Item {
    int id;
    bool aktiv;
};

//in-place swap
void swap(Item& left, Item& right) {
    left.aktiv ^= right.aktiv;
    right.aktiv ^= left.aktiv;
    left.aktiv ^= right.aktiv;
    left.id ^= right.id;
    right.id ^= left.id;
    left.id ^= right.id;
}

void naende(Item itf[], const size_t dim) {
    if (dim < 2) return;    //array is empty or has one single item, so do nothing
    Item temp = itf[0];     //init the temp to take the first item (adds only 1 more item in memory space)
    size_t rightSwapIndex = dim-1;  //index to put the checked item at the rightmost position
    size_t leftSwapIndex = 0;       //index to put the checked item at the leftmost position
    for (size_t i = 0; i < dim; ++i) {  //consider exactly 'dim' cases (guarantees algorithm to be O(n) time)
        if (!temp.aktiv) {  //needs to moved to the rightmost position
            swap(temp, itf[rightSwapIndex--]);  //swap the temp with the last item; and move the rightSwapIndex to left by one
        } else {
            itf[leftSwapIndex] = temp;      //put the temp at the rightmost index (may have no effect but important!)
            temp = itf[++leftSwapIndex];    //take the next item to consider; and move the leftSwapIndex to right
        }
    }
}

void printDebug(Item array[], const size_t dim) {
    for (size_t i = 0; i < dim; ++i) {
        std::cout<<array[i].id<<"/"<<array[i].aktiv<<" ";
    }
    std::cout<<std::endl;
}

int main() {
    //build some test array with a sample data
    size_t size = 10;
    Item array[size];
    for (size_t i = 0; i < size; ++i) {
        array[i].id = i;
        array[i].aktiv = i%2;   //TODO: test with some other inits as well, like for ex. this one: array[i].aktiv = (i%3)%2;
    }

    //test the function naende()
    printDebug(array, size);    //print out the array before the call
    naende(array, size);        //call our cute function
    printDebug(array, size);    //print out the array after the call
}

输出：

0/0 1/1 2/0 3/1 4/0 5/1 6/0 7/1 8/0 9/1 
9/1 1/1 7/1 3/1 5/1 6/0 4/0 8/0 2/0 0/0

具有不同数组初始化的另一个输出（请参阅我上面带有 TODO 的评论行:)

0/0 1/1 2/0 3/0 4/1 5/0 6/0 7/1 8/0 9/0 
7/1 1/1 4/1 3/0 5/0 6/0 2/0 8/0 9/0 0/0

Answer 3

你的post不清楚，不过你可以试试这个:

#include <bits/stdc++.h>
using namespace std;

struct Item
{
    int active;
    int id;
};

void SortByStat(Item itf[], int dim)
{
    std::stable_partition(itf,itf + dim ,[](const Item &a){return a.active == 1;});

    //std::sort(itf, itf + dim, [](const Item &a, const Item &b) { return a.active < b.active; });
}

int main()
{
    Item arr[5] = {{0, 1}, {1, 2}, {0, 3}, {1, 4}, {1, 5}};
    int size = 5;
    for (int i = 0; i < size; i++)
    {
        cout << "id = " << arr[i].id << " => " << arr[i].active << endl;
    }

    cout << "After Sorting" << endl;

    SortByStat(arr, size);
    for (int i = 0; i < size; i++)
    {
        cout << "id = " << arr[i].id << " => " << arr[i].active << endl;
    }
}

结构数组的 C++ 新顺序

C++ New Order for Structure Array

c++

arrays

sorting

structure

function