deque,queue,priority_queue
をテンプレートにして作成
[
トップ
|
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
開始行:
std::deque,queue,priority_queue
-----
#contents
-----
*deque [#nf3cbe70]
両端キュー(double-ended queue)．値をコンテナの両端から格...
メンバ関数はほぼvectorと同じであり，
先頭への要素の追加，削除用関数があることが異なる．
***インクルード [#h89f568a]
#include <deque>
***先頭への要素の追加，削除(push_front,pop_front) [#lfcce...
-push_front(val) : コンテナの先頭に要素を追加
void push_front(const T& val);
-pop_front() : コンテナの先頭要素を削除
void pop_front();
***vectorとdeque,どちらを使うべきか？ [#q7021b67]
dequeは名前からキューであるように思えるが，実際には任意の...
サポートしていてvectorとよく似ている．
しかし，両コンテナは以下のように操作によってパフォーマン...
-要素アクセス時間 : vector < deque
-コンテナ両端への要素の追加にかかる時間 : deque < vector
-コンテナ中間への要素の追加にかかる時間 : あまり変わらな...
一般的には要素アクセス速度が速いvectorを使えばよいが，両...
また，dequeはメモリ上の非連続領域を用いる場合もあるらしい...
従来の配列との互換性が必要な場合はvectorを用いた方がよい．
*queue [#g62b3c8c]
FIFO(First In First Out)方式のキューとして値を格納する．
dequeを基底としたコンテナアダプタ．
***インクルード [#he9d4889]
#include <queue>
***初期化(コンストラクタ) [#j0d0f7ec]
explicit queue(const Container& ctnr = Container());
***メンバ関数 [#lf020290]
-front() : コンテナの最初の要素にアクセスする関数
value_type& front();
const value_type& front() const;
-back() : コンテナの最後の要素にアクセスする関数
value_type& back();
const value_type& back() const;
-size() : コンテナのサイズを返す関数
size_type size() const;
-empty() : コンテナが空だったらtrueを返す関数．
bool empty () const;
-push(val) : コンテナの最後に要素を追加
void push(const T& val);
-pop() : コンテナの最初の要素を削除
void pop();
使用例
#code(C){{
#include <iostream>
#include <queue>
using namespace std;
int main(void)
{
queue<int> x;
for(int i = 0; i < 5; ++i){
x.push(i);
cout << x.back() << " ";
}
cout << endl;
for(int i = 0; i < 5; ++i){
cout << x.front() << " ";
x.pop();
}
cout << endl;
return 0;
}
}}
実行結果
0 1 2 3 4
0 1 2 3 4
***deque以外のコンテナを用いたqueue [#af9693e5]
queueコンテナアダプタの標準の基底はdequeであるが，
別のコンテナを基底に指定することもできる．
別のコンテナを使用したい場合は，
list<int> l(10, 1);
queue<int, list<int> > q(l);
のようにする．
*priority_queue [#x2df3f89]
優先順位付きのqueue．
クラスのテンプレート仕様は，
template < class T, class Container = vector<T>,
class Compare = less<typename Container::valu...
となっており，
定義時にデータ型，基底コンテナ(デフォルトはvector)，優先...
***インクルード [#k9c98188]
#include <queue>
***初期化(コンストラクタ) [#yf909b8a]
explicit priority_queue(const Compare& x = Compare(),
const Container& y = Container...
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last,
const Compare& x = Compare(),
const Container& y = Container());
***メンバ関数 [#p979d734]
-top() : 優先度が最も高い要素への参照を返す関数
const value_type& top() const;
-size() : コンテナのサイズを返す関数
size_type size() const;
-empty() : コンテナが空だったらtrueを返す関数．
bool empty () const;
-push(val) : キューに要素を追加
void push(const T& val);
-pop() : キューの最初の要素を削除
void pop();
使用例
#code(C){{
#include <iostream>
#include <queue>
using namespace std;
int main(void)
{
string s[] = {"b", "d", "a", "c", "e"};
priority_queue<string> x(s, s+5);
while(!x.empty()){
cout << x.top();
x.pop();
}
cout << endl;
priority_queue<string, vector<string>, greater<string> >...
while(!y.empty()){
cout << y.top();
y.pop();
}
cout << endl;
return 0;
}
}}
実行結果
edcba
abcde
***クラスオブジェクトの優先度付きキュー [#u41dab8e]
intやdoubleなどの組込オブジェクトでは優先順位が既に規定さ...
自身が作成したクラスについてpriority_queueを用いたい場合...
operator<を定義すればよい．
例
#code(C){{
#include <iostream>
#include <queue>
using namespace std;
class rxPriorityData
{
int m_iPriority;
double m_fValue;
public:
rxPriorityData() : m_iPriority(0),m_fValue(0.0) {}
rxPriorityData(int priority, double value) : m_iPriority...
int GetPriority(void) const { return m_iPriority; }
friend std::ostream &operator<<(std::ostream &out, rxPri...
};
inline bool operator<(rxPriorityData a, rxPriorityData b)
{
return a.GetPriority() < b.GetPriority();
}
inline std::ostream &operator<<(std::ostream &out, rxPrio...
{
return out << a.m_fValue << " ";
}
int main(void)
{
rxPriorityData p[] = { rxPriorityData(2, 30.0),
rxPriorityData(5, 10.0),
rxPriorityData(3, 25.0),
rxPriorityData(4, 35.0),
rxPriorityData(1, 15.0) };
priority_queue<rxPriorityData> z(p, p+5);
while(!z.empty()){
cout << z.top();
z.pop();
}
cout << endl;
return 0;
}
}}
実行結果
10 35 25 30 15
終了行:
std::deque,queue,priority_queue
-----
#contents
-----
*deque [#nf3cbe70]
両端キュー(double-ended queue)．値をコンテナの両端から格...
メンバ関数はほぼvectorと同じであり，
先頭への要素の追加，削除用関数があることが異なる．
***インクルード [#h89f568a]
#include <deque>
***先頭への要素の追加，削除(push_front,pop_front) [#lfcce...
-push_front(val) : コンテナの先頭に要素を追加
void push_front(const T& val);
-pop_front() : コンテナの先頭要素を削除
void pop_front();
***vectorとdeque,どちらを使うべきか？ [#q7021b67]
dequeは名前からキューであるように思えるが，実際には任意の...
サポートしていてvectorとよく似ている．
しかし，両コンテナは以下のように操作によってパフォーマン...
-要素アクセス時間 : vector < deque
-コンテナ両端への要素の追加にかかる時間 : deque < vector
-コンテナ中間への要素の追加にかかる時間 : あまり変わらな...
一般的には要素アクセス速度が速いvectorを使えばよいが，両...
また，dequeはメモリ上の非連続領域を用いる場合もあるらしい...
従来の配列との互換性が必要な場合はvectorを用いた方がよい．
*queue [#g62b3c8c]
FIFO(First In First Out)方式のキューとして値を格納する．
dequeを基底としたコンテナアダプタ．
***インクルード [#he9d4889]
#include <queue>
***初期化(コンストラクタ) [#j0d0f7ec]
explicit queue(const Container& ctnr = Container());
***メンバ関数 [#lf020290]
-front() : コンテナの最初の要素にアクセスする関数
value_type& front();
const value_type& front() const;
-back() : コンテナの最後の要素にアクセスする関数
value_type& back();
const value_type& back() const;
-size() : コンテナのサイズを返す関数
size_type size() const;
-empty() : コンテナが空だったらtrueを返す関数．
bool empty () const;
-push(val) : コンテナの最後に要素を追加
void push(const T& val);
-pop() : コンテナの最初の要素を削除
void pop();
使用例
#code(C){{
#include <iostream>
#include <queue>
using namespace std;
int main(void)
{
queue<int> x;
for(int i = 0; i < 5; ++i){
x.push(i);
cout << x.back() << " ";
}
cout << endl;
for(int i = 0; i < 5; ++i){
cout << x.front() << " ";
x.pop();
}
cout << endl;
return 0;
}
}}
実行結果
0 1 2 3 4
0 1 2 3 4
***deque以外のコンテナを用いたqueue [#af9693e5]
queueコンテナアダプタの標準の基底はdequeであるが，
別のコンテナを基底に指定することもできる．
別のコンテナを使用したい場合は，
list<int> l(10, 1);
queue<int, list<int> > q(l);
のようにする．
*priority_queue [#x2df3f89]
優先順位付きのqueue．
クラスのテンプレート仕様は，
template < class T, class Container = vector<T>,
class Compare = less<typename Container::valu...
となっており，
定義時にデータ型，基底コンテナ(デフォルトはvector)，優先...
***インクルード [#k9c98188]
#include <queue>
***初期化(コンストラクタ) [#yf909b8a]
explicit priority_queue(const Compare& x = Compare(),
const Container& y = Container...
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last,
const Compare& x = Compare(),
const Container& y = Container());
***メンバ関数 [#p979d734]
-top() : 優先度が最も高い要素への参照を返す関数
const value_type& top() const;
-size() : コンテナのサイズを返す関数
size_type size() const;
-empty() : コンテナが空だったらtrueを返す関数．
bool empty () const;
-push(val) : キューに要素を追加
void push(const T& val);
-pop() : キューの最初の要素を削除
void pop();
使用例
#code(C){{
#include <iostream>
#include <queue>
using namespace std;
int main(void)
{
string s[] = {"b", "d", "a", "c", "e"};
priority_queue<string> x(s, s+5);
while(!x.empty()){
cout << x.top();
x.pop();
}
cout << endl;
priority_queue<string, vector<string>, greater<string> >...
while(!y.empty()){
cout << y.top();
y.pop();
}
cout << endl;
return 0;
}
}}
実行結果
edcba
abcde
***クラスオブジェクトの優先度付きキュー [#u41dab8e]
intやdoubleなどの組込オブジェクトでは優先順位が既に規定さ...
自身が作成したクラスについてpriority_queueを用いたい場合...
operator<を定義すればよい．
例
#code(C){{
#include <iostream>
#include <queue>
using namespace std;
class rxPriorityData
{
int m_iPriority;
double m_fValue;
public:
rxPriorityData() : m_iPriority(0),m_fValue(0.0) {}
rxPriorityData(int priority, double value) : m_iPriority...
int GetPriority(void) const { return m_iPriority; }
friend std::ostream &operator<<(std::ostream &out, rxPri...
};
inline bool operator<(rxPriorityData a, rxPriorityData b)
{
return a.GetPriority() < b.GetPriority();
}
inline std::ostream &operator<<(std::ostream &out, rxPrio...
{
return out << a.m_fValue << " ";
}
int main(void)
{
rxPriorityData p[] = { rxPriorityData(2, 30.0),
rxPriorityData(5, 10.0),
rxPriorityData(3, 25.0),
rxPriorityData(4, 35.0),
rxPriorityData(1, 15.0) };
priority_queue<rxPriorityData> z(p, p+5);
while(!z.empty()){
cout << z.top();
z.pop();
}
cout << endl;
return 0;
}
}}
実行結果
10 35 25 30 15
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
