C++ map: std::map find, insert, erase and iterate

A C++ map, std::map<Key, T> from <map>, keeps its elements sorted by key and finds, inserts and erases in logarithmic time. To read a key without changing the map, call find, contains (C++20) or at, which throws std::out_of_range when the key is missing; m[key] inserts a value-initialized T when it is. To add a key only if it is absent, call try_emplace; to add or overwrite, insert_or_assign (both C++17). Loop with for (const auto& [key, value] : m). If you never need the keys in order, consider std::unordered_map.

This answer is written for C++17, which added try_emplace, insert_or_assign, extract, merge and the structured bindings in that loop. C++20 added contains and std::erase_if, C++23 added std::flat_map, and C++26 lets four more members take a std::string_view key when the comparator allows it.

The samples were built with four compilers on three standard libraries: MSVC 19.44 and Clang 19.1 on Microsoft’s STL (Windows x64), GCC 16.2 with libstdc++ and Clang 23.1 with libc++ (Compiler Explorer, Linux x86-64). Each output shown is what all four printed unless the text says otherwise, and every allocation count is from a release build. Since When’s C++17 table gives the first releases with try_emplace and structured bindings.

What changed: a key is added with m.insert(std::make_pair(key, value)) m.try_emplace(key, value) and tested with m.find(key) != m.end() m.contains(key).

since C++17

Create a std::map and loop over it

The running example is a settings map from names to values:

std::map<std::string, std::string> settings{
    {"retries", "3"}, {"port", "8080"}, {"host", "example.com"}};
settings["timeout"] = "30";             // adds a fourth key

for (const auto& [key, value] : settings)
    std::cout << key << " = " << value << '\n';

It printed the keys sorted, not in the order they were written:

host = example.com
port = 8080
retries = 3
timeout = 30

The order is std::less<Key> unless you pass a comparator for std::map as the third template argument. Each element is a std::pair<const Key, T>, the map’s value_type: a loop can change a value, never a key.

Look up a key: find, contains, at or operator[]

Every lookup but m[key] leaves the map as it is:

if (auto it = settings.find("port"); it != settings.end())
    std::cout << "port is " << it->second << '\n';
else
    std::cout << "no port set\n";

std::cout << "size before: " << settings.size() << '\n';
if (settings["user"].empty())       // a read that inserts "user"
    std::cout << "no user set\n";
std::cout << "size after: " << settings.size() << '\n';

On a map holding host and port, it printed:

port is 8080
size before: 2
no user set
size after: 3

The read through settings["user"] added "user" with an empty value, because operator[] is specified as return try_emplace(x).first->second; ([map.access]). That insertion is what makes it right for counting: ++counts[word] starts a new word at int(), which is 0.

For the same reason operator[] has no const overload: all four rejected settings["port"] through a const Settings& (both Clangs: no viable overloaded operator[] for type 'const Settings'). Use at there, and wherever a missing key is a bug. Its exception’s what() is each library’s own (Microsoft’s invalid map<K, T> key, libstdc++’s map::at, libc++’s map::at: key not found), so catch the type. contains needs C++20: in C++17 mode (-std=c++17, /std:c++17) all four reject it (GCC: has no member named 'contains').

lower_bound and upper_bound find the nearest key, the lookup an ordered map is for:

const std::map<int, std::string> ports{
    {80, "http"}, {443, "https"}, {8080, "proxy"}};

auto at_or_after = ports.lower_bound(443);  // first key >= 443
auto after = ports.upper_bound(443);        // first key > 443
auto nearest_up = ports.lower_bound(100);   // 443: no 100, next up
auto none = ports.lower_bound(9000);        // ports.end()

It printed:

443 8080 443 end

equal_range(443) returned the same two iterators as the first two calls, on all four.

Insert or update: try_emplace, insert_or_assign, emplace, insert or operator[]

To add a key only if it is absent, call try_emplace; to add it or overwrite its value, call insert_or_assign. Both are C++17 (N4279) and take the key and the value as separate arguments.

