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

问题:

I have an MFC project which, given an initial root path, iterates through every file, folder and subfolder, and subsequently displays each file to the user in a List Control. Since this can easily become a rather lengthy operation, I occasionally yield control to the operating system (via processing a single message pump queue), allowing each of the elements discovered thus far to be displayed. Now here comes the tricky part...

I would like to keep the elements sorted by their last known modification timestamps, which (I believe) would require some kind of insertion sorting technique. Since some elements may contain duplicate timestamps, but different file paths, and we would be sorting by timestamp (stored as an std::string in the format of MM:DD:YY hh:mm), a simple std::vector doesn't appear to do the job. Also, I would prefer to not keep the user waiting for the entire operation to complete before starting to sort the elements, since the amount of time to wait is unknown and like I stated above, could easily become lengthy enough to make any person impatient.

Lastly, I would need some way to keep the elements inserted into the List Control equally mapped to the sorting operations on the container, so the user can see the most recently modified contents (and subcontents) of the root path in real-time.

What would be the proper container(s) and algorithm(s) to use in order to achieve this?
Here's basically what I'm doing now:

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).

回答1:

Just use a std::multimap, with the key type either an integer timestamp (the fastest way) or as you suggested a time string if the default string sort keeps the timestamp order (this is slower)

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

or

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

Insert with:

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

回答2:

An std::set keeps its element sorted according to its Comparator.

Edit : you need to provide a strictly-less-than, deterministic Comparator (forgot the mathematical term). If multiple identical timestamps are a possibility, you need to disambiguate with another property (an id, for example).

回答3:

To synchronize the sorting of the MFC control with your internal data structure, you could try a virtual list: The key is using the LVS_OWNERDATA style. The list will then not store the item data by itself but call back into your code to get the information needed to display an item. This is where you can jump into your custom sorted container and retrieve the information.

The article 'Using virtual lists' on codeproject appears to be pretty comprehensive.

Next, sorting itself. You can try a custom type that contains the text to display as well as the criterion to sort by in numeric format, e.g.:

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

For performance reasons it may be useful to insert multiple items into a vector and then sort it once before you give control back to the OS. You'll have to test whether this actually works better than directly inserting into a sorted container though.

Anyway, to easily switch between container types, you can specify a sort functor that can be used as sort predicate (could probably be done more elegant with C++11 lambdas):

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

Use it like this:

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