What Is Heterogeneous Lookup In Associative Containers In C++?

Containers are data storage arrays in modern C++ and they are very useful to iterate and search data with their amazing methods and properties. The C++ Standard Library defines four different main container types and one of them is associative containers such as std::map, and std::set. These class types allow us to use the look-up method “find()” by a value based on a value of that type. C++14 introduced the “Heterogeneous Lookup In Associative Containers” feature that allows the lookup to be done via an arbitrary type, so long as the comparison operator can compare that type with the actual key type. In this post, we explain containers, associative containers, and heterogeneous lookup in associative containers.

What is a container in C++?

Containers are data storage arrays in modern C++, and they are very useful to iterate and search data with their amazing methods and properties. In C++, there are four main types of containers:

• Sequence Containers (vectors, arrays, …)
• Associative Containers (maps, sets, …)
• Unordered Associative Containers (unordered_set, unordered_map, …)
• Container Adapters (stack, queue, priority_queue)

If you want to know more about containers, here are more details about their types:

What Are The Amazing Containers In Modern C++?

What are associative containers in C++?

Associative Containers are class templates of container types that can be used to implement sorted data structures where can be quickly searched. They are sorted by keys. We can say they are about O(log n) complexity data structures.

The associative containers are:

• std::map : a class template for the collection of key-value pairs, its keys are unique and it is sorted by keys
• std::set : a class template for the collection of unique keys, it is sorted by keys 
• multiset : a class template for the collection of keys, it is sorted by keys
• multimap : a class template for the collection of key-value pairs, it is sorted by keys 

What is heterogeneous lookup in associative containers in C++?

The C++ Standard Library defines 4 associative container types. These class types allow us to use the look-up method find() by a value based on a value of that type. C++14 introduced the “Heterogeneous Lookup In Associative Containers” feature that allows the lookup to be done by an arbitrary type, so the comparison operator can compare types with the actual key type.

The heterogeneous lookup in associative containers gives us to use std::map, std::set, and other associative containers.

In example, let’s have some strings and have some values in a std::map (which is a associative container),

we can use find method of map as shown below:

In the heterogeneous lookup we can use less<> or other features.

Is there a full example about heterogeneous lookup in associative containers in C++?

When we want to do heterogeneous lookup, all we have to do is to use std::less<> or other heterogeneous lookup features and we should implement correct comparison methods. Here is an example,

The interesting thing is, it is straightforward to enable and we can use find method like so:

Note that here m is an iterator and you find by using const char* and you can find by string_view .

Is there a full example about heterogeneous lookup in associative containers in C++?

Here is a full example about how we can use std::less<> with a std::map to use find method in the heterogeneous lookup in associative containers,

You can also try your implementation and use the ideas from this video.

In C++20 through there are more improvements about containers and heterogeneous lookup in other container types. We will have more examples about these in the next posts later.

C++ Builder is the easiest and fastest C and C++ compiler and IDE for building simple or professional applications on the Windows, MacOS, iOS & Android operating systems. It is also easy for beginners to learn with its wide range of samples, tutorials, help files, and LSP support for code. RAD Studio’s C++ Builder version comes with the award-winning VCL framework for high-performance native Windows apps and the powerful FireMonkey (FMX) framework for cross-platform UIs.

There is a free C++ Builder Community Edition for students, beginners, and startups; it can be downloaded from here. For professional developers, there are Professional, Architect, or Enterprise versions of C++ Builder and there is a trial version you can download from here.