Boost::filesystem,std::sort:在排序过程中无法保留信息

我正在尝试对包含从 boost::filesystem::dictionary_iterator 读取的信息的数据类型使用 std::sort.看来,由于排序算法已经进行了 n 比较,n 是目录中的文件数,因此该信息会丢失,我最终会出现段错误.Valgrind 说我正在使用未初始化的值并进行无效读取.

I'm trying to use std::sort on a data type that contains information read from a boost::filesystem::dictionary_iterator. It appears that as the sorting algorithm has done n comparisons, n being the number of files in the directory, that information gets lost and I end up segfaulting. Valgrind says I'm using uninitialized values and doing invalid reads.

如何更改我的 File 数据类型或算法,以便在两次传递之间保留信息?

How can I change my File data type or algorithms so that the information is kept between passes?

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <boost/filesystem.hpp>
namespace fs = boost::filesystem;

struct File {
    fs::path path;
    fs::file_status status;
};

bool comp(const File& a, const File& b) {
    static size_t count = 0;
    std::cout << "Compare function called " << ++count << " times" << std::endl;
    std::string a_filename = a.path.filename().native();
    std::string b_filename = b.path.filename().native();
    return a_filename.compare(b_filename);
}

int main() {
    std::vector<File> vec;

    // Read directory
    fs::directory_iterator it("/etc"), end;
    for (; it != end; it++) {
        File f = *(new File);
        f.path = it->path();
        f.status = it->status();
        vec.push_back(f);
    }

    std::sort(vec.begin(), vec.end(), comp);

    // Clean up
    for (std::vector<File>::iterator it = vec.begin(); it != vec.end(); it++)
        delete &(*it);

    return 0;
}

(这不是我的实际程序,但表现出相同的行为.)

(This is not my actual program, but exhibits the same behavior.)

推荐答案

最后对 compare() 的调用是错误的,它返回一个可以是-1、0 或 1 的 int,如 strcmp().改为使用对 std::less()(a_filename, b_filename) 的简单调用.还要确保你有单元测试,以确保比较器创建严格弱排序,这是 std::sort 所要求的.

The call to compare() at the end is wrong, it returns an int that can be -1, 0 or 1 like strcmp(). Use a simple call to std::less()(a_filename, b_filename) instead. Also make sure you have unit tests that make sure the comparator creates a strict-weak ordering, as is required for std::sort.

具有内部检查的比较器:

Comparator with internal checking:

inline bool do_compare(const File& a, const File& b)
{
    /* ... */
} 

bool compare(const File& a, const File& b)
{
    bool const res = do_compare(a, b);
    if(res)
        assert(!do_compare(b, a));
    return res;
}

如果定义了 NDEBUG(即 assert() 停用),编译器应该能够将其优化为与以前相同数量的代码.现在,我希望您编写按顺序对文件名 9.png、10.png 和 11.png 进行排序的代码.;)

If NDEBUG is defined (i.e. assert() deactivated) the compiler should be able to optimize this to the same amount of code as before. And now, I wish you much fun writing the code that sorts the filenames 9.png, 10.png and 11.png in that order. ;)

相关文章