View source for Talk:cpp/container/map/emplace hint

=== If the hint is correct, {{tt|emplace_hint}} is fast ===

Here's an example ([http://melpon.org/wandbox/permlink/98BhVCZ6bv5WjfWa link]). (If you change the code by uncommenting {{tt|#define FALSE_HINT}}, you can see what happens if the hint is wrong.)

{{example
 | 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;
}
}}
[[User:Fdklsa|Fdklsa]] ([[User talk: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 {{lc|std::reduce}} --[[User:Cubbi|Cubbi]] ([[User talk:Cubbi|talk]])