当前位置：文江博客话题详情

如何使用 C++ 创建双重排序整数数组？

发布于 2024-12-17 17:53:11 字数 770 浏览 0 评论 0原文

我有 3 列整数数组，其最后 2 个元素用于排序。例如

10 0 1
11 0 2
12 1 2
13 0 1

我希望他们成为：

10 0 1
13 0 1
11 0 2
12 1 2

数组首先根据第二列排序，然后再次根据第三列排序。

我有超过 3000 行，所以我需要一些快速的东西。你怎么能在c++中做到这一点？

注意：将使用以下模板动态分配数组：

template <typename T>
T **AllocateDynamic2DArray(int nRows, int nCols){
    T **dynamicArray;

    dynamicArray = new T*[nRows];
    for( int i = 0 ; i < nRows ; i++ ){
        dynamicArray[i] = new T[nCols];
        for ( int j=0; j<nCols;j++){
            dynamicArray[i][j]= 0;
        }
    }
    return dynamicArray;
}

in main,

int ** lineFilter = AllocateDynamic2DArray(2*numberOfLines,3);

原文

I have 3-column integer arrays, whose last 2 elements are for sorting. For example

10 0 1
11 0 2
12 1 2
13 0 1

I want them to become:

10 0 1
13 0 1
11 0 2
12 1 2

The arrays are first sorted according to the 2nd column, and then again according to 3rd column.

I have over 3000 rows, so I need something also fast. How can you do this in c++?

Note: The array will be allocated dynamically using the following templates:

template <typename T>
T **AllocateDynamic2DArray(int nRows, int nCols){
    T **dynamicArray;

    dynamicArray = new T*[nRows];
    for( int i = 0 ; i < nRows ; i++ ){
        dynamicArray[i] = new T[nCols];
        for ( int j=0; j<nCols;j++){
            dynamicArray[i][j]= 0;
        }
    }
    return dynamicArray;
}

in main,

int ** lineFilter = AllocateDynamic2DArray(2*numberOfLines,3);

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

千里故人稀 2024-12-24 17:53:11

您可以使用 std::sort() ；但是，由于您的数组是二维的，这会变得复杂。

一般来说，std::sort()不能吃2D数组；您必须创建一个类来绕过编译器警告和投诉：

#include <iostream>
#include <algorithm>

int data[4][3] = {
    {10,0,1},
    {11,0,2},
    {12,1,2},
    {13,0,1}
};

struct row_t { // our type alias for sorting; we know this is compatible with the rows in data
    int data[3];
    bool operator<(const row_t& rhs) const {
        return (data[1]<rhs.data[1]) || ((data[1]==rhs.data[1]) && (data[2]<rhs.data[2]));
    }
};              

int main() {
    std::sort((row_t*)data,(row_t*)(data+4));
    for(int i=0; i<4; i++)
        std::cout << i << '=' << data[i][0] << ',' << data[i][1] << ',' << data[i][2] << ';' << std::endl; 
    return 0;
}

如果您使用 std::vector 来保存真正属于 row_t 类型的项目，则会变得容易得多> 或类似的。向量是动态调整大小和可排序的。

you can use std::sort(); however, this is complicated by your array being 2D.

In general, std::sort() can't eat 2D arrays; you have to create a class to cast around the compiler warnings and complaints:

#include <iostream>
#include <algorithm>

int data[4][3] = {
    {10,0,1},
    {11,0,2},
    {12,1,2},
    {13,0,1}
};

struct row_t { // our type alias for sorting; we know this is compatible with the rows in data
    int data[3];
    bool operator<(const row_t& rhs) const {
        return (data[1]<rhs.data[1]) || ((data[1]==rhs.data[1]) && (data[2]<rhs.data[2]));
    }
};              

int main() {
    std::sort((row_t*)data,(row_t*)(data+4));
    for(int i=0; i<4; i++)
        std::cout << i << '=' << data[i][0] << ',' << data[i][1] << ',' << data[i][2] << ';' << std::endl; 
    return 0;
}

It becomes much easier if you use a std::vector to hold your items that really are of type row_t or such. Vectors are dynamically sized and sortable.

回复收藏 0 原文

卸妝后依然美 2024-12-24 17:53:11

我认为这应该可行：

template<typename T>
struct compareRows {
    bool operator() (T * const & a, T * const & b) {
        if (a[1] == b[1])
            return a[2] < b[2];
        else
            return a[1] < b[1];
    }
};

std::sort(dynamicArray, dynamicArray+nrows, compareRows<int>());

使用函子来实现行之间的比较。排序将获取指向每行开头的指针，并根据行的内容交换它们。这些行将保留在内存中的相同位置。

I think this should work:

template<typename T>
struct compareRows {
    bool operator() (T * const & a, T * const & b) {
        if (a[1] == b[1])
            return a[2] < b[2];
        else
            return a[1] < b[1];
    }
};

std::sort(dynamicArray, dynamicArray+nrows, compareRows<int>());

Use a functor to implement the comparison between the rows. The sort will take pointers to the beginning of each row and swap them according to the contents of the rows. The rows will stay in the same places in memory.

回复收藏 0 原文

〗斷ホ乔殘χμё〖 2024-12-24 17:53:11

好的，OP有一个三列整数数组，这并不容易排序，因为你不能分配数组。

一种选择是使用结构数组，其中结构每一列包含一个元素，编写自定义比较例程并使用 std::sort。

另一种选择是假装我们有这样一个结构体数组，并利用reinterpret_cast的邪恶之处，如下所示：

#include <algorithm>
#include <iostream>

struct elt_t
{
  int e0;
  int e1;
  int e2;
};

