Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/container/set/emplace hint"

From cppreference.com
< cpp‎ | container‎ | set
m (langlinks)
m (templatized.)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
{{cpp/container/set/title | emplace_hint}}
+
{{include page|cpp/container/emplace_hint|set}}
−
{{cpp/container/set/navbar}}
+
−
{{dcl begin}}
+
−
{{dcl | since=c++11 |
+
−
template <class... Args>
+
−
iterator emplace_hint( const_iterator hint, Args&&... args );
+
−
}}
+
−
{{dcl end}}
+
−
 
+
−
Inserts a new element into the container as close as possible to the position just before {{tt|hint}}. The element is constructed in-place, i.e. no copy or move operations are performed.
+
−
 
+
−
The constructor of the element is called with exactly the same arguments as supplied to the function, forwarded with {{c|std::forward<Args>(args)...}}.
+
−
 
+
−
{{cpp/container/note_iterator_invalidation|set|emplace_hint}}
+
−
 
+
−
===Parameters===
+
−
{{par begin}}
+
−
{{par | hint | iterator to the position before which the new element will be inserted}}
+
−
{{par | args | arguments to forward to the constructor of the element}}
+
−
{{par end}}
+
−
 
+
−
===Return value===
+
−
Returns an iterator to the newly inserted element.
+
−
 
+
−
If the insertion failed because the element already exists, returns an iterator to the already existing element with the equivalent key.
+
−
 
+
−
===Exceptions===
+
−
If an exception is thrown by any operation, this function has no effect (strong exception guarantee).
+
−
 
+
−
===Complexity===
+
−
Logarithmic in the size of the container in general, but amortized constant if the new element is inserted just before {{tt|hint}}.
+
−
 
+
−
===Example===
+
−
{{example
+
−
|
+
−
| code=
+
−
#include <set>
+
−
#include <chrono>
+
−
#include <iostream>
+
−
#include <iomanip>
+
−
#include <functional>
+
−
 
+
−
const int nof_operations = 100500;
+
−
 
+
−
int set_emplace() {
+
−
  std::set<int> set;
+
−
  for(int i = 0; i < nof_operations; ++i) {
+
−
    set.emplace(i);
+
−
  }
+
−
  return set.size();
+
−
}
+
−
 
+
−
int set_emplace_hint() {
+
−
  std::set<int> set;
+
−
  auto it = set.begin();
+
−
  for(int i = 0; i < nof_operations; ++i) {
+
−
    set.emplace_hint(it, i);
+
−
    it = set.end();
+
−
  }
+
−
  return set.size();
+
−
}
+
−
 
+
−
int set_emplace_hint_wrong() {
+
−
  std::set<int> set;
+
−
  auto it = set.begin();
+
−
  for(int i = nof_operations; i > 0; --i) {
+
−
    set.emplace_hint(it, i);
+
−
    it = set.end();
+
−
  }
+
−
  return set.size();
+
−
}
+
−
 
+
−
int set_emplace_hint_corrected() {
+
−
  std::set<int> set;
+
−
  auto it = set.begin();
+
−
  for(int i = nof_operations; i > 0; --i) {
+
−
    set.emplace_hint(it, i);
+
−
    it = set.begin();
+
−
  }
+
−
  return set.size();
+
−
}
+
−
 
+
−
int set_emplace_hint_closest() {
+
−
  std::set<int> set;
+
−
  auto it = set.begin();
+
−
  for(int i = 0; i < nof_operations; ++i) {
+
−
    it = set.emplace_hint(it, i);
+
−
  }
+
−
  return set.size();
+
−
}
+
−
 
+
−
void timeit(std::function<int()> set_test, std::string what = "") {
+
−
  auto start = std::chrono::system_clock::now();
+
−
  int setsize = set_test();
+
−
  auto stop = std::chrono::system_clock::now();
+
−
  std::chrono::duration<double, std::milli> time = stop - start;
+
−
  if (what.size() > 0 && setsize > 0) {
+
−
    std::cout << std::fixed << std::setprecision(2) << std::setw(5)
+
−
              << time.count() << "  ms for " << what << '\n';
+
−
  }
+
−
}
+
−
 
+
−
int main() {
+
−
  timeit(set_emplace); // stack warmup
+
−
  timeit(set_emplace, "plain emplace");
+
−
  timeit(set_emplace_hint, "emplace with correct hint");
+
−
  timeit(set_emplace_hint_wrong, "emplace with wrong hint");
+
−
  timeit(set_emplace_hint_corrected, "corrected emplace");
+
−
  timeit(set_emplace_hint_closest, "emplace using returned iterator");
+
−
}
+
−
|p=true
+
−
| output=
+
−
18.96  ms for plain emplace
+
−
7.95  ms for emplace with correct hint
+
−
19.39  ms for emplace with wrong hint
+
−
8.39  ms for corrected emplace
+
−
7.90  ms for emplace using returned iterator
+
−
}}
+
−
 
