how to speed up map insertion?

Looks like I finally improved a little map insertion speed (sorting before inserting). What do you think about these results ? Are there anymore oprimisations ?

int main (int argc, char* argv []) {
  //a map<size_t, size_t> random initilisation
  std::map<size_t, size_t> m0, m1, m2;
  {
    std::vector<std::pair<size_t, size_t> > t (10000, std::pair<size_t, size_t> ((size_t) -1, (size_t) -1));
    std::vector<std::pair<size_t, size_t> >::iterator i (t.begin ());
    for (; i != t.end (); ++i) {
      i->first = rand () % 1000000;
      i->second = rand () %1;
    }
    m0.insert (t.begin (), t.end ());
    m2 = m1 = m0;
  }
  //vins :
  std::vector<std::pair<size_t, size_t> > vins (10000, std::pair<size_t, size_t> (0, 0));
  {
    std::vector<std::pair<size_t, size_t> >::iterator i (vins.begin ());
    for (; i != vins.end (); ++i) {
      i->first = rand () % 1000000;
      i->second = rand () %1;
    }
  }
  //normal insertion
  clock_t t0 (clock ()), t1 (t0);
  {
    std::map<size_t, size_t>::iterator ihint (m0.begin ());
    std::vector<std::pair<size_t, size_t> >::iterator i (vins.begin ());
    for (; i != vins.end (); ++i) {
      m0.insert (*i);
    }
  }
  t1 = clock ();
  std::cout << "normal hint insertion took " << (size_t) (t1 - t0) << " ticks" << std::endl;
  //reused hint insertion
  t0 = t1;
  {
    std::sort (vins.begin (), vins.end (), [] (std::pair<size_t, size_t>& p0, std::pair<size_t, size_t>& p1)->bool {
      return (p0.first < p1.first ? true:false);
    });
    std::map<size_t, size_t>::iterator ihint (m1.begin ());
    std::vector<std::pair<size_t, size_t> >::iterator i (vins.begin ());
    for (; i != vins.end (); ++i) {
      ihint = m1.insert (ihint, *i);
    }
  }
  t1 = clock ();
  std::cout << "hint insertion took " << (size_t) (t1 - t0) << " ticks" << std::endl;
  if (m0 != m1) std::cout << "but insertion is nok" << std::endl;
  else std::cout << "and insertion is ok" << std::endl;
}

A result on a Lenovo Think Centre :

normal hint insertion took 1927 ticks

hint insertion took 1658 ticks