Exponenta Banner

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

Функции от algorithm библиотека неправильно используется с несоответствующими входными параметрами, приводящими к неэффективному коду

расширьте все на странице

Описание

Это средство проверки повышено, когда вы используете функции в algorithm библиотека неэффективно или с несоответствующими входными параметрами. Вы можете повторно вычислять известную или постоянную информацию о контейнере, или вы можете использовать функцию, которая является несоответствующей для контейнера. Сценарии, которые инициировали это средство проверки, включают:

  • Используя поиск функционирует, такие как std::find, std::equal_range, std::upper_bound, std::binary_search и std::lower_bound на ассоциативных контейнерах, таких как std::set, std::map, std::multiset, и std::mutimap.

  • Используя std::count проверять, содержит ли контейнер определенный ключ. Таким образом, выход std::count преобразован в bool или по сравнению с любым 0 или 1.

  • Используя std::is_sorted на ассоциативном контейнере.

  • Используя std::distance вычислить размер ассоциативного контейнера.

  • Используя std::adjacent_find на контейнерах уникального значения, таких как std::set или std::map.

Риск

Неправильное использование функций от algorithm библиотека или использование их с несоответствующими наборами входа могут привести к неэффективному коду или неожиданному поведению. Например:

  • Функционирует, такие как std::find и std::binary_search выполните линейный поиск, который неэффективен для ассоциативных контейнеров.

  • Функциональный std::count выполняет линейный поиск, чтобы считать все соответствующие ключи в контейнере. При проверке, существует ли ключ в контейнере, выполняя исчерпывающий поиск каждого экземпляра ключа путем вызова std::count является ненужным и неэффективным.

  • Выход std::is_sorted является постоянным, когда обращено отсортированный контейнер. Выход неопределенен, когда функция вызвана на неотсортированном контейнере. Поскольку результат известен заранее, вызов является ненужным. Неопределенный выход может привести к неожиданному поведению.

  • Ассоциативные контейнеры имеют свой собственный size метод, который более эффективен, чем использование std::distance.

  • Выход std::adjacent_find то, когда это используется на уникальном контейнере значения, является end(). Компилятор производит тот же выход после исчерпывающего двоичного поиска. Поскольку выход известен заранее, вызов неэффективен.

Исправление

Чтобы зафиксировать этот дефект, осуществите рефакторинг свой код, чтобы использовать стандартный algorithm функции более эффективно. Определенная фиксация может зависеть от вашего варианта использования. Например:

  • При использовании ассоциативных контейнеров вызовите их методы члена, такие как std::set::find, вместо std функции, такие как std::find.

  • Чтобы проверять включение, используйте член find или contains (C++ 20), функционирует вместо std::count. Для контейнеров без этих функций членства используйте std::find вместо std::count.

  • Избегайте использования std::is_sorted или std::adjacent_find на ассоциативных контейнерах.

  • Чтобы проверять размер ассоциативного контейнера, используйте его член size функция, такая как std::vector::size. Избегайте использования std::distance вычислить размер.

Повышения производительности могут варьироваться на основе компилятора, реализации библиотеки и среды, которую вы используете.

Примеры

развернуть все

#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);         //Noncompliant 
	std::equal_range(m.begin(), m.end(), kv);   //Noncompliant  
	std::lower_bound(mm.begin(), mm.end(), kv); //Noncompliant 
	std::upper_bound(ms.begin(), ms.end(), key);  //Noncompliant
	std::count(um.begin(), um.end(), kv);         //Noncompliant 
	if(std::binary_search(s.begin(), s.end(), key)==0){         //Noncompliant 
          //....
      }

	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
	

}

В этом примере, Polyspace® отмечает использование std функции поиска, такие как std::find или std::count, на ассоциативных контейнерах, когда контейнеры имеют эквивалентные функции членства. Используя их std функции с контейнерами, которые не имеют эквивалентных функций членства, совместимы с этим правилом. Например, Polyspace отмечает использование std::find на set потому что std::set::find более эффективно. Используя find на vector совместимо потому что класс vector не имеет никакой эквивалентной функции членства.

Коррекция

Чтобы зафиксировать этот дефект, используйте функцию членства ассоциативных контейнеров вместо std функции. Если нет никакой эквивалентной функции членства, то осуществите рефакторинг свой код, чтобы использовать существующие функции членства. Например, замените std::binary_search с std::set::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 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);         //Compliant 
	m.equal_range(key);   //Compliant 
	mm.lower_bound(key); //Compliant    
	ms.upper_bound(key);  //Compliant  
      if(s.find(key)==s.end()){         //Compliant 
          //....
      }
      um.count(key);//Compliant


}
#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 conatins()
{
	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);//Noncompliant 
	bool b_um = std::count(um.begin(), um.end(), kv);//Noncompliant
	bool b_s = std::count(s.begin(), s.end(), key);//Noncompliant
	bool b_ms = std::count(ms.begin(), ms.end(), key);//Noncompliant
	
	if(std::count(v.begin(), v.end(), key)==2){ //Compliant
		//...
	}

}

В этом примере Polyspace отмечает использование std::count проверять, содержит ли контейнер конкретный член. Более эффективно использовать член, находят функцию или std::find функция для проверки включения.

Используя std::count считать экземпляры члена не повышает дефект, если контейнер не имеет эквивалентного члена. Например, Polyspace не повышает дефект когда std::count используется для проверки если v содержит два экземпляра key.

Коррекция — использует find проверять включение

Чтобы зафиксировать эти дефекты, использование член ищут функции, такие как std::set::find проверять на включение. При проверке включения в контейнер, который не имеет члена find функция, используйте std::find вместо std::count.

#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 conatins()
{
	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());//Compliant 
	bool b_um = (um.find(key)!=um.end());//Compliant
	bool b_s = (s.find(key)!=s.end());//Compliant
	bool b_ms = (ms.find(key)!=ms.end());//Compliant

}
#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 conatins()
{
	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()); //NonCompliant

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

В этом примере Polyspace отмечает несколько несоответствующего и неэффективного использования algorithm функции. Например:

  • Функциональный std::is_sorted возвращает известную константу, когда она называется на set объект. Функция возвращает неопределенное значение, когда обращено unoerderd_set. Polyspace отмечает эти использования.

  • set или map не может содержать дублирующиеся элементы по определению. Вызов std::adjacent_find на этих типах контейнеров всегда возвращает end(). Polyspace отмечает такое использование.

  • Ассоциативные контейнеры имеют свой собственный size функция. Polyspace отмечает использование std::distance измерять размер ассоциативного контейнера.

Информация о результате

Группа: Производительность
Язык: C++
Значение по умолчанию: Off
Синтаксис командной строки: EXPENSIVE_USE_OF_STD_ALGORITHM
Удар: Средняя

Смотрите также

Темы

Введенный в R2021b

Документация Polyspace Bug Finder

Поддержка