help with efficiency of map traversal c++

I have a map defined as

map<string,map<string,int> > subjectCodes;

each subject string has its own map of courses

I also have 2 iterators defined

map<string,map<string,int> >::iterator it;
map<string,int>::iterator jt;

one to iterate thru each subject and one to iterate thru each course per subject

I need to make my program read in 50,000 lines of info, sort them into the开发者_如何学运维 map, and print all in under 1 second. I think I have figured out the fastest way to add everything into the map, but I'm struggling to speed up the printing, which is 0(n squared) at the moment and causes my program to take around 3 seconds to run.

here is my print code:

//print out sorted list
for(it=subjectCodes.begin();it!=subjectCodes.end();it++)
{
    cout<<it->first<<": "<<(it->second).size()<<" courses"<<endl;
    for(jt=(it->second).begin();jt!=(it->second).end();jt++)
    {
        cout<<"  "<<jt->first<<": "<<jt->second<<" classes"<<endl;
    }
}

is there a more efficient way of printing a map in a map that someone could show me? Thank you

A simple efficiency saving:

   cout<<"  "<<jt->first<<": "<<jt->second<<" classes"<<endl;

should be:

   cout<<"  "<<jt->first<<": "<<jt->second<<" classes"<< '\n';

The endl manipulator flushes the stream, which can be a very expensive operation, if you don't need the flush. You should easily be able to write 50K lines to a stream in a minute, though possibly not to a stream connected to a terminal of some sort (i.e. to an xterm or a Windows cmd prompt window).

I can't tell what your data looks like, but you might have better luck with "composite keys." That is, instead of using a map full of maps, concatenate the two keys together and use the result as the key in a single map.

Also, if you're not modifying the map after it's created, consider using a sorted vector instead (using std::sort and std::binary_search). When you iterate the data, it's all contiguous in memory and you'll get better cache performance.

Did you think about parallelizing your application, e.g with Threads or OpenMP?

another tip: the printf() function might be faster than streaming option.

also, did you compile with full optimizations? this might also provide a significant boost in performance.

When you are having performance problems, it is important to go after the low hanging fruit. To do this, you need to figure out how where the bottlenecks of your algorithm are. What is taking too long?

Once you have figured out what is taking time, you can start asking more specific questions. Typically going after the low-hanging fruit means that you should go after easy problems to solve that have a large impact on the speed of your algorithm. Two examples of that have already been pointed out in this thread (replace std::endl by '\n' to reduce the amount of flushing and using printf over std::cout to reduce the amount of function calls/different algorithm).

A few more possibilities:

• Use a stringstream and write that in a single operation
• Redesign your structure so it is faster to use in the way you typically use it (could a vector be used instead of a map at the second level?)
• Something completely unrelated to the block of code you wrote ;)