Talk:cpp/container/map/emplace hint

The return type for emplace_hint is incorrect. And the fact that something will not be inserted if it already exists is missing. I attempted to edit in a correction, but was unable to. But I'm a rank beginner on this site.

Good catch, and yes, editing these templates can be a bit difficult. --Cubbi 18:56, 29 August 2012 (PDT)

There is no a word of exception safety. 195.16.110.88 04:27, 13 April 2016 (PDT)

added, thanks. --Cubbi (talk) 05:36, 13 April 2016 (PDT)

If the hint is correct, emplace_hint is fast

Here's an example (link). (If you change the code by uncommenting #define FALSE_HINT, you can see what happens if the hint is wrong.)

Run this code

#include <iostream>
#include <map>
#include <chrono>
 
/* uncomment one of the following 2 lines */
#undef  FALSE_HINT                            /* use correct hint */
//#define FALSE_HINT                            /* use false hint */
 
 
struct A {
    A(unsigned ii) : i(ii) { }
 
    unsigned i;
};
 
constexpr unsigned get_skew(unsigned i)
{
    unsigned ret = 0;
    for (unsigned j = i/2; j; j/=2) {
        ret += j;
    }
    return ret;
}
 
int main()
{
    constexpr unsigned loops  = 100000;
 
    constexpr unsigned num_el = 1000000;
    constexpr unsigned skew_key = get_skew(num_el) + (1-(get_skew(num_el)&1));         // odd key that we want to insert
 
    std::map<unsigned, A> m;
    for (unsigned i = 0; i < num_el; ++i) { const auto ii = i+i; m.emplace(ii, ii);  } // construct initial map with only even keys
 
    {
        const std::chrono::time_point<std::chrono::steady_clock> curr_tp = std::chrono::steady_clock::now();
        for (unsigned j = 0; j < loops; ++j) {
            auto it = m.emplace(skew_key, skew_key).first; // emplace element
            m.erase(it);                                   // remove  element
        }
        const auto now = std::chrono::steady_clock::now();
 
        std::cout << "Normal emplace   : runs for " << std::chrono::duration_cast<std::chrono::microseconds>(now-curr_tp).count() << " microseconds" << std::endl;
    }
 
 
#ifdef  FALSE_HINT
    auto it_after = m.end();  // m.begin();
#else
    constexpr unsigned even_existing_key = skew_key + (skew_key & 1); // even key, before which we want to insert the odd key
    auto it_after = m.find(even_existing_key);
#endif
 
    {
        const std::chrono::time_point<std::chrono::steady_clock> curr_tp = std::chrono::steady_clock::now();
        for (unsigned j = 0; j < loops; ++j) {
            auto it = m.emplace_hint(it_after, skew_key, skew_key); // emplace element with hint
            m.erase(it);                                            // remove  element
        }
        const auto now = std::chrono::steady_clock::now();
 
        std::cout << "With emplace_hint: runs for " << std::chrono::duration_cast<std::chrono::microseconds>(now-curr_tp).count() << " microseconds" << std::endl;
    }
    return 0;
}

Fdklsa (talk) 01:07, 17 January 2017 (PST)

It may be better to show when hints are used in code rather than test whether the standard library implements them. For example, I've seen hinted inserts used was for bulk appends of already-sorted sequences (so the hint was simply the end iterator). I could imagine it would be useful for bulk-inserting a sorted sequence in the middle too. Also, the example could use less verbosity, like the microbenchmark on std::reduce --Cubbi (talk)