Member Avatar for Web_Sailor

Hi :icon_smile:

I have written a C++ program which works very fine. The problem comes in terms of efficiency and speed. I am using a multimap which is required for my type of requirement.

multimap<string,string>

Now the problem is that for files more than 100 MB it takes a lot of time to load the data into multimap which slows down the program.

I am inserting Strings into the multimap. I even used references of string for insertion into multimap but not of much help.

My question is more conceptual. So what do I need to do to speed up my program ?

If I insert my strings into a vector and then insert that vector into multimap - will that increase the speed of my program ?

I mean something like this:

multimap<vector<string>,vector<string>>

Would appreciate any advice

Thanks in advance :-/

  • 3 Contributors
  • 3 Replies
  • 83 Views
  • 18 Hours Discussion Span
  • Latest Post Latest Post by Web_Sailor

Dani AI

Generated

Good call from to rethink the algorithm. A std::multimap does O(log N) work per insert and creates one tree node (and string allocations) per element, so building it incrementally from 100+ MB of records will be slow; see the multimap complexity notes on cppreference multimap complexity. Two practical patterns usually beat blind per-record tree inserts:

  • Grouped containers: use std::unordered_map<Key, std::vector<Value>> (or std::map<Key, std::vector<Value>> if you need order). One node per key, then append values into a vector; far fewer allocations and faster lookups for per-key work. Reserve buckets first to avoid rehashing.
  • Bulk then sort: push all (key,value) pairs into a single vector, reserve capacity, sort by key, then scan once to process each key’s range. Sorting is O(N log N) but has much lower per-element overhead than many tree node allocations; see vector behavior vector complexity and std::sort sort.

Small, effective micro-optimizations: use emplace/move to avoid copies, call equal_range/lower_bound only once per key (your posted loop repeatedly recomputes count/equal_range), reserve capacity for vectors and unordered containers, and consider string_view to parse without copying (only if the source buffer outlives the views) string_view. If allocations are the bottleneck, an arena/pool allocator or memory-mapped input can help. Profile first (simple timing around read vs insert) to know whether I/O, parsing, allocation, or tree balancing is the real culprit.

Example bulk-loading sketch:

std::vector<std::pair<std::string,std::string>> items;
items.reserve(estimated_count);
// read and emplace_back parsed key/value pairs, then:
std::sort(items.begin(), items.end(),
          [](auto &a, auto &b){ return a.first < b.first; });
// scan contiguous ranges for each key

For the posted code, replacing repeated count/equal_range calls with a single range lookup or switching to per-key vectors will yield the biggest immediate speedups.

Recommended Answers

All 3 Replies

Member Avatar for Nick Evan

All the thing mentioned by you could speed up your program. But the main question is: Why are you loading 100 mb of data in your memory? This might be a good time to review your algorithm!

Member Avatar for mrnutty

Post code. Reading 100mb, will take time.

Member Avatar for Web_Sailor

Lets suppose this code. My requirement is like the code below. Is there a way I can do such a thing using vector ? without loading into memory ?

// multimap::count
#include <iostream>
#include <map>
#include<vector>
#include<string>
using namespace std;

int main ()
{
  multimap<string,string> mymm;
  multimap<string,string>::iterator it;
  vector<string> vec1;
  vector<string>::iterator itv;

  mymm.insert(pair<string,string>("andrew","andrew S* years old"));
  mymm.insert(pair<string,string>("peter","peter 1 years old"));
  mymm.insert(pair<string,string>("peter","peter 2 years old"));
  mymm.insert(pair<string,string>("peter","peter 3 years old"));
  mymm.insert(pair<string,string>("mathew","mathew 1 years old"));
  mymm.insert(pair<string,string>("mathew","mathew 2 years old"));
  mymm.insert(pair<string,string>("Dsouza","Dsouza S* years old"));
  mymm.insert(pair<string,string>("Austin","Austin 1 years old"));
  mymm.insert(pair<string,string>("Austin","Austin 2 years old"));
  mymm.insert(pair<string,string>("Austin","Austin 3 years old"));
  mymm.insert(pair<string,string>("Austin","Austin 4 years old"));
  mymm.insert(pair<string,string>("Austin","Austin 5 years old"));
  mymm.insert(pair<string,string>("David","David S* years old"));
  mymm.insert(pair<string,string>("John","John 1 years old"));
  mymm.insert(pair<string,string>("John","John 2 years old"));

  vec1.push_back("Austin");
  vec1.push_back("andrew");
  vec1.push_back("David");
  vec1.push_back("peter"); 
  vec1.push_back("mathew");
  vec1.push_back("Dsouza");
  vec1.push_back("John");
                             
    for(itv=vec1.begin(); itv < vec1.end(); itv++)
  {
       int i = 0;
       int k = 0;
    for (it=mymm.equal_range(*itv).first; it!=mymm.equal_range(*itv).second; ++it)
      if((int)mymm.count(*itv)>2){      
         if(i==0){
            cout << "one"<<"\t"<<(*it).second << endl;
         }    
         else if(i>0 && i < ( mymm.count(*itv) - 1)){
            cout << "middle"<<"\t"<<(*it).second << endl;
         }
         else if(i !=0 ){     
            cout << "end"<<"\t"<<(*it).second << endl;
         }
       i++;
      }
      else if((int)mymm.count(*itv)==1){      
            cout << "Single"<<"\t"<<(*it).second << endl;   
      }
      else if((int)mymm.count(*itv)==2){      
         if(k==0){
            cout << "one" << "\t"<< (*it).second << endl;
         }
         else {
            cout << "end" << "\t" << (*it).second << endl; 
         } 
         k++;
      }
  }
  return 0;
}

Thanks

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.