boost multi_index_container 和删除性能

Question

我有一个 boost multi_index_container 声明如下，它由 hash_unique id(unsigned long) 和 hash_non_unique 事务 id(long) 索引。元素的插入和检索速度很快，但是当我删除元素时，速度要慢得多。我期待它是恒定的时间，因为 key 是散列的。

例如从容器中删除元素

对于 10,000 个元素，大约需要 2.53927016 秒

对于 15,000 个元素，大约需要 7.137100068 秒

对于 20,000 个元素，大约需要 21.391720757 秒

这是我遗漏的东西还是预期的行为？

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

Answer 1

在您的测试代码中，m_nTransactionHandle 的值是多少？做 Session对象接收？是否所有对象的值都相同？如果是这样，删除将需要很长时间，因为当有许多相等的元素时，散列容器的性能很差。尝试分配不同的 m_nTransactionHandle创建值以查看这是否会加快您的测试速度。