Each way to add was run on a map holding port, once with a missing key and once with port. The key k is a const char*, the type a string literal decays to, and the mapped type logs its constructions and assignments.

The iterator points to the element with that key, new or old. Behind the same false, the calls did different work on the three libraries, in C++17 mode: emplace and the make_pair insert built a node and freed it, insert({k, v}) built a pair and destroyed it, and try_emplace touched nothing.

emplace is allowed to: the element “may be constructed even if there already is an element with the key in the container, in which case the newly constructed element will be destroyed immediately” (cppreference on std::map::emplace). With a move-only value, that decides whether your object survives:

auto conn = std::make_unique<Connection>("db-2");
pool.emplace("db", std::move(conn));        // "db" is taken
// ...
conn = std::make_unique<Connection>("db-3");
pool.emplace(key, std::move(conn));         // key: a std::string
// ...
conn = std::make_unique<Connection>("db-4");
pool.try_emplace("db", std::move(conn));    // "db" is taken

Building nothing for a std::string key is each library’s optimization, not a guarantee, and it held here for a two-argument emplace on a map with the default allocator. On GCC 16.2’s libstdc++, the same call built the element and took conn under -std=c++14, or on a map with another allocator; Microsoft’s STL and libc++ kept it in both cases.

std::move(conn) moved nothing by itself (what std::move really does): the call decides. The one call guaranteed to leave its arguments alone when the key exists is try_emplace, which then has “no effect” ([map.modifiers]).

m[k] = v also needs a default constructor for T; the other calls do not. With a Port type that has none, try_emplace, insert_or_assign and emplace built on all four, and ports["http"] = Port(80) failed on all four inside the library’s headers rather than on that line (MSVC: error C2512: 'Port::Port': no appropriate default constructor available).

Erase: by key, in a loop, or by condition

std::map<std::string, int> counts{{"host", 1}, {"port", 4},
                                  {"retries", 0}, {"timeout", 2},
                                  {"user", 0}};
int& port = counts.at("port");      // a reference to one element

std::cout << counts.erase("retries") << '\n';   // 1: erased
std::cout << counts.erase("retries") << '\n';   // 0: was not there

for (auto it = counts.begin(); it != counts.end();) {
    if (it->second == 0)
        it = counts.erase(it);      // returns the next element
    else
        ++it;
}
// ...
std::cout << "port is still " << port << '\n';

It printed the two results, the elements left, and port:

1
0
host 1
port 4
timeout 2
port is still 4

it = counts.erase(it) is the loop idiom because erasing invalidates only iterators and references to the erased elements ([associative.reqmts]): the old it is gone, the returned one is valid, and port still read 4. In C++20, std::erase_if writes that loop for you:

auto erased = std::erase_if(counts, [](const auto& item) {
    return item.second == 0;
});                                 // C++20

On the same map it returned 2 and left the same three elements. In C++17 mode all four reject it (Clang: no member named 'erase_if' in namespace 'std').

The loop that copies every element

for (const std::pair<std::string, int>& item : counts) compiles, and copies every element. The element type is std::pair<const std::string, int>, so the reference binds to a temporary converted from it. A key type that counts its copies showed it, over three elements:

for (const std::pair<Word, int>& item : counts)    // not the type
    total += item.second;
// ...
for (const auto& [word, n] : counts)
    total += n;
// ...
for (auto [word, n] : counts)       // a copy of each element
    total += n;

The five loops (two left out above) printed:

const std::pair<Word, int>&: 3 copies
const auto&: 0 copies
const auto& [word, n]: 0 copies
const std::pair<const Word, int>&: 0 copies
auto [word, n]: 3 copies

Write const auto& or const auto& [key, value]; without the &, structured bindings copy each element too. GCC and both Clangs warn about the first loop at -Wall -Wextra (-Wrange-loop-construct: the loop variable “binds to a temporary”); MSVC at /W4 said nothing.

