Expensive use of a standard algorithm when a more efficient method exists

Functions from the algorithm library are misused with inappropriate inputs, resulting in inefficient code

Since R2021b

expand all in page

Description

Polyspace® reports a defect when you misuse functions in the algorithm library with a container, which results in inefficient code. You might be recalculating known or constant information about the container or using a function that is inappropriate for the container. The scenarios that trigger this defect include:

  • Running a search by calling functions such as std::find, std::equal_range, std::upper_bound, std::binary_search, and std::lower_bound with associative containers such as std::set, std::map, std::multiset, and std::mutimap.

  • Checking for the presence of a certain key in a container by calling std::count. That is, you convert the output of std::count to a bool or compare the output to either 0 or 1.

  • Checking for a sorted associative container by calling std::is_sorted.

  • Calculating the size of an associative container by calling std::distance.

  • Searching for consecutive equal elements in unique-value containers such as std::set or std::map by calling std::adjacent_find.

  • Passing expensive functors by value to standard functions.

Risk

Misusing the functions from the algorithm library might result in inefficient code or unexpected behavior.

  • Searching associative containers by using linear search functions, such as std::find and std::binary_search, is inefficient.

  • When checking for a certain key in a container, performing an exhaustive search for every instance of the key by calling std::count is unnecessary and inefficient.

  • If an associative container is already sorted, calling std::is_sorted is unnecessary. If the associative container is not sorted, the output of std::is_sorted might be indeterminate, resulting in unexpected behavior.

  • Calculating the size of an associative container by calling its size method is more efficient than using the std::distance function.

  • Calling std::adjacent_find with unique-value containers such as std::set or std::map always results in end(). Because the output is constant, the call is unnecessary.

  • If you pass a functor to a standard algorithm function, it is always copied. If the functor is expensive, this copy operation makes your code expensive and inefficient.

Fix

To fix this defect, refactor your code to use the standard algorithm functions more efficiently.

  • When searching in associative containers, avoid using std functions. If possible, use the search method of the container, such as std::set::find.

  • When checking for the presence of a certain key, call the find or contains (C++20) method of the container. For containers that do not implement these methods, use std::find instead of std::count.

  • Avoid using std::is_sorted or std::adjacent_find with associative containers.

  • To check the size of an associative container, use the size method of the container. Avoid using std::distance to calculate size.

  • Avoid passing expensive-to-copy functors to std functions. Instead, create a wrapper functor that contains a reference to the original functor and pass the wrapper to standard algorithm functions.

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

Examples

expand all

In this example, Polyspace flags the use of std functions, such as std::find or std::count, with associative containers when the containers have equivalent find or count methods. Using these std functions with containers that do not have equivalent methods is not reported as a defect. For instance,

  • Polyspace flags the use of std::find with a set because std::set::find is more efficient.

  • Polyspace does not flag the use of std::find with a vector because the class vector has no find method.

#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <array>
#include <set>
#include <map>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <string>

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

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


	std::set<V> s;
	std::multiset<V> ms;
	std::map<K, V> m;
	std::multimap<K, V> mm;
	std::vector<V> v;
	std::list<V> l;
	std::deque<V> d;
	std::string str;
	std::unordered_map<K, V> um;

	
	std::find(s.begin(), s.end(), key);
	std::equal_range(m.begin(), m.end(), kv);
	std::lower_bound(mm.begin(), mm.end(), kv);
	std::upper_bound(ms.begin(), ms.end(), key);
	std::count(um.begin(), um.end(), kv);
	if(std::binary_search(s.begin(), s.end(), key)==0){
          //....
      }

	std::find(v.begin(),v.end(), key); //Compliant
	std::equal_range(l.begin(),l.end(), key); //Compliant
	std::lower_bound(d.begin(),d.end(), key); //Compliant
	

}
Correction — Use the Methods of Containers

To fix this defect, use the methods of a container instead of the std functions. For instance, when using a set, use std::set::find instead of std::binary_search. It might be necessary to refactor your code to use the lookup methods of the container.

#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <array>
#include <set>
#include <map>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <string>

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


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

	std::unordered_map<K, V> um;
	std::set<V> s;
	std::multiset<V> ms;
	std::map<K, V> m;
	std::multimap<K, V> mm;
	std::vector<V> v;
	std::list<V> l;
	std::deque<V> d;
	std::string str;

	
	s.find(key);          
	m.equal_range(key);   
	mm.lower_bound(key);     
	ms.upper_bound(key);    
      if(s.find(key)==s.end()){          
          //....
      }
      um.count(key);//Compliant


}

