C++ Equiv。 C＃的intQueue.Contains（）

我正在翻譯從C＃到C++的一些代碼，我被困在一個看似基本的問題上。C++ Equiv。 C＃的intQueue.Contains（）

我想做一個簡單的評估，看看int的FIFO隊列是否包含特定的int。這不難做到，但我似乎無法在Google上找到一個好例子。

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

我發現問完了here同樣的問題，但答案並不真正適用於我的情況。請幫忙！謝謝！

來源

2016-07-23 trademark

'intQueue'是一個不是類型的變量。可能類型是'隊列'？我將在C++中使用'deque'和'find'成員函數。 –

沒錯。作爲一個例子，intQueue是一個變量名。也許一個德克更適合這種情況。感謝您的評論。我會研究一下。 – trademark

更正。我的意思是'std :: find'。 deque沒有找到成員函數。 –

我可能會使用位於<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

來源

2016-07-23 04:29:28

「PC勒德分子」有答案，但在這裏它是在你的榜樣的直接轉換：

#include <deque> 
#include <algorithm> 

... 

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

來源

2016-07-23 15:13:06

你不能用'queue'來做這件事。 'queue'不允許你訪問開始和結束迭代器。 –

@PCLuddite：你說得對 - 謝謝你。 –

因此，如果使用的是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; 
}

來源

2016-07-23 17:02:26

如果你可以使用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順序的狀態作爲狀態，而第二種方法不適用。

來源

2016-07-23 17:07:53 ovanes

C++ Equiv。 C＃的intQueue.Contains（）

回答

相關問題