Почему std :: set не имеет функции-члена «содержит»?

103

Я активно использую, std::set<int>и часто мне просто нужно проверить, содержит ли такой набор число или нет.

Я считаю естественным написать:

if (myset.contains(number))
   ...

Но из-за отсутствия containsчлена мне нужно написать громоздкое:

if (myset.find(number) != myset.end())
  ..

или не такое очевидное:

if (myset.count(element) > 0) 
  ..

Есть ли причина для такого дизайнерского решения?

бессмыслица
источник
7
Большая часть стандартной библиотеки работает с итераторами, поэтому обычно функции, возвращающие итераторы, - это то, что вы ожидали. Хотя нетрудно написать функцию, чтобы абстрагироваться от этого. Скорее всего, компилятор встроит его, поскольку это должна быть только одна или две строки кода, и вы получите такую ​​же производительность.
NathanOliver 01
3
Другая (более фундаментальная) проблема с этим count()подходом заключается в том, что он выполняет больше работы, чем countains()нужно.
Лео Хайнсаар 02
11
Основная причина позади этого проекта решения является то , contains()который возвращает boolбы потерять ценную информацию о том, где элемент находится в коллекции . find()сохраняет и возвращает эту информацию в виде итератора, поэтому это лучший выбор для универсальной библиотеки, такой как STL. (Это не bool contains()значит, что это не очень приятно иметь или даже не нужно, хотя.)
Лео Хайнсаар,
3
С contains(set, element)помощью общедоступного интерфейса набора легко написать бесплатную функцию. Таким образом, интерфейс набора функционально завершен; добавление удобного метода просто увеличивает интерфейс без включения каких-либо дополнительных функций, чего нельзя сказать о C ++.
Тоби Спейт
3
Мы закрываем все в эти дни? Каким образом этот вопрос "основан преимущественно на мнении"?
Mr. Alien

Ответы:

148

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

Лично я считаю это ошибкой.

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

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

Хотя все равно обидно.

Мартин Боннер поддерживает Монику
источник
5
Между прочим, то же самое и с картами и мульти-картами (что так же уродливо, но менее уродливо, чем все эти сравнения .end()).
Matteo Italia
8
В качестве альтернативы они могли не видеть необходимости в дополнительном члене contains()на том основании, что он был бы избыточным, поскольку для любого std::set<T> sи T tрезультат s.contains(t)точно идентичен результату static_cast<bool>(s.count(t)). Поскольку использование значения в условном выражении приведет к его неявному преобразованию bool, они, возможно, сочли, что count()это достаточно хорошо служит цели.
Джастин Тайм - Восстановите Монику
2
Орфографическая ошибка? if (myset.ICanHaz(element)) ...: D
Стефан Гуришон 02
3
@MartinBonner На самом деле не имеет значения, были ли причины для отказа от него тупыми. Также не имеет значения, был ли разговор 100% -ным окончательным обоснованием. Ваш ответ здесь - всего лишь разумное предположение о том, как вы думаете, что это должно быть. Разговор, и ответ от кого - то не только участвует в ней, но поставлена задача предложить его (несмотря на то, что они не делали), бесспорно , ближе к истине , чем это предположение, независимо от того , как вы смотрите на него. Как минимум, вы должны хотя бы упомянуть об этом в этом ответе, это было бы большим улучшением и было бы ответственным делом.
Jason C
2
@JasonC: Не могли бы вы отредактировать раздел внизу? Я не совсем понимаю, о чем вы пытаетесь сказать, и комментарии, вероятно, не лучший способ прояснить это. Спасибо!
Мартин Боннер поддерживает Монику
44

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

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

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

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

Лео Хайнсаар
источник
5
И интересно отметить, что это обсуждение закончилось почти достижением консенсуса в отношении того, что это желательно, и вас попросили написать предложение по этому поводу.
PJTraill 02
@PJTraill Верно, и причина, по которой я не пошел дальше, заключается в том, contains()что, очевидно, это будет сильно взаимодействовать с существующими контейнерами и алгоритмами, на которые будут сильно влиять концепции и диапазоны - в то время, которое ожидается в C ++ 17 - и Я был убежден (в результате обсуждения, а также нескольких личных обменов электронной почтой), что лучше сначала дождаться их. Конечно, в 2015 году не было ясно, что ни концепции, ни диапазоны не войдут в C ++ 17 (на самом деле, на это возлагались большие надежды). Однако я не уверен, что стоит заниматься этим сейчас.
Лео Хайнсаар, 03
1
Ибо std::set(об этом и спрашивается) я не понимаю, как countработает больше, чем containsнужно. Реализация glibc count(примерно) return find(value) == end() ? 0 : 1;. Помимо подробностей о тернарном операторе и просто возврате != end()(который, как я ожидал, оптимизатор удалит), я не вижу, как там еще работать.
Мартин Боннер поддерживает Монику
4
"... contains (), который возвращает логическое значение, потеряет ценную информацию о том, где элемент находится в коллекции " - если пользователь позвонит myset.contains()(если он существует), это будет довольно убедительным признаком того, что эта информация не представляет ценности ( пользователю в этом контексте).
Кейт Томпсон
1
Почему делает count()больше работы, чем contains()нужно std::set? Он уникален, поэтому count()может быть return contains(x) ? 1 : 0;точно таким же.
Timmmm
22

