Почему std:: set не имеет функции "содержит"?

Ответ 1

Я думаю, что это, вероятно, потому, что они пытались сделать std::set и std::multiset как можно более похожими. (И, очевидно, count имеет совершенно разумный смысл для std::multiset.)

Лично я думаю, что это была ошибка.

Это выглядит не так уж плохо, если вы притворяетесь, что count - это просто орфографическая ошибка contains и записать тест как:

if (myset.count(element)) 
   ...

Ответ 2

Чтобы иметь возможность писать if (s.contains()), contains() должен возвращать bool (или тип, конвертируемый в bool, что является другой историей), как это делает binary_search.

фундаментальная причина принятия решения о дизайне , а не сделать это таким образом, заключается в том, что contains(), который возвращает bool, потеряет ценную информацию о том, где находится элемент в коллекция. find() сохраняет и возвращает эту информацию в форме итератора, поэтому является лучшим выбором для универсальной библиотеки, такой как STL. Это всегда было руководящим принципом для Алекса Степанова, как он часто объяснял (например, здесь).

Что касается подхода count() в целом, хотя он часто является хорошим решением, проблема в том, что он выполняет больше работы, чем contains().

Это не означает, что bool contains() не очень хорошо иметь или даже необходимо. Некоторое время назад у нас была долгая дискуссия об этой же самой проблеме в Стандарт ISO C++ - Группа будущих предложений.

Ответ 3

Этого не хватает, потому что никто не добавил его. Никто не добавил его, потому что контейнеры из STL, в которые встроена библиотека std, где они были минимальными в интерфейсе. (Обратите внимание, что std::string не поступал из STL таким же образом).

Если вы не против какого-то странного синтаксиса, вы можете подделать его:

template<class K>
struct contains_t {
  K&& k;
  template<class C>
  friend bool operator->*( C&& c, contains_t&& ) {
    auto range = std::forward<C>(c).equal_range(std::forward<K>(k));
    return range.first != range.second;
    // faster than:
    // return std::forward<C>(c).count( std::forward<K>(k) ) != 0;
    // for multi-meows with lots of duplicates
  }
};
template<class K>
containts_t<K> contains( K&& k ) {
  return {std::forward<K>(k)};
}

использование:

if (some_set->*contains(some_element)) {
}

В принципе, вы можете писать методы расширения для большинства типов С++ std, используя эту технику.

Для этого гораздо больше смысла:

if (some_set.count(some_element)) {
}

но меня удивляет метод метода расширения.

Самое печальное, что писать эффективный contains может быть быстрее на multimap или multiset, поскольку они просто должны найти один элемент, а count должен найти каждый из них и подсчитать их.

Мультимножество, содержащее 1 миллиард экземпляров 7 (вы знаете, в случае, если вы закончите) может иметь очень медленный .count(7), но может иметь очень быстрый contains(7).

С помощью вышеупомянутого метода расширения мы могли бы сделать это быстрее для этого случая, используя lower_bound, по сравнению с end, а затем сравнивая его с элементом. Для этого для неупорядоченного мяука, а также заказанного мяу потребуются фантастические SFINAE или специфические для контейнера перегрузки.

Ответ 4

Вы смотрите на конкретный случай и не видите большую картинку. Как указано в документации std::set отвечает требованиям AssociativeContainer концепция. Для этой концепции не имеет смысла иметь метод contains, поскольку он почти бесполезен для std::multiset и std::multimap, но count отлично работает для всех из них. Хотя метод contains может быть добавлен как псевдоним для count для std::set, std::map и их хэшированных версий (например, length для size() в std::string), но выглядит так, как создатели библиотеки не видели реальной потребности в нем.

Ответ 5

Хотя я не знаю, почему std::set не имеет contains, но count, который только возвращает 0 или 1, вы можете написать шаблонную вспомогательную функцию contains следующим образом:

template<class Container, class T>
auto contains(const Container& v, const T& x)
-> decltype(v.find(x) != v.end())
{
    return v.find(x) != v.end();
}

И используйте его следующим образом:

    if (contains(myset, element)) ...

Ответ 6

Истинная причина для set - загадка для меня, но одно возможное объяснение для этой же конструкции в map может заключаться в том, чтобы предотвратить случайное обращение людей с неэффективным кодом:

if (myMap.contains("Meaning of universe"))
{
    myMap["Meaning of universe"] = 42;
}

Это приведет к двум поисковым запросам map.

Вместо этого вам нужно получить итератор. Это дает вам мысленный намек на то, что вы должны повторно использовать итератор:

auto position = myMap.find("Meaning of universe");
if (position != myMap.cend())
{
    position->second = 42;
}

который потребляет только один поиск map.

Когда мы понимаем, что set и map сделаны из одной и той же плоти, мы можем применить этот принцип также к set. То есть, если мы хотим действовать на элемент в set, только если он присутствует в set, этот проект может помешать нам писать код следующим образом:

struct Dog
{
    std::string name;
    void bark();
}

operator <(Dog left, Dog right)
{
    return left.name < right.name;
}

std::set<Dog> dogs;
...
if (dogs.contain("Husky"))
{
    dogs.find("Husky")->bark();
}

Конечно, все это просто предположение.

Ответ 7

А как насчет бинарного поиска?

 set <int> set1;
 set1.insert(10);
 set1.insert(40);
 set1.insert(30);
 if(std::binary_search(set1.begin(),set1.end(),30))
     bool found=true;

Ответ 8

Другая причина заключается в том, что это даст программисту ложное впечатление, что std:: set - это набор в смысле теории математического набора. Если они реализуют это, тогда последует много других вопросов: если std:: set содержит() для значения, почему он не имеет его для другого набора? Где union(), intersection() и другие заданные операции и предикаты?

Разумеется, ответ состоит в том, что некоторые из заданных операций уже реализованы как функции в (std:: set_union() и т.д.), а другие реализованы так же тривиально, как contains(). Функции и объекты функций лучше работают с математическими абстракциями, чем элементы объекта, и они не ограничены конкретным типом контейнера.

Если нужно реализовать полную функциональность с математическим набором, у него есть не только выбор базового контейнера, но также он имеет выбор деталей реализации, например, будет ли его функция theory_union() работать с неизменяемыми объектами, лучше подходит для функционального программирования, или он изменит свои операнды и сохранит память? Будет ли он реализован как объект функции с самого начала или лучше реализовать C-функцию и использовать std:: function < > если необходимо?

Как и сейчас, std:: set - это просто контейнер, хорошо подходящий для реализации набора в математическом смысле, но он почти не является теоретическим набором, как std::vector, из теоретического вектора.