|
|
| (One intermediate revision by one user not shown) |
| Line 1: |
Line 1: |
| − | {{cpp/container/{{{1|}}}/title|emplace_hint}}
| |
| − | {{cpp/container/{{{1|}}}/navbar}}
| |
| − | {{ddcl|since={{cpp/container/if flat|{{{1|}}}|c++23|c++11}}|
| |
| − | template< class... Args >
| |
| − | iterator emplace_hint( const_iterator hint, Args&&... args );
| |
| − | }}
| |
| | | | |
| − | {{cpp/container/if ord|{{{1|}}}
| |
| − | |Inserts a new element into the container as close as possible to the position just before hint.
| |
| − | |Inserts a new element into the container, using {{c|hint}} as a suggestion where the element should go.
| |
| − | }}
| |
| − |
| |
| − | {{cpp/container/if set|{{{1|}}}
| |
| − | |The constructors of the key and mapped value are called with exactly the same arguments as supplied to the function, forwarded with {{c|std::forward<Args>(args)...}}.
| |
| − | |The constructor of the element type ({{tt|value_type}}, that is, {{c|std::pair<const Key, T>}}) is called with exactly the same arguments as supplied to the function, forwarded with {{c|std::forward<Args>(args)...}}.
| |
| − | }}
| |
| − |
| |
| − | {{cpp/container/note_iterator_invalidation|{{{1|}}}|emplace_hint}}
| |
| − |
| |
| − | ===Parameters===
| |
| − | {{par begin}}
| |
| − | {{cpp/container/if ord|{{{1|}}}
| |
| − | |{{par|hint|iterator to the position before which the new element will be inserted}}
| |
| − | |{{par|hint|iterator, used as a suggestion as to where to insert the new element}}
| |
| − | }}
| |
| − | {{par|args|arguments to forward to the constructor of the element}}
| |
| − | {{par end}}
| |
| − |
| |
| − | ===Return value===
| |
| − | Returns an iterator to the newly inserted element. {{cpp/container/if uniq|{{{1|set}}}|
| |
| − | If the insertion failed because the element already exists, returns an iterator to the already existing element with the equivalent key.}}
| |
| − |
| |
| − | ===Exceptions===
| |
| − | <!--{{cpp/container/exceptions|{{{1}}}|emplace_hint}}-->
| |
| − | {{cpp/strong exception safety guarantee}}
| |
| − |
| |
| − | ===Complexity===
| |
| − | <!--{{cpp/container/complexity|{{{1}}}|emplace_hint}}-->
| |
| − | {{cpp/container/if flat|{{{1}}}
| |
| − | |<!--
| |
| − | Logarithmic in the size of the container in general, but amortized constant if the new element is inserted just before {{c|hint}}, plus complexity of emplace into underlying container(s) (typically linear).
| |
| − | -->{{todo}}
| |
| − | |{{cpp/container/if ord|{{{1|}}}
| |
| − | |Logarithmic in the size of the container in general, but amortized constant if the new element is inserted just before {{c|hint}}.
| |
| − | |Amortized constant on average, worst case linear in the size of the container.
| |
| − | }}
| |
| − | }}
| |
| − |
| |
| − | ===Example===
| |
| − | {{#vardefine:cont|{{{1|map}}}}}
| |
| − | {{#switch:{{#var:cont}}
| |
| − | |set|unordered_set|flat_set=
| |
| − | {{example
| |
| − | |code=
| |
| − | #include <chrono>
| |
| − | #include <cstddef>
| |
| − | #include <functional>
| |
| − | #include <iomanip>
| |
| − | #include <iostream>
| |
| − | #include <{{cpp/container/get header|{{#var:cont}}}}>
| |
| − |
| |
| − | const int n_operations = 100'500'0;
| |
| − |
| |
| − | std::size_t set_emplace()
| |
| − | {
| |
| − | std::{{#var:cont}}<int> set;
| |
| − | for (int i = 0; i < n_operations; ++i)
| |
| − | set.emplace(i);
| |
| − | return set.size();
| |
| − | }
| |
| − |
| |
| − | std::size_t set_emplace_hint()
| |
| − | {
| |
| − | std::{{#var:cont}}<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::{{#var:cont}}<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::{{#var:cont}}<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::{{#var:cont}}<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);
| |
| − | }
| |
| − | |p=true
| |
| − | |output=
| |
| − | {{#switch:{{#var:cont}}
| |
| − | |set=
| |
| − | 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)
| |
| − | |unordered_set=
| |
| − | 146.88ms for plain emplace (ratio: 1.00)
| |
| − | 168.20ms for emplace with correct hint (ratio: 0.87)
| |
| − | 168.78ms for emplace with wrong hint (ratio: 0.87)
| |
| − | 166.58ms for corrected emplace (ratio: 0.88)
| |
| − | 168.27ms for emplace using returned iterator (ratio: 0.87)
| |
| − | |flat_set=
| |
| − | ...TODO...
| |
| − | }}
| |
| − | }}
| |
| − | |map|unordered_map|flat_map=
| |
| − | {{example
| |
| − | |code=
| |
| − | #include <chrono>
| |
| − | #include <cstddef>
| |
| − | #include <functional>
| |
| − | #include <iomanip>
| |
| − | #include <iostream>
| |
| − | #include <{{cpp/container/get header|{{#var:cont}}}}>
| |
| − |
| |
| − | const int n_operations = 100'500'0;
| |
| − |
| |
| − | std::size_t map_emplace()
| |
| − | {
| |
| − | std::{{#var:cont}}<int, char> map;
| |
| − | for (int i = 0; i < n_operations; ++i)
| |
| − | map.emplace(i, 'a');
| |
| − | return map.size();
| |
| − | }
| |
| − |
| |
| − | std::size_t map_emplace_hint()
| |
| − | {
| |
| − | std::{{#var:cont}}<int, char> map;
| |
| − | auto it = map.begin();
| |
| − | for (int i = 0; i < n_operations; ++i)
| |
| − | {
| |
| − | map.emplace_hint(it, i, 'b');
| |
| − | it = map.end();
| |
| − | }
| |
| − | return map.size();
| |
| − | }
| |
| − |
| |
| − | std::size_t map_emplace_hint_wrong()
| |
| − | {
| |
| − | std::{{#var:cont}}<int, char> map;
| |
| − | auto it = map.begin();
| |
| − | for (int i = n_operations; i > 0; --i)
| |
| − | {
| |
| − | map.emplace_hint(it, i, 'c');
| |
| − | it = map.end();
| |
| − | }
| |
| − | return map.size();
| |
| − | }
| |
| − |
| |
| − | std::size_t map_emplace_hint_corrected()
| |
| − | {
| |
| − | std::{{#var:cont}}<int, char> map;
| |
| − | auto it = map.begin();
| |
| − | for (int i = n_operations; i > 0; --i)
| |
| − | {
| |
| − | map.emplace_hint(it, i, 'd');
| |
| − | it = map.begin();
| |
| − | }
| |
| − | return map.size();
| |
| − | }
| |
| − |
| |
| − | std::size_t map_emplace_hint_closest()
| |
| − | {
| |
| − | std::{{#var:cont}}<int, char> map;
| |
| − | auto it = map.begin();
| |
| − | for (int i = 0; i < n_operations; ++i)
| |
| − | it = map.emplace_hint(it, i, 'e');
| |
| − | return map.size();
| |
| − | }
| |
| − |
| |
| − | double time_it(std::function<std::size_t()> map_test,
| |
| − | std::string what = "", double ratio = 0.0)
| |
| − | {
| |
| − | const auto start = std::chrono::system_clock::now();
| |
| − | const std::size_t map_size = map_test();
| |
| − | const auto stop = std::chrono::system_clock::now();
| |
| − | std::chrono::duration<double, std::milli> time = stop - start;
| |
| − | if (what.size() && map_size)
| |
| − | 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(map_emplace); // cache warmup
| |
| − | const auto x = time_it(map_emplace, "plain emplace");
| |
| − | time_it(map_emplace_hint, "emplace with correct hint", x);
| |
| − | time_it(map_emplace_hint_wrong, "emplace with wrong hint", x);
| |
| − | time_it(map_emplace_hint_corrected, "corrected emplace", x);
| |
| − | time_it(map_emplace_hint_closest, "emplace using returned iterator", x);
| |
| − | }
| |
| − | |p=true
| |
| − | |output=
| |
| − | {{#switch:{{#var:cont}}
| |
| − | |map=
| |
| − | 365.08ms for plain emplace (ratio: 1.00)
| |
| − | 96.54ms for emplace with correct hint (ratio: 3.78)
| |
| − | 409.40ms for emplace with wrong hint (ratio: 0.89)
| |
| − | 85.57ms for corrected emplace (ratio: 4.27)
| |
| − | 84.31ms for emplace using returned iterator (ratio: 4.33)
| |
| − | |unordered_map=
| |
| − | 143.48ms for plain emplace (ratio: 1.00)
| |
| − | 164.78ms for emplace with correct hint (ratio: 0.87)
| |
| − | 171.22ms for emplace with wrong hint (ratio: 0.84)
| |
| − | 166.55ms for corrected emplace (ratio: 0.86)
| |
| − | 167.41ms for emplace using returned iterator (ratio: 0.86)
| |
| − | |flat_map=
| |
| − | ...TODO...
| |
| − | }}
| |
| − | }}
| |
| − | |{{example}}
| |
| − | }}
| |
| − |
| |
| − | ===See also===
| |
| − | {{dsc begin}}
| |
| − | {{dsc inc|cpp/container/dsc emplace|{{{1|}}}}}
| |
| − | {{dsc inc|cpp/container/dsc insert|{{{1|}}}}}
| |
| − | {{dsc end}}
| |
| − |
| |
| − | {{langlinks|de|es|fr|it|ja|pt|ru|zh}}
| |
