Best STL containers to avoid heap fragmentation
<p>I have a program which analyzes 150,000 files.  Valgrind reports no memory leak but the program slows over time.</p>

<p>Some of the problems were related to using std::string too often and mktime taking too much time. (see <a href="https://stackoverflow.com/questions/37928455/c-slows-over-time-reading-70-000-files">C++ slows over time reading 70,000 files</a>)</p>

<p>But it still slows down over time.  <a href="https://stackoverflow.com/users/1253006/lotharyx">Lotharyx</a> suggested that container usage is causing heap fragmentation.</p>

<p>I read the various flow charts on the pros and cons of the different STL containers but I didn't quite get it.</p>

<p>In the pseudo code below, I'm not sure I've made the right choices to avoid heap fragmentation.</p>

<pre><code>fileList.clear()
scan all disks and build "fileList", a std::set of file paths matching a pattern.

// filepaths are named by date, eg 20160530.051000, so are intrinsically ordered 

foreach(filePath in fileList)
{
    if (alreadyHaveFileDetails(filePath))
        continue;

    // otherwise
    collect file details into a fileInfoStruct;  // like size, contents, mod 

    fileInfoMap[time_t date] = fileInfoStruct;
}

// fileInfoMap is ordered collection of information structs of about 100,000 files

// traverse the list in order
foreach (fileInfo in fileInfoMap)
{
    if (meetsCondition(fileInfo))
    {
        TEventInfo event = makeEventInfo()
        eventList.push_back(event);
    }
}
</code></pre>

<p>And the above sequence repeats forever.</p>

<p>So for choice of containers, I've used (or need):</p>

<p><code>fileList</code> -- list of unique strings containing 150,000 pathnames.<br>
I chose std::set because it it automatically handles duplicates and maintains sort order automatically.
No random access, only add the entries, sort them (manually or automatically), and iterate over them.</p>

<p><code>fileInfoMap</code> -- an array of structures keyed by a time_t timestamp corresponding to the date of the file.
I chose std::map.  It too would have 150,000 entries so occupies a lot of memory.
No random access, only add the entries to one end. Must iterate over them and, if necessary, delete entries from the middle.</p>

<p><code>eventList</code> -- a small list of "event" structures, say 50 items.
I chose std::vector.  Not sure why really.
No random access, only add entries to one end and later iterate over the collection.</p>

<p>I'm fairly new to C++.  Thanks for your consideration.</p>