4

我char*在一个文件中有一个数组。我工作的公司将数据存储在平面文件中。有时数据是排序的，但有时不是。我想对文件中的数据进行排序。

现在我可以从头开始编写代码来做到这一点。有没有更简单的方法？

当然，就地排序将是最好的选择。我正在处理大文件并且内存很小。但我会考虑所有选项。

所有字符串的长度相同。

这是一些示例数据：

the data is of fixed length
the Data is of fixed length
thIS data is of fixed lengt

这将表示长度为 28 的三个记录。应用程序知道长度。每条记录都以 CRLF ( \r\n) 结尾，尽管这对于这种排序无关紧要。

4

9 回答 9

15 
template<size_t length> int less(const char* left, const char* right) {
    return memcmp(left, right, length) < 0;
}

std::sort(array, array + array_length, less<buffer_length>);
于 2008-11-24T15:45:24.840 回答
6

如果您无法将数据放入 RAM，请使用 GNU 排序程序（外部）：它将对任意大小的文件进行排序，文件越大，创建进程的额外成本就越小。

于 2008-11-24T15:59:04.330 回答
5

您可以在数组本机数据类型上使用 STL 中的算法，而不仅仅是在 STL 容器上。但是，使用 std::sort 的另一个建议不会像发布的那样起作用，因为 strcmp 返回一个值，当字符串不相同时，所有比较的结果都为 true，而不仅仅是左侧小于右侧手边——这是 std::sort 想要的；左侧返回 true 的二元谓词小于右侧。

这有效：

struct string_lt : public std::binary_function<bool, char, char>
{
    bool operator()(const char* lhs, const char* rhs)
    {
        int ret = strcmp(lhs, rhs);
        return ret < 0;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    char* strings [] = {"Hello", "World", "Alpha", "Beta", "Omega"};
    size_t numStrings = sizeof(strings)/sizeof(strings[0]);

    std::sort(&strings[0], &strings[numStrings], string_lt());

    return 0;
}
于 2008-11-24T15:54:47.270 回答
3

boost::bind可以做到：

// ascending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) < 0); 

// descending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) > 0);

编辑：字符串不是以空结尾的：

// ascending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) < 0); 

// descending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) > 0);
于 2008-11-24T16:09:28.660 回答
2

可能最简单的方法是使用旧的 stdlib.h 函数 qsort。这应该有效：

qsort( array, num_elements, sizeof( char* ), strcmp )

请注意，这是标准 C，仅适用于英文文本。

如果您有一个 String 对象列表，那么在 C++ 中可以进行其他操作。

如果您在 Linux 上编写 gtk 或 Qt 应用程序，那么我建议您事先查看这些库。

于 2008-11-24T15:46:42.717 回答
2

如果文件很大并且不适合 RAM，您可以使用bin/bucket排序将数据拆分为较小的文件，最后将这些片段聚合到一个结果文件中。其他响应向您展示如何对每个单独的存储桶文件进行排序。

于 2008-11-24T15:50:34.160 回答
0

在 C 中对字符串数组进行排序的规范方法，因此在 C++ 中是一种可用但不一定推荐的方法，它使用以下间接级别strcmp()：

static int qsort_strcmp(const void *v1, const void *v2)
{
    const char *s1 = *(char * const *)v1;
    const char *s2 = *(char * const *)v2;
    return(strcmp(s1, s2));
}

static void somefunc(void)   // Or omit the parameter altogether in C++
{
    char **array = ...assignment...
    size_t num_in_array = ...number of char pointers in array...
    ...
    qsort(array, num_in_array, sizeof(char *), qsort_strcmp);
    ...more code...
}
于 2008-11-24T17:19:19.893 回答
0

我想到了几件事：

  1. 如果您的数据太大而无法放入内存，您可能只想在内存中建立文件偏移量的索引，然后对文件进行内存映射以访问字符串（取决于您的操作系统）。
  2. 就地将需要大量内存副本。如果可以，请使用 shell 排序。然后，一旦您知道最终顺序，就可以更容易地在线性时间内就地重新排序字符串。
  3. 如果字符串的长度都相同，那么您真的需要基数排序。如果您不熟悉基数排序，这里的基本思想是：基于比较的排序（即 what std::sort、qsort和任何其他通用排序）总是需要 O(N log N) 时间。基数排序一次比较单个数字（从K 长度的字符串开始str[0]和结束），并且总体上只需要 O(N) 时间来执行。str[K-1]

有关基数排序算法的详细描述，请参阅 Internet，这比我能提供的要好得多。除了我所说的之外，我会避免使用所有其他使用标准图书馆分类设施的解决方案。不幸的是，它们并不是为您设计的特定问题。

于 2008-11-25T13:46:41.477 回答
0

您可能想查看 POSIX 上的内存映射文件（请参阅http://en.wikipedia.org/wiki/Memory-mapped_file）、 mmap() 函数（http://en.wikipedia.org/wiki/Mmap）-投诉操作系统。您实际上将获得一个指向表示文件内容的连续内存的指针。

好的一面是操作系统会负责将文件的一部分加载到内存中，并根据需要再次卸载它们。

一个缺点是，如果多个进程可能访问该文件，您将需要解决某种形式的文件锁定以避免损坏。

另一个缺点是这并不能保证良好的性能 - 为此，您需要一个排序算法来尝试避免不断加载和卸载页面（当然，除非您有足够的内存来将整个文件加载到内存中）。

希望这给了你一些想法！

于 2008-11-26T17:58:00.377 回答