I have a boost multi_index_container declared as below which is indexed by hash_unique id(unsigned long) and hash_non_unique transaction id(long). Insertion and retrieval of elements is fast but when I delete elements, it is much slower. I was expecting it to be constant time as key is hashed.

e.g To erase elements from container

for 10,000 elements, it takes around 2.53927016 seconds

for 15,000 elements, it takes around 7.137100068 seconds

for 20,000 elements, it takes around 21.391720757 seconds

Is it something I am missing or is it expected behavior?

class Session
{
  public:
    Session() {
      //increment unique id
      static unsigned long counter = 0;
      boost::mutex::scoped_lock guard(mx);
      counter++;
      m_nId = counter;
    }

    unsigned long GetId() {
     return m_nId;
    }
    long GetTransactionHandle(){
    return m_nTransactionHandle;
    }
    ....
private:
  unsigned long m_nId;
  long m_nTransactionHandle;
  boost::mutext mx;
  ....
};

typedef multi_index_container<
  Session*,
  indexed_by< 
    hashed_unique< mem_fun<Session,unsigned long,&Session::GetId> >,
    hashed_non_unique< mem_fun<Session,unsigned long,&Session::GetTransactionHandle> >
    >  //end indexed_by
  > SessionContainer;
typedef SessionContainer::nth_index<0>::type SessionById;


int main() {
  ...
   SessionContainer container;
   SessionById *pSessionIdView = &get<0>(container);
   unsigned counter = atoi(argv[1]);
   vector<Session*> vSes(counter);
   //insert
   for(unsigned i = 0; i < counter; i++) {
     Session *pSes = new Session();
     container.insert(pSes); 
     vSes.push_back(pSes);
   }
   timespec ts;
   lock_settime(CLOCK_PROCESS_CPUTIME_ID, &ts);
   //erase
   for(unsigned i = 0; i < counter; i++) {
      pSessionIdView->erase(vSes[i]->getId());
      delete vSes[i];
   }
   lock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
   std::cout << "Total time taken for erase:" << ts.tv_sec << "." << ts.tv_nsec << "\n";
   return (EXIST_SUCCESS);
}