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);
}