int
compare (const elt_t &a, const elt_t &b)
{
  if (a.e1 == b.e1)
    return a.e2 < b.e2;
  else
    return a.e1 < b.e1;
}

int a [10][3] = 
{
  { 10, 0, 1 },
  { 11, 0, 2 },
  { 12, 1, 2 },
  { 13, 0, 1 }
};


int
main ()
{
  std::sort (reinterpret_cast<elt_t *>(&a[0]),
             reinterpret_cast<elt_t *>(&a[4]), compare);

  int i, j;

  for (i = 0; i < 4; ++i)
    std::cout << a [i][0] << ", " << a [i][1] << ", " << a [i][2] << std::endl;

  return 0;
}

当然，这是否符合标准是非常有争议的：）

编辑：

由于动态分配矩阵的附加要求，您可以使用 std::vector 数组，或 std:: 向量向量：

#include <algorithm>
#include <iostream>
#include <vector>

int
compare (const std::vector<int> &a, const std::vector<int> &b)
{
  if (a[1] == b[1])
    return a[2] < b[2];
  else
    return a[1] < b[1];
}


std::vector<int> *
make_vec (unsigned int r, unsigned int c)
{
  std::vector<int> *v = new std::vector<int> [r];

  /* Don't care for column count for the purposes of the example.  */
  v [0].push_back (10); v [0].push_back (0); v [0].push_back (1);
  v [1].push_back (11); v [1].push_back (0); v [1].push_back (2);
  v [2].push_back (12); v [2].push_back (1); v [2].push_back (2);
  v [3].push_back (13); v [3].push_back (0); v [3].push_back (1);

  return v;
}

int
main ()
{
  std::vector<int> *v = make_vec (4, 3);

  std::sort (&v[0], &v[4], compare);

  int i, j;

  for (i = 0; i < 4; ++i)
    std::cout << v[i][0] << ", " << v [i][1] << ", " << v [i][2] << std::endl;

  delete [] v;
  return 0;
}

OK, the OP has a three-column integer arrays, which is not straightforward to sort, because you can't assign arrays.

One option is to have arrays of structs, where the struct contains one element for each column, write a custom compare routine and use std::sort.

Another option is to pretend we have such an array of structs and employ the evilness of reinterpret_cast, like below:

#include <algorithm>
#include <iostream>

struct elt_t
{
  int e0;
  int e1;
  int e2;
};

int
compare (const elt_t &a, const elt_t &b)
{
  if (a.e1 == b.e1)
    return a.e2 < b.e2;
  else
    return a.e1 < b.e1;
}

int a [10][3] = 
{
  { 10, 0, 1 },
  { 11, 0, 2 },
  { 12, 1, 2 },
  { 13, 0, 1 }
};


int
main ()
{
  std::sort (reinterpret_cast<elt_t *>(&a[0]),
             reinterpret_cast<elt_t *>(&a[4]), compare);

  int i, j;

  for (i = 0; i < 4; ++i)
    std::cout << a [i][0] << ", " << a [i][1] << ", " << a [i][2] << std::endl;

  return 0;
}

Of course, whether or not this is standards compliant is highly debatable :)

EDIT:

With the added requirement for the matrix to by dynamically allocated, you can use an array of std::vector, or a vector of std::vector:

#include <algorithm>
#include <iostream>
#include <vector>

int
compare (const std::vector<int> &a, const std::vector<int> &b)
{
  if (a[1] == b[1])
    return a[2] < b[2];
  else
    return a[1] < b[1];
}


std::vector<int> *
make_vec (unsigned int r, unsigned int c)
{
  std::vector<int> *v = new std::vector<int> [r];

  /* Don't care for column count for the purposes of the example.  */
  v [0].push_back (10); v [0].push_back (0); v [0].push_back (1);
  v [1].push_back (11); v [1].push_back (0); v [1].push_back (2);
  v [2].push_back (12); v [2].push_back (1); v [2].push_back (2);
  v [3].push_back (13); v [3].push_back (0); v [3].push_back (1);

  return v;
}

int
main ()
{
  std::vector<int> *v = make_vec (4, 3);

  std::sort (&v[0], &v[4], compare);

  int i, j;

  for (i = 0; i < 4; ++i)
    std::cout << v[i][0] << ", " << v [i][1] << ", " << v [i][2] << std::endl;

  delete [] v;
  return 0;
}

回复收藏 0 原文

何止钟意 2024-12-24 17:53:11

将其用于第二列，然后用于第三列。现在它适用于单个暗淡阵列

   int *toplace(int *start, int *end)
{
    int *i = start+1, *j= end-1;

    while(i<=j)
    {
    while(*i<=*start && i<=j) {i++;}
    while(*j>=*start && i<=j) {j--;}    
    if (i<j) std::swap(*i++,*j--); 
    }

    std::swap(*start,*(i-1)); 
    return i-1;
}



void quicksort(int *start, int *end)
{
    if (start >= end) return;

    int *temp = start;
    temp = toplace(start,end);

    quicksort(start,temp);
    quicksort(temp+1,end);

}

use this for the second column and then for the third. Now it works for single dim arrays

   int *toplace(int *start, int *end)
{
    int *i = start+1, *j= end-1;

    while(i<=j)
    {
    while(*i<=*start && i<=j) {i++;}
    while(*j>=*start && i<=j) {j--;}    
    if (i<j) std::swap(*i++,*j--); 
    }

    std::swap(*start,*(i-1)); 
    return i-1;
}



void quicksort(int *start, int *end)
{
    if (start >= end) return;

    int *temp = start;
    temp = toplace(start,end);

    quicksort(start,temp);
    quicksort(temp+1,end);

}

回复收藏 0 原文