#c #insert #integer #containers #contains
#c #вставить #целое число #контейнеры #содержит
Вопрос:
Я хочу использовать структуру, в которую я вставляю целые числа, а затем могу спросить
if (container.contains(3)) { /**/ }
Должно быть что-то вроде этого.
Ответ №1:
Вы можете использовать std::vector .
std::vector<int> myVec;
myVec.push_back(3);
if (std::find(myVec.begin(), myVec.end(), 3) != myVec.end())
{
// do your stuff
}
Вы даже можете создать небольшую вспомогательную функцию:
template <class T>
bool contains(const std::vector<T> amp;vec, const T amp;value)
{
return std::find(vec.begin(), vec.end(), value) != vec.end();
}
Вот как вы могли бы это использовать:
if (contains(myVec, 3)) { /*...*/ }
Комментарии:
1. @Nemo: Операционная система никогда не запрашивала метод быстрого выполнения, а только рабочий метод. Я предложил общее решение общей проблемы. Если OP запрашивает конкретную проблему, где важна скорость, то другое решение было бы лучше. Выбор
std::setсразу только для сохранения поиска в линейное время влечет за собой другие последствия для дизайна, и я бы рассматривал это как преждевременную оптимизацию (когда на самом деле поиск даже не может быть узким местом в производительности). Преждевременная оптимизация — корень всего зла. Другое решение проблемы не стоит того, чтобы голосовать против, ИМО.2. @Nemo: Правильное решение с линейным временем подойдет, если измерение не докажет, что это существенное узкое место.
3. Линейное время — лучшее, что вы можете сделать, если по какой-либо причине вы не можете использовать отсортированный список или хэш-таблицу (например. вы хотите сохранить порядок вставки.)
4. Что мы все должны знать: Линейная итерация по коллекциям, линейным в памяти (как вектор, если однородный), выполняется (если повторяется) быстро, как молния! Держите тени рядом!
Ответ №2:
Простой алгоритм:
template <typename Container>
bool contains(Container constamp; c, typename Container::const_reference v) {
return std::find(c.begin(), c.end(), v) != c.end();
}
Вы можете настроить его для более эффективного поиска в некоторых известных контейнерах:
template <typename Key, typename Cmp, typename Alloc>
bool contains(std::set<Key,Cmp,Alloc> constamp; s, Key constamp; k) {
return s.find(k) != s.end();
}
template <typename Key, typename Value, typename Cmp, typename Alloc>
bool contains(std::map<Key,Value,Cmp,Alloc> constamp; m, Key constamp; k) {
return m.find(k) != m.end();
}
И таким образом вы получаете единый алгоритм, который выполняет поиск по любому типу контейнера и специально обработан для ускорения работы с теми контейнерами, которые упорядочены.
Ответ №3:
find для несортированного вектора равно O(n).
std::set поддерживает O (log n) вставок и поисковых запросов и является хорошим выбором.
std::tr1::unordered_set предоставляет аналогичный интерфейс, но поддерживает поиск практически в постоянном режиме времени. Это лучший выбор, если у вас есть TR1 (или C 0x) и вам не нужно перечислять элементы по порядку.
Комментарии:
1. Для небольших n несортированный вектор отлично подходит, возможно, даже быстрее.
Ответ №4:
Вам нужен метод find_first_of из библиотеки алгоритмов. (или двоичный поиск, или что-нибудь в этом роде)
Комментарии:
1. std::find_first_of выполняет поиск подпоследовательностей в большей последовательности, но ‘содержит(3)’ имеет только один скаляр без диапазона начала / конца. Так что std::find здесь подходит лучше.
Ответ №5:
Если вы хотите использовать стандартный контейнер C , из-за его конструкции сами контейнеры не обязательно содержат «contains», но вы всегда можете использовать алгоритм поиска.
Вы должны выбрать свой контейнер в соответствии с характеристиками вашего набора данных и «рабочей нагрузкой» доступа.
Для получения хорошей ссылки на контейнеры и алгоритмы в стандартной библиотеке C проверьте http://www.cplusplus.com
Если, как кажется, ваши данные состоят из уникальных элементов, для которых вы хотите связать значение, вам, вероятно, будет полезен контейнер map. Если все, что вас волнует, это «членство», то set — лучший выбор.