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

Question

私はC＃からC++にコードを翻訳していますが、私は一見基本的な質問に固執しています。

intのFIFOキューに特定のintが含まれているかどうかを簡単に評価したいと考えています。これは難しいことではありませんが、Googleで良い例を見つけることはできません。

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

私はhere上で求めていたこの同じ質問を見つけましたが、答えは本当に私の状況には適用されません。助けてください！ありがとう！

Answer 1

おそらく、<algorithm>にあるstd::find()を使用します。 queueクラスではアクセスできない開始イテレータと終了イテレータを渡す必要があります。良い代替手段は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; 
} 

上記の使用は、あなたがそれへのアクセスを持っていない場合、あなたはこのような同じことを行うことができ、11をC++：

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

、直接受け入れられないとqueueが効率的に検索するには向いていないdequeまたはlist使用している場合。 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 
} 

は、それがイテレータを提供していますように、1が使用する可能性がありますどのようなデータ構造は重要ではありません。

注！注意を払う必要があるのは、望ましい複雑さだけです。ここでは、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順の状態として要素を必要とする場合がありますが、2番目の方法は適用されません。