Его не хватает, потому что его никто не добавил. Никто не добавил его, потому что контейнеры из 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типов C ++, используя эту технику.

Имеет смысл просто сделать это:

if (some_set.count(some_element)) {
}

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

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

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

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

Якк - Адам Неврамонт
источник
2
1 миллиард копий 7? А здесь я подумал, что std::setне может содержать дубликатов и поэтому std::set::countвсегда будет возвращать 0или 1.
nwp 02
5
@nwp std::multiset::countcan
milleniumbug
2
@nwp Мне не хватает backticksслова "набор" потому, что я не говорю std::setконкретно о нем. Чтобы вам
стало
3
Кажется, я упустил шутку из-за того, на что должно было подразумеваться «мяу».
user2357112 поддерживает Монику
2
@ user2357112 мяу - это заполнитель для "набор или карта". Спросите STL, почему.
Yakk - Adam Nevraumont 02
12

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

Слава
источник
8
Обратите внимание, что stringэто чудовище: он существовал до STL, где у него были lengthи все те методы, которые основаны на индексах, а затем был «контейнерован», чтобы соответствовать модели STL ... без удаления существующих методов по причинам обратной совместимости . См. GotW # 84: Monoliths Unstrung => stringдействительно нарушает принцип проектирования «минимальное количество функций-членов».
Matthieu M.
5
Но тогда возникает вопрос: «Почему стоит иметь такую ​​концепцию AssociativeContainer?» - и я не уверен, что это было задним числом.
Мартин Боннер поддерживает Монику
24
Для меня имеет смысл спрашивать, содержит ли мультимножество, мультикарту или карту что-то. Фактически, containsна множестве / карте трудозатрат равен, но может быть выполнен быстрее, чем countна мультинаборе / мульти- карте .
Yakk - Adam Nevraumont 01
5
AssociativeContainer не требует, чтобы классы не имели containsметода.
user2357112 поддерживает Монику
6
@Slava Это как сказать size()и empty()есть дубликаты, но во многих контейнерах есть и то, и другое.
Barry
10

Хотя я не знаю, почему 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)) ...
ржавый
источник
3
-1, потому что этому прямо противоречит тот факт, что на самом деле containsметод существует, просто он назван глупо.
Matteo Italia,
4
«В STL стремится предложить минимальный интерфейс» галка std::string кашель
Болы
6
@bolov: ваша точка зрения? std.::stringНЕ является частью STL! Это часть стандартной библиотеки и шаблон задним числом ...
MFH
3
@MatteoItalia countможет быть медленнее, так как ему фактически нужно сделать два finds, чтобы получить начало и конец диапазона, если код используется совместно с multiset.
Марк Рэнсом,
2
OP уже знает, что это избыточно, но, очевидно, хочет, чтобы код читался явно contains. Я не вижу в этом ничего плохого. @MarkRansom, маленький SFINAE предназначен для предотвращения привязки этого шаблона к вещам, которых он не должен.
rustyx 01
7

Истинная причина этого для 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();
}

Конечно, все это лишь домыслы.

Мартин Дроздик
источник
1
Да, но это не относится к наборам int.
Jabberwocky
7
Вот только люди могут if (myMap.count("Meaning of universe"))нормально писать , так что ...?
Барри
@MichaelWalz Ой, ты прав. Я изменил свой ответ, включив в него также заданный пример. Однако аргументация для набора int для меня остается загадкой.
Мартин Дроздик 01
2
Это не может быть правдой. Они могут так же легко написать ваш неэффективный код, containsкак с count.
Мартин Боннер поддерживает Монику
2

Начиная с c ++ 20,

bool contains( const Key& key ) const

доступен.

Энди
источник
0

А что насчет binary_search?

 set <int> set1;
 set1.insert(10);
 set1.insert(40);
 set1.insert(30);
 if(std::binary_search(set1.begin(),set1.end(),30))
     bool found=true;
Массимилиано Ди Кавио
источник
Это не сработало бы std::unordered_set, но сработало std::setбы.
Jabberwocky
Это нормально, binary_search работает только для двоичных деревьев.
Массимилиано Ди Кавио
0

contains () должен возвращать bool. Используя компилятор C ++ 20, я получаю следующий вывод кода:

#include<iostream>
#include<map>
using namespace std;

int main()
{
    multimap<char,int>mulmap;
    mulmap.insert(make_pair('a', 1)); //multiple similar key
    mulmap.insert(make_pair('a', 2)); //multiple similar key
    mulmap.insert(make_pair('a', 3)); //multiple similar key
    mulmap.insert(make_pair('b', 3));
    mulmap.insert({'a',4});
    mulmap.insert(pair<char,int>('a', 4));
    
    cout<<mulmap.contains('c')<<endl;  //Output:0 as it doesn't exist
    cout<<mulmap.contains('b')<<endl;  //Output:1 as it exist
}
Башар
источник
-1

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

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

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

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

Майк Тюканов
источник