CODEWITHSUNDEEP
c++c++11
Onkar N Mahajan
Onkar N Mahajan

Reputation: 437

what is the use case for using emplace_hint in the case of sets?

what is the use case for using emplace_hint in the case of sets ? I gave a hint (s.begin() in the program below) and yet, the emplace_hint seem to be paying no attention to it. Program - 

#include <iostream>
#include <string>
#include <set>

using namespace std;

void show(set<string>& s) {
    set<string>::iterator it = s.begin();

    cout << "<" << *it++;
    for (; it != s.end(); it++)
        cout << ", " << *it;
    cout << ">" << endl;
}


set<string>::iterator myEmplaceHint(set<string>::iterator hint_it, set<string> &s, string e) {

    set<string>::iterator ret_it, tmp_it;

    cout << "hint_it :" << *hint_it << endl;
    ret_it = s.emplace_hint(hint_it, e);
    return ret_it;
}


int main(int argc, char *argv[]){

    set <string> s = { "alpha", "beta", "gamma", "delta" };
    show(s);

    string str("epsilon"), retVal;
    retVal = *myEmplaceHint(s.begin(), s, str);
    cout << "retVal :" << retVal << endl;

    show(s);

    return 0;
}

$ make
g++ -g -Wall -o test test.cpp
$ ./test
<alpha, beta, delta, gamma>
hint_it :alpha
retVal :epsilon
<alpha, beta, delta, epsilon, gamma>

Expected the output to be <alpha, epsilon, beta, delta, gamma> which is clearly not the case.

Upvotes: 1

Views: 665

Answers (1)

Richard Hodges
Richard Hodges

Reputation: 69892

  1. std::set always stores items in the order specified by the comparison type. This defaults to std::less, which means that items will by default always be ascending order. It does not matter what you hint at, the set guarantees to maintain order.

  2. emplace_hint is designed to avoid searching the set again if you already know where the item should be inserted.

A very trivial example:

#include <set>
#include <cassert>

void ensure_present(std::set<int>& s, int v)
{
    // finding the upper bound is O(logN)
    auto i = s.upper_bound(v);
    if (i == std::end(s) || *i != v) {

        // this would be inefficient since we'd be performing another redundant 
        // O(logN) search for the insertion point
        // s.emplace(v);

        // since we already have the position close to were it should go, we
        // can avoid another search
        s.emplace_hint(i, v);
    }
}

Upvotes: 2

Related Questions