Expensive use of container's count method

The function member count() of a container is used for checking if a key is present, leading to inefficient code

Since R2021b

Description

This defect is raised when the function member count() of these containers is called for checking if a key is present:

std::multimap
std::multiset
std::unordered_multiset
std::unordered_multimap

When checking containment, you convert the output of the container's count() method to a bool, or compare it to either 0 or 1.

Risk

The count function of the preceding containers performs a linear search and finds all the instances of a key in the container. When checking if a key is present in a container, performing an exhaustive search for every instance of the key is unnecessary and inefficient.

Fix

To fix this defect, call the member find or contains function of a container when checking for containment. These functions stop searching for a key as soon as one instance of the key is found. These functions check containment more efficiently compared to the count function.

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

Examples

expand all

Inefficient Containment Check

#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <algorithm>
#include <string>

typedef std::string V;  
typedef std::string K;  


void conatins()
{
	std::string key;
	std::pair<const K, V> kv;

	
	std::multiset<V> ms;
	std::multimap<K, V> mm;
	std::unordered_multimap<K, V> umm;
	std::unordered_multiset<K> ums;
	
	//Check containment
	
	bool b_ms = (ms.count(key)==0);
	bool b_mm = (mm.count(key)==0);
	bool b_ums = (ums.count(key)==0);
	bool b_umm = (umm.count(key)==0);

}

In this example, Polyspace^® flags the use of the member count function to check containment in various containers. These count functions are inefficient because they continue searching for key even after the first instance is found.

Correction

To fix this defect, use the member find function to check for containment. For instance, use std::multimap::find instead of std::multimap::count. The find functions are more efficient because they stop searching as soon as the first instance of key is found.

#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <algorithm>
#include <string>

typedef std::string V; 
typedef std::string K; 

void conatins()
{
	std::string key;
	std::pair<const K, V> kv;

	
	std::multiset<V> ms;
	std::multimap<K, V> mm;
	std::unordered_multimap<K, V> umm;
	std::unordered_multiset<K> ums;
	
	//Check containment
	
	bool b_ms = (ms.find(key)== ms.end());
	bool b_mm = (mm.find(key)== mm.end());
	bool b_ums = (ums.find(key)==ums.end());
	bool b_umm = (umm.find(key)==umm.end());

}

Result Information

Group: Performance

Language: C++

Default: Off

Command-Line Syntax: EXPENSIVE_CONTAINER_COUNT

Impact: Medium

Version History

Introduced in R2021b