C++ Equiv. of C#'s intQueue.Contains()

本文关键字：intQueue Contains Equiv of C++ | 更新日期: 2023-09-27 17:58:14

我正在将大量代码从C#翻译成C++，但我陷入了一个看似基本的问题。

我想做一个简单的评估，看看int的FIFO队列是否包含一个特定的int。这可能很难做到，但我似乎在谷歌上找不到一个好的例子。

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

我在这里发现了同样的问题，但答案并不适用于我的情况。请帮忙！谢谢

C++ Equiv. of C#'s intQueue.Contains()

我可能会使用位于<algorithm>中的std::find()。您需要将起始迭代器和结束迭代器传递给它，使用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

如果您可以使用C++11及以上版本，我建议使用any_of算法：

#include <algorithm>
if(std::any_of(intQueue.begin(), intQueue.end(), value))
{
  //do some stuff here
}

使用什么数据结构并不重要，只要它提供迭代器即可。

注意你唯一需要注意的是所需的复杂性。在这里，您可能会得到O（N）比较但是，如果底层队列已知为排序（例如优先级队列），则可以将运行时改进为O（log 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（log N）插入时间）保持排序条件，否则您将面临更糟糕的运行时复杂性。特别是，您可能需要元素作为FIFO顺序的状态，而第二种方法不适用。

'PC Luddite'有答案，但这里是您的例子的直接转换：

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

因此，如果直接使用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;
}
相关文章：