我可以使用哪个 STL 容器/算法来解决这个问题？

Question

我有一个 MFC 项目，给定一个初始根路径，循环遍历每个文件、文件夹和子文件夹，然后在列表控件中向用户显示每个文件。由于这很容易成为一个相当冗长的操作，我偶尔会将控制权交给操作系统（通过处理单个消息泵队列），从而允许显示迄今为止发现的每个元素。棘手的部分来了...

我想保持元素按其最后已知的修改时间戳排序，（我相信）这需要某种插入排序技术。由于某些元素可能包含重复的时间戳，但文件路径不同，我们将按时间戳排序（以 MM:DD:YY hh:mm 的格式存储为 std::string），简单的 std::vector 不会似乎能胜任这项工作。另外，我不想让用户在开始对元素进行排序之前等待整个操作完成，因为等待的时间是未知的，而且就像我上面所说的那样，很容易变得冗长到足以让任何人不耐烦。

最后，我需要一些方法来保持插入列表控件的元素同样映射到容器上的排序操作，这样用户就可以看到最近修改的根路径的内容（和子内容）实时.

为了实现这一点，应该使用什么合适的容器和算法？
这基本上是我现在正在做的事情：

void CFileSearchDlg::UpdateDirectoryList(std::string strRootPath)
{
    CFilesystem fs; // Helper class which uses C++11 <filesystem> to iterate through file path entries
    DWORD time = GetTickCount(); // Determines if we should yield control to the OS after a certain period of time
    m_listView.DeleteAllItems(); // Clears all current elements from the list view control

    /*
    // CFilesystem::Search() takes in a root path and a lambda expression, and executes the expression for each
    // element found within the root path, passing a basic_directory_entry<path> as a parameter to the lambda
    // expression, and will continue to parse until no entries are left (or until we return false)...
    */
    fs.Search(strRootPath, [&](CFilesystem::path_entry pe)
        {
            // This is primarily a Unicode project, so we need to convert the search results to an std::wstring
            std::string path = pe.path().string();
            std::wstring wpath;
            wpath.assign(path.begin(), path.end());

            // Get a Win32 handle to the file/folder, or display an error & exit
            auto hFile = CreateFileA(path.c_str(), GENERIC_READ, NULL, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
            if (hFile == INVALID_HANDLE_VALUE) {
                MessageBoxA(NULL, "Failed to open file", path.c_str(), MB_OK | MB_ICONERROR);
                return false; // Stop parsing
            }

            // Get the date & time attributes of the file/folder, or display an error & exit
            TCHAR fileTime[MAX_PATH];
            ZeroMemory(&fileTime, sizeof(TCHAR)* MAX_PATH);
            auto ret = GetLastWriteTime(hFile, fileTime, MAX_PATH);
            CloseHandle(hFile);
            if (!ret) {
                MessageBoxA(NULL, "Failed to get date & time attributes", path.c_str(), MB_OK | MB_ICONERROR);
                return false; // Stop parsing
            }
            std::wstring strTime(fileTime);

            /************************************************** 
            // THIS IS WHERE THE MAGIC IS SUPPOSED TO HAPPEN //
            /*************************************************/
            InsertPathItem(m_listView, wpath, strTime); // ... But how?

            // Check if we should yield control to the operating system
            auto tick = GetTickCount();
            if (tick - time > 100) {
                YieldControl();
                time = tick;
            }

            // Continue to parse directory contents
            return true;
        }
    );
}

EDIT: The full answer appears to be a combination of galinette's (about the proper STL container), and foraidt's (about synchronizing the view with the data).

Answer 1

只需使用 std::multimap，键类型可以是整数时间戳（最快的方法），或者如果默认字符串排序保持时间戳顺序（这样较慢），则您建议使用时间字符串

std::multimap<time_t, std::wstring>

或

std::multimap<std::string, std::wstring>

插入：

myFileMap.insert(std::pair<time_t, std::wstring>(time,wPath));

Answer 2

一个 std::set 保持其元素根据其比较器排序。

编辑：您需要提供一个严格小于、确定性的比较器（忘记了数学术语）。如果可能有多个相同的时间戳，则需要用另一个属性（例如一个 id）来消除歧义。

Answer 3

要同步 MFC control 的排序与您的内部数据结构，您可以尝试虚拟列表：关键是使用 LVS_OWNERDATA 样式。然后列表将不会自己存储项目数据，而是回调到您的代码中以获取显示项目所需的信息。您可以在此处跳入自定义排序容器并检索信息。

这篇文章 'Using virtual lists' on codeproject 看起来很全面。

接下来，排序本身。您可以尝试自定义类型，其中包含要显示的文本以及以数字格式排序的标准，例如：

struct item {
    std::string label;
    time_t mtime;
};

出于性能原因，将多个项目插入向量中然后在将控制权交还给 OS 之前对其进行一次排序可能很有用。不过，您必须测试这是否真的比直接插入排序容器更好。

无论如何，要在容器类型之间轻松切换，您可以指定一个可用作排序谓词的排序仿函数（使用 C++11 lambda 可能做得更优雅）：

struct item_less {
    bool operator()(const item & a, const item & b) {
        return a.mtime < b.mtime;
    }
};

这样使用：

std::set<item, item_less> a; // Automatic sorting
std::vector<item> b;
std::sort(a.begin(), a.end(), item_less()); // Manual sorting

我可以使用哪个 STL 容器/算法来解决这个问题？

Which STL container(s)/algorithm(s) could I use to solve this?

c++

sorting

algorithm

containers

stl