c++ - Best STL containers to avoid heap fragmentation -

i have program analyzes 150,000 files. valgrind reports no memory leak program slows on time.

some of problems related using std::string , mktime taking time. (see c++ slows on time reading 70,000 files)

but still slows down on time. lotharyx suggested container usage causing heap fragmentation.

i read various flow charts on pros , cons of different stl containers didn't quite it.

in pseudo code below, i'm not sure i've made right choices avoid heap fragmentation.

filelist.clear() scan disks , build "filelist", std::set of file paths matching pattern.  // filepaths named date, eg 20160530.051000, intrinsically ordered   foreach(filepath in filelist) {     if (alreadyhavefiledetails(filepath))         continue;      // otherwise     collect file details fileinfostruct;  // size, contents, mod       fileinfomap[time_t date] = fileinfostruct; }  // fileinfomap ordered collection of information structs of 100,000 files  // traverse list in order foreach (fileinfo in fileinfomap) {     if (meetscondition(fileinfo))     {         teventinfo event = makeeventinfo()         eventlist.push_back(event);     } } 

and above sequence repeats forever.

so choice of containers, i've used (or need):

filelist -- list of unique strings containing 150,000 pathnames.
chose std::set because it automatically handles duplicates , maintains sort order automatically. no random access, add entries, sort them (manually or automatically), , iterate on them.

fileinfomap -- array of structures keyed time_t timestamp corresponding date of file. chose std::map. have 150,000 entries occupies lot of memory. no random access, add entries 1 end. must iterate on them and, if necessary, delete entries middle.

eventlist -- small list of "event" structures, 50 items. chose std::vector. not sure why really. no random access, add entries 1 end , later iterate on collection.

i'm new c++. consideration.

about memory management, container belongs 2 large families: 1 allocate elements together, , 1 allocate elements separately.

vector , deque belong first family, list, set , map second.

memory fragmentation arises when elements continuously added , removed container not supporting global relocation.

one way avoid problem use vectors, using "reserve" anticipate memory need reduce relocations, , keeping data sorted upon insertion.

another way use "linking based container" (like list, set etc.) providing them allocator allocate memory larger chunks, recycling them instead of calling raw malloc/free every single element insert/remove.

give std::allocator

you can write allocator deriving std::allocator , overriding allocate/deallocate functions adding required logic, , passing yourallocator optional template parameter of container use.