Sorting an STL map

[Mike Copeland]

I have implemented an STL map allowing me to store and update
information reasonably well...but I need to "dump" its contents in a
different order than it was built.. Specifically,

struct Fin_Struct
{ // Individual Finisher data
string finName; // Finisher Name (Last, First M.)
string finDoB; // (derived) DoB from event Age/Year
char finSex; // gender
int finishCount; // # Finishes by this participant
long finIdNum; // unique Finisher (link) Id
short finSrcCount; // Count of Source roots
} finWork;
typedef map<string, Fin_Struct> Fin_Type;
Fin_Type finMap;
Fin_Type::iterator finIter;

The map's key is the string "finName", and the incoming data sources
do not come into the program sorted by that field. Once the map is
populated (currently ~400,000 objects constructed from ~100 input
files), I need to write out the data in "key order". However, iterating
through the map doesn't produce the data from the entire data set in
that order. For example, if "Adams" is stored and updated after
"Baker" is first processed, "Adams" should come out before "Baker", etc.
- but it doesn't.
Ultimately, I want to output to be in name order, but since there's
no "map sort" I can't see how to accomplish this with the STL map. Is
there a way to do what I want, or is map the wrong container for my
application. (Please consider that the data volume is high, and the
bulk of the processing is in the storing/accumulating of the data set.)
Any thoughts? TIA

 

[Alf P. Steinbach]

I have implemented an STL map allowing me to store and update
information reasonably well...but I need to "dump" its contents in a
different order than it was built.. Specifically,

struct Fin_Struct
{ // Individual Finisher data
string finName; // Finisher Name (Last, First M.)
string finDoB; // (derived) DoB from event Age/Year
char finSex; // gender
int finishCount; // # Finishes by this participant
long finIdNum; // unique Finisher (link) Id
short finSrcCount; // Count of Source roots
} finWork;
typedef map<string, Fin_Struct> Fin_Type;
Fin_Type finMap;
Fin_Type::iterator finIter;

The map's key is the string "finName", and the incoming data sources
do not come into the program sorted by that field. Once the map is
populated (currently ~400,000 objects constructed from ~100 input
files), I need to write out the data in "key order". However, iterating
through the map doesn't produce the data from the entire data set in
that order. For example, if "Adams" is stored and updated after
"Baker" is first processed, "Adams" should come out before "Baker", etc.
- but it doesn't.

It should.

One possible problem is leading spaces. Trim down the strings.

Another possible problem is uppercase versus lowercase. I suggest to
translate all map key strings (but not the data) to lowercase.

However, the best is to reproduce the problem in a minimal program.

Trying that may tell you directly what the problem is, and if it
doesn't, then you have a nice little concrete example to post here.

Ultimately, I want to output to be in name order, but since there's
no "map sort" I can't see how to accomplish this with the STL map.

Isn't name order the same as "finName" order?

Is
there a way to do what I want, or is map the wrong container for my
application.

It's unclear what you want. However, if the goal is to get those records
sorted on name, then a map is a good choice. You can define a sort order
simply by specifying a custom comparator as map template parameter; see
<url: http://en.cppreference.com/w/cpp/container/map>.

If you want to be able to access the records in various orders then you
can store them unordered, e.g. in a vector, and use one map (with
pointers to the data) for each desired order.


Cheers & hth.,

- Alf