Как один член теста проверить элемент в неупорядоченной последовательности (C ++)?

Question

Я давно использую python, и я только начинаю использовать C ++

. В python, если есть набор или словарь, относительно легко получить логическое значение, указывающее,или нет определенного элемента в этой последовательности с использованием ключевого слова in .то есть

a = set(2,4,3)   
if 4 in a  
print "yes, 4 is in a, thank you for asking!"

это гораздо эффективнее, чем это:

a = [2,3,4]  
for number in a
>if number == 4  
>>return "yes, 4 is in a, thank you for asking!"

есть ли способ сделать тест на членство простым и эффективным в cpp или вам всегда приходится повторятькакая-то упорядоченная последовательность?

Answer 1

Посмотрите на контейнеры, предлагаемые STL , и их рабочие характеристики.

Answer 2

Познакомьтесь со стандартной библиотекой шаблонов C ++.Класс set (и другие) имеет метод find(), который возвращает итератор для элемента в наборе, если он существует.

Answer 3

У вас есть такая функциональность в std :: set и tr1 :: unordered_set (еще не в стандарте C ++).

#include <set>
#include <cstdio>

int main() {
     std::set<int> s;
     s.insert(1);        
     s.insert(2);
     s.insert(4);
     if (s.find(4) != s.end())
          puts("4 found!");
     return 0;
}

На самом деле, если ваш набор данных небольшой, линейный поиск все еще может быть более быстрым вариантом.

Answer 4

std::find может определить, существует ли элемент в каком-либо неупорядоченном контейнере или последовательности.Если последовательность неупорядочена и не хранится в специализированном контейнере, предназначенном для поиска, вряд ли вы добьетесь большего успеха, чем O(N).

Answer 5

template<typename T>
bool contains(const std::set<T>& a, const T& value) {
    return a.find(value) != a.end();
}

if (contains(a, 4)) {
    std::cout << "A contains 4\n";
}

Answer 6

Метод Python не "намного более эффективен", потому что вы не знаете сложности конструкции in.

В C ++ существует много методов хранения данных.Бинарные деревья лучше всего подходят для поиска.

Если вы работаете с числами, такими как 2,3,4 и т. Д., Вы можете рассмотреть возможность использования массива bools и просто посмотреть, если array[4] == true