In this example, Polyspace flags the use of std::count to check if a container contains a particular member. Using the find method of the container or the std::find function is more efficient when checking containment.

Using std::count to count instances of a member does not cause a defect if the container does not have an equivalent member. For instance, Polyspace does not report a defect when you use std::count to check if v contains two instances of the string key.

#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <array>
#include <set>
#include <map>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <string>

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


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

	std::set<V> s;
	std::multiset<V> ms;
	std::vector<V> v;
	std::unordered_map<K, V> um;
	
	//Check containment
	bool b_v = std::count(v.begin(), v.end(), key); 
	bool b_um = std::count(um.begin(), um.end(), kv);
	bool b_s = std::count(s.begin(), s.end(), key);
	bool b_ms = std::count(ms.begin(), ms.end(), key);
	
	if(std::count(v.begin(), v.end(), key)==2){ //Compliant
		//...
	}

}
Correction — Use find to Check Containment

To fix these defects, use the find method of a container, such as std::set::find, to check for containment. When checking containment in a container that does not have a find method, use std::find.

#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <array>
#include <set>
#include <map>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <string>

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


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

	std::set<V> s;
	std::multiset<V> ms;
	std::vector<V> v;
	std::unordered_map<K, V> um;
	
	//Check containment
	bool b_v = (std::find(v.begin(), v.end(), key)!=v.end()); 
	bool b_um = (um.find(key)!=um.end());
	bool b_s = (s.find(key)!=s.end());
	bool b_ms = (ms.find(key)!=ms.end());

}

In this example, Polyspace flags inappropriate uses of algorithm functions with container.

  • The function std::is_sorted returns a known constant when you call the function with a std::set object. The function returns an indeterminate value when you call it with an std::unoerderd_set object. Because the function call either returns a constant or an indeterminate value, calling std::is_sorted on std::set or std::unoerderd_set is unnecessary. Polyspace flags these usages.

  • An std::set or std::map object cannot contain duplicate elements by definition. Calling std::adjacent_find on these types of containers is unnecessary because the call always returns end(). Polyspace flags such usage.

  • Associative containers have their own size methods. Polyspace flags the use of std::distance to measure the size of an associative container.

#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <array>
#include <set>
#include <map>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <string>

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

void contains()
{
	std::string key;
	std::pair<const K, V> kv;
	std::map<K, V> m;
	std::set<V> s;
	std::multiset<V> ms;
	std::vector<V> v;
	std::unordered_set< V> us;
	
	// Expression always returns same value
	bool b1 = std::is_sorted(s.begin(), s.end()); 

	// Result might be indeterminate
	bool b2 = std::is_sorted(us.begin(), us.end());
	
	// std::set never has duplicates
	std::adjacent_find(s.begin(), s.end());
	
	// std::map never has duplicates
	std::adjacent_find(m.begin(), m.end()); 
	
	//Inefficient use	
	std::distance(s.begin(), s.end());
}

In this example, you pass the functor ExpensiveLess to std::stable_sort. This function copies the expensive functor, resulting in inefficient code. Polyspace reports a defect.

#include <string>
#include <vector>
#include <algorithm>
#include <functional>

class ExpensiveLess {
public:
    ExpensiveLess() {}

    bool operator()(const std::string &s1, const std::string &s2) const
    {
        return s1 < s2;
    }

    std::vector<std::string> m_list;
};

void foo()
{
    ExpensiveLess f;
    std::vector<std::string> v, v1;

    std::stable_sort(v.begin(), v.end(), f); //Defect
}
Correction — Use std::reference_wrapper Object

To fix this defect, create a std::reference_wrapper object wrapper. This object contains a reference to an ExpensiveLess object. Passing this inexpensive wrapper might improve the efficiency of your code.

#include <string>
#include <vector>
#include <algorithm>
#include <functional>

class ExpensiveLess {
public:
    ExpensiveLess() {}

    bool operator()(const std::string &s1, const std::string &s2) const
    {
        return s1 < s2;
    }

    std::vector<std::string> m_list;
};

void foo()
{
	ExpensiveLess f;
	std::reference_wrapper<ExpensiveLess> wrapper(f);
	std::vector<std::string> v, v1;
	std::stable_sort(v.begin(), v.end(), wrapper); //No Defect
}

Result Information

Group: Performance
Language: C++
Default: Off
Command-Line Syntax: EXPENSIVE_USE_OF_STD_ALGORITHM
Impact: Medium

Version History

Introduced in R2021b

expand all

See Also

Topics