Меня интересует портирование this Python code на C++. Как часть порта, я использую std::stack из заголовка <stack>. Как я могу определить, содержится ли какой-либо символ в пределах stack<char>? Например:Поиск определенного элемента в стеке
std::stack<char> myStack
if (!('y' is included in myStack)) // I know that this is wrong
{
}
C++ stack не поддерживает произвольный доступ, так что нет никакого прямого способа использования stack, чтобы проверить, если элемент содержится. Тем не менее, вы можете сделать копию стека, а затем непрерывно pop с этого стека, пока элемент не будет найден.
В качестве альтернативы, если вам нужно найти stack, вы можете вместо этого использовать deque, который поддерживает произвольный доступ. Например, вы могли бы использовать алгоритм find на deque для поиска элемента:
find(myDeque.begin(), myDeque.end(), myValue);
Если вам нужны частые поисковые запросы на stack, рассмотрит ведение параллельного set вместе с stack, которая хранит те же элементы, что и stack. Таким образом, вы можете просто использовать set::find, чтобы проверить (эффективно), существует ли элемент.
Надеюсь, это поможет!
Я пишу 'else if (! (Std :: find (myStack.begin(), myStack.end(), x)))' и дает мне ошибку _no operator "!" соответствует этим операндам_. Есть ли функция поиска, которая возвращает bool или делает это? –
Функция find возвращает итератор, а не логический. Вы должны написать if (std :: find (myStack.begin(), myStack.end(), x)! = myStack.end()) {...} – templatetypedef
Если вам нужно найти элемент в контейнере, по определению stack - это неправильный контейнер для ваших нужд. С крайне минимальным объемом информации, которую вы предоставили либо vector, либо deque, похоже, что они предоставят необходимый вам интерфейс (std::find(c.begin(), c.end(), item);).
Я использовал 'else if (! (find (visited.begin(), visited.end(), x))) 'и' else if (! (find_if (visit.begin(), visited.end(), x))) 'он дал мне ошибку _no operator"! " соответствует этим операндам_. ** Как вернуть true, если элемент найден? ** –
Поскольку вы хотите реализовать DFS и BFS, используя std::stack (для DFS) и std::queue (для BFS) действительно целесообразно, чтобы еще не посещенных узлов, и вам нужно только использовать push() и pop() методы этих контейнеров.
Но стека и очереди недостаточно для хранения посещенных узлов. Мое предпочтение было бы использовать ассоциативный контейнер, например. std::set, еще лучше unordered_set, если у вас есть его компилятор C++, поскольку поиск произвольного значения в ассоциативном контейнере происходит быстрее, чем в последовательности, такой как vector или deque (если данные не отсортированы там).
Имеет ли 'std :: set' функцию' pop' и 'push'? Я искал и узнал, что таких функций нет. Какие-либо предложения? –
Для ассоциативных контейнеров соответствующие операции «erase» и «insert». И вам, скорее всего, не понадобится «erase», потому что контейнер будет использоваться для посещенных узлов. Таким образом, программа будет использовать стек/очередь для посещений узлов и набор для уже посещенных узлов. –
Если вам нужно часто искать в стеке, подумайте об использовании набора рядом. Всегда сохраняйте также обновленный набор: если какой-либо элемент выталкивается из стека, удаляет его из набора и при любой операции нажатия в стек, вставьте его в набор.
stack<int> st;
set<int> s;
//push
st.push(2);s.insert(2);
//pop
s.erase(st.top()); st.pop();
//find (what your main objective was)
bool ispresent = s.find(2)!=s.end() ; // on failure the iterator = s.end()
Могу ли я спросить, почему вы используете стек и не устанавливаете? – Maciek
Невозможно выполнить итерацию/поиск в 'std :: stack', вам разрешено просматривать последний элемент и выталкивать его. Возможно, вам нужен другой контейнер. – birryree
Если вы хотите посмотреть на все элементы, вам, вероятно, не нужен стек. –