c++ - 更好的数组移位算法？

Question

我有一项作业，要求我在读取名称时对基于堆的C样式的名称数组进行排序，而不是先读取所有名称然后进行排序。这涉及到将数组的内容多移一位以允许插入新名称。我正在使用下面的代码，但是它非常慢。在不更改存储类型的情况下，我还有什么可以做的来优化它？

//the data member
string *_storedNames = new string[4000];

//together boundary and index define the range of elements to the right by one
for(int k = p_boundary - 1;k > index;k--)
   _storedNames[k]=_storedNames[k - 1];

编辑2:
如Cartroo所建议，我尝试将memmove与使用malloc的动态数据一起使用。当前，这可以正确移动数据，但是在重新分配过程中再次失败。我想念什么吗？

int numberOfStrings = 10, MAX_STRING_SIZE = 32;

char **array = (char **)malloc(numberOfStrings);

for(int i = 0; i < numberOfStrings; i++)
    array[i] = (char *)malloc(MAX_STRING_SIZE);

array[0] = "hello world",array[2] = "sample";   

    //the range of data to move
int index = 1, boundary = 4;
int sizeToMove = (boundary - index) * sizeof(MAX_STRING_SIZE);

memcpy(&array[index + 1], &array[index], sizeToMove);

free(array);

Answer 1

如果您对方法进行了最小的更改，则可以使用 memmove() 函数，该函数可能比您自己的手动版本要快。您不能按照一位评论者的建议使用 memcpy() ，因为不允许内存区域重叠(如果重叠，则行为是不确定的)。

在不更改存储类型或算法的情况下，您无能为力。但是，如果您更改为使用链表，则该操作将显着提高效率，尽管您将进行更多的内存分配。如果分配确实是一个问题(除非您使用的是有限的嵌入式系统，否则可能不是)，那么pool allocators或类似方法可能会有所帮助。

编辑:重新阅读您的问题，我猜您实际上不是在使用Heapsort，您的意思是说您的数组是在堆上分配的(即使用malloc())，并且您正在做一个简单的insertion sort。在这种情况下，尽管您应该意识到插入排序与大容量插入和后跟更好的排序算法(例如Quicksort，可以使用标准库 qsort() 实现)相比，插入的排序效率不高，但是下面的信息并不能直接为您使用功能)。如果您只需要最低(或最高)商品而不是完整排序的商品，那么Heapsort仍然是有用的阅读 Material 。

如果您使用的是标准Heapsort，则根本不需要此操作-项会附加在数组的末尾，然后使用“heapify”操作将它们交换到堆中的正确位置。每次交换只需要一个临时变量即可交换两个项目-不需要像您的代码片段中那样拖拉任何内容。它确实要求数组中的所有内容都具有相同的大小(固定大小的就地字符串，或者更有可能是指针)，但是您的代码似乎已经假定了(在标准char数组中使用可变长度的字符串)将是一件很奇怪的事情)。

请注意，严格来讲，Heapsort在二叉树上运行。由于您要处理数组，因此我假设您正在使用以下实现:使用连续数组，索引n处的节点的子级分别存储在索引2n和2n+1中。如果不是这种情况，或者根本不使用Heapsort，则应更详细地说明您将尝试做些什么以获得更有用的答案。

编辑:以下是对您上面更新的代码的回应。

在释放过程中看到问题的主要原因是，如果您践踏了一些内存-换句话说，您正在复制超出分配区域大小的内容。当您覆盖系统用于跟踪分配的值并引起各种问题(通常会导致程序崩溃)时，这确实是一件坏事。

首先，您似乎对内存分配和释放的性质有些困惑。您分配一个char*数组，它本身就可以。然后为每个字符串分配char数组，这也很好。但是，您只需要为初始数组调用free()-这还不够。需要调用free()来匹配每个对malloc()的调用，因此您需要释放分配的每个字符串，然后释放初始数组。

其次，将sizeToMove设置为sizeof(MAX_STRING_SIZE)的倍数，几乎可以肯定这不是您想要的。这是用于存储MAX_STRING_SIZE常量的变量的大小。相反，您需要sizeof(char*)。在某些平台上，它们可能是相同的，在这种情况下，事情仍然可以进行，但是不能保证。例如，我希望它能在32位平台(int和char*大小相同)上工作，但不能在64位平台(在它们不同的情况下)上工作。

第三，您不能仅将字符串常量(例如"hello world")分配给已分配的块-您在这里所做的就是替换指针。您需要使用strncpy()或memcpy()之类的东西将字符串复制到分配的块中。为了方便起见，我建议使用snprintf()，因为strncpy()的问题是不能保证最终结果为零，但这取决于您。

第四，您仍在使用memcpy()而不是memmove()来随机播放项目。

最后，我刚刚看到您的评论，您必须使用new和delete。没有等效的realloc()，但是如果一切都已知，那就可以了。您似乎想做的事情是这样的:

bool addItem(const char *item, char *list[], size_t listSize, size_t listMaxSize)
{
    // Check if list is full.
    if (listSize >= listMaxSize) {
        return false;
    }
    // Insert item inside list.
    for (unsigned int i = 0; i < listSize; ++i) {
        if (strcmp(list[i], item) > 0) {
            memmove(list + i + 1, list + i, sizeof(char*) * (listSize - i));
            list[i] = item;
            return true;
        }
    }
    // Append item to list.
    list[listSize] = item;
    return true;
}

我还没有进行编译和检查，因此请注意不存在的一次性错误等，但希望您能理解。无论您使用 malloc()和 free()还是 new和 delete，此函数都应该起作用，但是它假定您已经将字符串 item复制到了将要保留的分配缓冲区中，因为它当然存储了一个指针。

请记住，您当然需要在此函数之外自行更新 listSize －这只是为您将一个项目插入数组中的正确点。如果函数返回 true，则将 listSize的副本增加1-如果返回 false，则您未分配足够的内存，因此未添加项目。

还要注意，在C和C++中，对于 list数组，语法 &list[i]和 list + i是完全等效的-如果您更容易理解，请在 memmove()调用中使用第一个语法。