2009/6/10 Christian Schladetsch <christian.schladetsch@gmail.com>:
monotonic: 0.005 std: 0.09
How about intrusive? I had to up the count to 0x101010 to get a measurable value, which gave the following timings (three runs, reported in order): mono: 1.37/1.41/1.38 std: 1.51/1.51/1.51 intrusive: 1.34/1.33/1.33 Upping it to 0x1010101 gave this: mono: 35.82/35.71/35.82 std: 37.94/37.83/37.81 intrusive: 36.17/35.78/35.62 GCC 4.3.3 with -O3, 32-bit linux on Core2. Here's the intrusive code: struct mylistnode : list_base_hook<link_mode<normal_link> > { int i; }; struct mymapnode : set_base_hook<link_mode<normal_link> > { list<mylistnode> v; int k; }; bool operator<(mymapnode const &lhs, mymapnode const &rhs) { return lhs.k < rhs.k; } union node { void *_; char mapnode[sizeof(mymapnode)]; char listnode[sizeof(mylistnode)]; }; int main() { unsigned const count = 0x101010;//101; // node nodes[count]; node *nodes = new node[count]; set<mymapnode> m; boost::timer timer; for (size_t i = 0; i < count; ++i) { int random = rand(); mymapnode &mapnode = *(new(nodes[i].mapnode) mymapnode); mapnode.k = random; set<mymapnode>::iterator iter = m.find(mapnode); if (iter == m.end()) { m.insert(mapnode); } else { mapnode.~mymapnode(); mylistnode &listnode = *(new(nodes[i].listnode) mylistnode); iter->v.push_back(listnode); } } double elapsed = timer.elapsed(); cout << "intrusive: " << elapsed << endl; }