эффективное использование памяти — C ++ проверяет, находится ли элемент в массиве
В C ++ у меня есть массив, и я пытаюсь проверить, есть ли определенный элемент в массиве. Вот мой массив:
string choices[3] = {"a", "b", "c"}
Я хочу, чтобы он выводил истину, если пользовательский ввод присутствует в массиве, поэтому, если пользователь введет «b», он напечатает истину и выдаст мне индекс массива. Это похоже на версию Python в или найти. Я знаю, что могу просто использовать цикл for, чтобы просмотреть все элементы, но есть ли более эффективный способ? Благодарю.
Решение
Для поиска индекса вы можете использовать следующий код:
int x = std::distance(choices, std::find(choices, choices + 3, "b"));
Вот, distance а также find метод можно найти в <algorithm> заголовок.
Другие решения
Вы можете использовать стандартный алгоритм std::find объявлено в заголовке <algorithm> Это решает две задачи. Он может сказать, присутствует ли строка в контейнере, и он может предоставить индекс первого найденного элемента.
Если вам нужно только определить, присутствует ли строка в контейнере, вы можете использовать стандартный алгоритм std::any_of
Оба алгоритма имеют линейную сложность.
Если контейнер (например, массив) упорядочен, то вы можете использовать стандартный алгоритм std::binary_search определить, присутствует ли строка в контейнере.
Пример, демонстрирующий использование стандартного алгоритма std::find
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>
int main()
{
std::string choices[] = { "a", "b", "c" };
std::cout << "Enter a string: ";
std::string s;
std::cin >> s;
auto it = std::find( std::begin( choices ), std::end( choices ), s );
bool in_array = it != std::end( choices );
std::cout << "String "\" << s << "\" is present in the array = "<< std::boolalpha << in_array << std::endl;
if ( in_array )
{
std::cout << "It is " << std::distance( std::begin( choices ), it )
<< " element in the array" << std::endl;
}
}
Если вам нужно более сложное условие поиска элемента в контейнере, вы можете использовать стандартный алгоритм std::find_if который принимает предикат в качестве аргумента.
std::find возвращает итератор для элемента в массиве, если он найден, или конечный итератор в противном случае:
auto const last = std::end(choices);
auto const pos = std::find(std::begin(choices), end, "b");
if (last != pos) {
// Use pos here.
}
Если вам не нужно ничего делать с элементом, вы можете использовать any_of:
if (std::any_of(std::begin(choices), std::end(choices),
[](std::string const& s) { return "b" == s; })
{
// "b" is in the array.
}
Обе эти функции являются внутренними циклами, они не будут быстрее, чем рукописные циклы. Если ваш массив отсортирован, то вы можете использовать std::lower_bound вместо std::find а также std::binary_search вместо std::any_of,
Нет более эффективного способа, если только предметы не заказаны. Учтите, что элемент, который вы хотите найти, теоретически может иметь любой индекс, включая последний индекс, который вы бы проверили.
Если вы хотите найти его эффективно, используйте std::set, Тогда вы можете использовать set::count(item) > 0 решить, если item находится в наборе.
Кроме того, в Python, он эффективно делает цикл над всеми элементами, когда вы проверяете, есть ли элемент в списке item in [itemA, itemB, itemC] или в кортеже item in (itemA, itemB, itemC), Это только когда вы используете Python set а также frozenset что этот поиск очень быстрый.
Я бы порекомендовал использовать функцию std::find если вы не хотите сами писать цикл O (n) и использовать std::set класс, если вы хотите быстрее поиск.