Main Content

Expensive use of map instead of set

The key for a map is member of the object being inserted, resulting in redundant map key

Since R2024b

expand all in page

Description

This defect occurs when you use a member of an object as a key when inserting the object in a map container. Consider this code:

class Person {
public:
	std::string name;
	int age;
	double height;


	//...
};

void InsertPerson(std::map<std::string, Person> &map, const Person &person) {
	map[person.name] = person;   // Defect
}
The function InsertPerson() inserts an object of class Person and uses the member Person::name as the key. Because a member of the inserted value is used as the key, Polyspace® reports this defect. This checker applies to inappropriate use of std::map, std::multimap, std::unordered_multimap, and std::unordered_map.

Risk

Using a member of an object inserted in a map container as the key for that object results in redundant copies of same data, which is inefficient, especially if the key is expensive to copy. This practice can also indicate inappropriate choice of container.

Fix

To look up objects using a members of the object, use set containers such as std::set or std::unordered_set instead of map containers.

Performance improvements might vary based on the compiler, library implementation, and environment that you are using.

Examples

expand all

In this code, the container employeesByName contains objects of class Employee as value and uses Employee::name as keys. Because the value being inserted contains the key in addEmployee(), Polyspace reports a defect. 

#include <map>
#include <set>
#include <string>

struct Employee
{
	std::string name;
	std::string position;
};


static std::map<std::string, Employee> employeesByName;

void addEmployee(const Employee &employee)
{
	employeesByName[employee.name] = employee;   //Defect
}

bool hasEmployee(const std::string &name)
{
	return employeesByName.find(name) != employeesByName.end();
}

std::string getEmployeePosition(const std::string &name)
{
	return employeesByName[name].position;
}

This code maps Employee::name to an object of type Employee, which allows you to look up Employee objects using Employee::name, as demonstrated by hasEmployee() and getEmployeePosition(). However, using std::set instead of std::map allows for the same functionality without redundant keys.

Correction — Use std::set Instead

To look up objects by one of their members, use std::set. Define a custom comparator overload to compare Employee objects and use this comparator for the container.

#include <map>
#include <set>
#include <string>

struct Employee
{
	std::string name;
	std::string position;
};

bool operator<(const Employee &e, const std::string &k) {
	return e.name < k;
}
bool operator<(const std::string &k, const Employee &e) {
	return k < e.name;
}
bool operator<(const Employee &e1, const Employee &e2) {
	return e1.name < e2.name;
}


static std::set<Employee, std::less<>> employeesByName;

void addEmployee(const Employee &employee)
{
	employeesByName.insert(employee);    // No defect
}

bool hasEmployee(const std::string &name)
{
	return employeesByName.find(name) != employeesByName.end();
}

std::string getEmployeePosition(const std::string &name)
{
	auto it = employeesByName.find(name);
	if(it != employeesByName.end())
	{
		return it->position;
	}
	return {};
}

Result Information

Group: Performance
Language: C++
Default: Off
Command-Line Syntax: EXPENSIVE_USE_OF_MAP_INSTEAD_OF_SET
Impact: Low

Version History

Introduced in R2024b

See Also

Topics