c++ - 在集合的情况下使用 emplace_hint 的用例是什么？

Question

在集合的情况下使用 emplace_hint 的用例是什么？我给出了一个提示(下面程序中的 s.begin())，但是 emplace_hint 似乎没有注意到它。程序-

#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>

预期输出为 <alpha, epsilon, beta, delta, gamma>显然不是这样。

Answer 1

1. std::set 总是按照比较类型指定的顺序存储项目。这默认为 std::less，这意味着项目将默认始终升序排列。不管你暗示什么，集合保证维持秩序。

2. emplace_hint 旨在避免在您已经知道应该插入项目的位置时再次搜索集合。

一个非常简单的例子:

#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);
    }
}