The clang-tidy 19.1.5 bundled with Visual Studio reports it with performance-implicit-conversion-in-loop: “the type of the loop variable ‘item’ is different from the one returned by the iterator and generates an implicit conversion”. In the same file, readability-container-contains reported counts.count("port") > 0 (“use ‘contains’ to check for membership”) but not counts.find("host") != counts.end(), which clang-tidy trunk reports against libstdc++ and libc++. clang-tidy and the other analyzers are on Toolchain.

Look up by std::string_view without building a string

With the default comparator, std::less<std::string>, find takes only a const std::string&. A std::string_view does not compile there (Clang: no matching member function for call to 'find'), and find(std::string(sv)) copies the key into a new string. Declare the map with std::less<>, a transparent comparator that compares a std::string with a view directly:

std::map<std::string, std::string, std::less<>> settings{
    {std::string(key), "300"}};
// ...
auto a = plain.find(std::string(key));  // builds a std::string
// ...
auto b = settings.find(key);            // compares in place
auto n = settings.count(key);
auto c = settings.lower_bound(key);

key is a 40-character std::string_view cut from a config line, and plain the same map with the default comparator. In release builds, plain.find(std::string(key)) made 1 allocation and the three calls on settings made none, on all three libraries. The members that take the view, with std::less<>:

• C++14 (N3657): find, count, lower_bound, upper_bound, equal_range.
• C++20: contains.
• C++23 (P2077R3): erase, extract; libc++ 23.1 lacks both, even in C++26 mode.
• C++26 (P2363R5): operator[], at, try_emplace, insert_or_assign; of the libraries tested, only GCC 16.2’s libstdc++ accepts them, and Microsoft’s STL and libc++ 23.1 reject settings[key] in C++26 mode.

std::unordered_map takes a view from C++20, given a transparent equality such as std::equal_to<> and a transparent hash. The standard library has none for std::string, so you write it:

struct StringHash {             // hashes std::string and string_view
    using is_transparent = void;
    std::size_t operator()(std::string_view s) const noexcept {
        return std::hash<std::string_view>{}(s);
    }
};

using Settings = std::unordered_map<std::string, std::string,
                                    StringHash, std::equal_to<>>;

With it, find(key) made no allocation on all three libraries; in C++17 mode it does not compile.

Change a key, or move elements to another map

A key is const inside the map, so to change one, take its node out. extract (C++17) returns a node handle whose key() can be assigned, and insert puts it back:

auto node = settings.extract("hostname");   // the node, unlinked
node.key() = "host";        // a node's key can be changed
settings.insert(std::move(node));
// ...
settings.merge(defaults);   // "port" stays in defaults

The rename and the merge made 0 allocations on all three libraries; cppreference calls extract “the only way to change a key of a map element without reallocation”. merge moved retries and timeout out of defaults and left port=80 there, because settings already had a port. extract of a key the map lacks returns an empty node handle.

std::map, std::unordered_map or std::flat_map

A std::flat_map (header <flat_map>) keeps the keys in one sorted container and the values in another, std::vector by default, with no nodes; [flat.map.overview] exempts it from the associative containers’ invalidation guarantees.

A program inserted the same 1,000 int keys, in a scrambled order, into each container, and a replaced operator new counted the allocations. For std::flat_map:

std::flat_map<int, int> m;                  // C++23
for (int i = 0; i < 1000; ++i) m.emplace(key_at(i), i);

A std::map allocated once per element on all three libraries; on libstdc++ and libc++, a std::flat_map allocated 22 times for the same 1,000 keys. Microsoft’s STL in MSVC 19.44 has no <flat_map> (fatal error C1083: Cannot open include file: 'flat_map': No such file or directory); Since When’s C++23 table lists it from libstdc++ 15.1, libc++ 20 and Visual Studio 2026 18.6.

Which call for which job

More answers about the library’s containers and types are in Standard library.