+
−
===See also===
+
−
{{dsc begin}}
+
−
{{dsc inc | cpp/container/dsc emplace |set}}
+
−
{{dsc inc | cpp/container/dsc insert |set}}
+
−
{{dsc end}}
+
  
 
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}
 
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}

Latest revision as of 08:00, 30 January 2024

[edit template]
 
C++
 
Containers library
 
std::set
Member functions
Non-member functions
(until C++20)(until C++20)(until C++20)(until C++20)(until C++20)
Deduction guides(C++17)
 
template< class... Args >
iterator emplace_hint( const_iterator hint, Args&&... args );
 (since C++11)

Inserts a new element into the container as close as possible to the position just before hint.

The constructors of the key and mapped value are called with exactly the same arguments as supplied to the function, forwarded with std::forward<Args>(args)....

No iterators or references are invalidated.

Contents

[edit] Parameters

hint - iterator to the position before which the new element will be inserted
args - arguments to forward to the constructor of the element

[edit] Return value

An iterator to the inserted element, or to the element that prevented the insertion.

[edit] Exceptions

If an exception is thrown for any reason, this function has no effect (strong exception safety guarantee).

[edit] Complexity

Logarithmic in the size of the container in general, but amortized constant if the new element is inserted just before hint.

[edit] Example

Run this code
#include <chrono>
#include <cstddef>
#include <functional>
#include <iomanip>
#include <iostream>
#include <set>
 
const int n_operations = 100'500'0;
 
std::size_t set_emplace()
{
    std::set<int> set;
    for (int i = 0; i < n_operations; ++i)
        set.emplace(i);
    return set.size();
}
 
std::size_t set_emplace_hint()
{
    std::set<int> set;
    auto it = set.begin();
    for (int i = 0; i < n_operations; ++i)
    {
        set.emplace_hint(it, i);
        it = set.end();
    }
    return set.size();
}
 
std::size_t set_emplace_hint_wrong()
{
    std::set<int> set;
    auto it = set.begin();
    for (int i = n_operations; i > 0; --i)
    {
        set.emplace_hint(it, i);
        it = set.end();
    }
    return set.size();
}
 
std::size_t set_emplace_hint_corrected()
{
    std::set<int> set;
    auto it = set.begin();
    for (int i = n_operations; i > 0; --i)
    {
        set.emplace_hint(it, i);
        it = set.begin();
    }
    return set.size();
}
 
std::size_t set_emplace_hint_closest()
{
    std::set<int> set;
    auto it = set.begin();
    for (int i = 0; i < n_operations; ++i)
        it = set.emplace_hint(it, i);
    return set.size();
}
 
double time_it(std::function<std::size_t()> set_test,
               const char* what = nullptr,
               double ratio = 0.0)
{
    const auto start = std::chrono::system_clock::now();
    const std::size_t setsize = set_test();
    const auto stop = std::chrono::system_clock::now();
    const std::chrono::duration<double, std::milli> time = stop - start;
    if (what != nullptr && setsize > 0)
        std::cout << std::setw(8) << time << " for " << what << " (ratio: "
                  << (ratio == 0.0 ? 1.0 : ratio / time.count()) << ")\n";
    return time.count();
}
 
int main()
{
    std::cout << std::fixed << std::setprecision(2);
    time_it(set_emplace); // cache warmup
    const auto x = time_it(set_emplace, "plain emplace");
    time_it(set_emplace_hint, "emplace with correct hint", x);
    time_it(set_emplace_hint_wrong, "emplace with wrong hint", x);
    time_it(set_emplace_hint_corrected, "corrected emplace", x);
    time_it(set_emplace_hint_closest, "emplace using returned iterator", x);
}

Possible output: 

392.25ms for plain emplace (ratio: 1.00)
 97.15ms for emplace with correct hint (ratio: 4.04)
387.52ms for emplace with wrong hint (ratio: 1.01)
 84.80ms for corrected emplace (ratio: 4.63)
 83.67ms for emplace using returned iterator (ratio: 4.69)

[edit] See also

(C++11)
 constructs element in-place
(public member function) [edit]
inserts elements or nodes(since C++17)
(public member function) [edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/container/set/emplace_hint&oldid=169407"