C++ Equiv. из C# intQueue.Contains()

Question

Я переводил хороший код с C# на C++, и я застрял на кажущемся основным вопросом.

Я хочу сделать простую оценку, чтобы увидеть, есть ли в очереди FIFO ints определенный int. Это не сложно сделать, но я не могу найти хороший пример в Google.

if(intQueue.Contains(value)){ /* do some stuff */ } 

Я нашел этот же вопрос, заданный через here, но ответ на самом деле не относится к моей ситуации. Пожалуйста помоги! Благодаря!

Answer 1

Я бы, вероятно, использовал std::find(), расположенный в <algorithm>. Вам необходимо передать начальные и конечные итераторы, к которым невозможно получить доступ, используя класс queue, поэтому хорошей альтернативой будет deque.

Deque функционирует аналогично очереди в том, что элементы могут быть нажаты и выскользнули из него, но элементы не ограничиваются моделью «первый в первом». Элементы можно выталкивать и выталкивать как со спины, так и спереди. Вот как класс queue сохраняет свои элементы по умолчанию.

#include <deque> 
#include <algorithm> 
#include <iostream> 

int main() 
{ 
    // initialize deque with ints 3, 2, 1 
    std::deque<int> intDeque{ 3, 2, 1 }; 

    auto it = std::find(intDeque.begin(), intDeque.end(), 2); // find 2 in intDeque 

    if (it == intDeque.end()) { 
     std::cout << "Not found" << std::endl; 
    } 
    else { 
     std::cout << "Found!" << std::endl; 
    } 

    return 0; 
} 

выше применений C++ 11, если у вас нет доступа к этому, вы можете сделать то же самое, как это:

std::deque<int> intDeque; 
// push elements onto the deque 
intDeque.push_back(3); 
intDeque.push_back(2); 
intDeque.push_back(1); 

std::deque<int>::iterator it = std::find(intDeque.begin(), intDeque.end(), 2); // find 2 in intDeque 

Answer 2

«PC луддитов» есть ответ, но здесь он находится в прямом преобразовании вашего примера:

#include <deque> 
#include <algorithm> 

... 

std::deque<int> intQueue; 
if (std::find(intQueue.begin(), intQueue.end(), value) != intQueue.end()) 
{ 
} 

Answer 3

Таким образом, при использовании deque или list непосредственно не является приемлемым и queue не поддаются поиск эффективно. Давайте продолжим очередь с cbegin/cend и включим std::find.

template <typename _Ty, typename _Container = deque<_Ty>> 
class searchable_queue : public std::queue<_Ty, _Container> 
{ 
public: 
    template<class... _Axx> 
    searchable_queue(_Axx&&... _Ax) 
     : std::queue<_Ty, _Container>(std::forward<_Axx>(_Ax)...) 
    {} 

    typename _Container::const_iterator cbegin() const noexcept 
    { 
     return (c.cbegin()); 
    } 

    typename _Container::const_iterator cend() const noexcept 
    { 
     return (c.cend()); 
    } 
}; 

int main() 
{ 
    list<int> l = { 11, 22, 44, 55 }; 
    auto q = searchable_queue<int,list<int>>(std::move(l)); 
    auto res = std::find(q.cbegin(), q.cend(), 22); 
    cout << boolalpha << (res != q.cend()) << '\n'; //displays 'true' 
    res = std::find(q.cbegin(), q.cend(), 77); 
    cout << boolalpha << (res != q.cend()) << '\n'; // displays 'false' 
    return 0; 
} 

Answer 4

Если вы можете использовать C++ 11 и выше, я предлагаю использовать any_of алгоритм:

#include <algorithm> 

if(std::any_of(intQueue.begin(), intQueue.end(), value)) 
{ 
    //do some stuff here 
} 

Не важно, что структура данных можно было бы использовать, до тех пор, как он предлагает итераторы.

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

#include <deque> 
#include <algorithm> 

// std::deque<int> intQueue; 
std::sort(intQueue.begin(), intQueue.end()); // !!! this is O(N log N) !!! 


if(std::binary_search(intQueue.begin(), intQueue.end(), value)) // O(log N) 
{ 
    //do some stuff here 
} 

Как выясняется: вы должны поддерживать отсортированный состояние после начальной сортировки (с O (журнал N) время вставки), в противном случае вы будете в конечном итоге с худшей сложности выполнения ,В частности, вам могут понадобиться элементы как состояния в порядке FIFO, чем второй подход не применим.