標準テンプレートライブラリ(STL)使用---vector
9940 ワード
C++を主なプログラミング言語としてTopCoderの問題を解決しているかもしれません.これは、配列と文字列がSTLオブジェクトとして関数に渡されるため、STLを簡単に使用したことを意味します.多くのプログラマーがコードを書くのがあなたよりずっと速く、簡潔であることに気づいたかもしれません.
C++プログラム猿になりたいわけではないかもしれませんが、このプログラミング言語の機能が強く、豊富なライブラリがあるからです(TopCoderの練習室やコンテストで非常にシンプルなソリューションをたくさん見たからかもしれません).
過去にかかわらず、この文章は役に立つだろう.ここでは、標準テンプレートライブラリ(Standard Template Library-STL、アルゴリズムコンテストで多くの時間を節約できる非常に有用なツール)のいくつかの強力な特性をレビューします.
STLに慣れるには、容器から始めるのが一番簡単です.
ようき
大量の要素を操作する必要がある場合でも、あるコンテナが使用されます.C言語には内蔵コンテナが1つしかありません.配列です.
問題は、配列に限界があることではありません(たとえば、実行時に配列サイズを決定することはできません).逆に、問題は主に多くのタスクがより強力なコンテナを必要としていることです.
たとえば、次の操作を1つ以上必要とします.
もちろん,これらの機能は通常の配列で実現できる.しかし、これらの些細な実現は非常に効果的ではありません.ツリー構造またはハッシュ構造を作成して問題を迅速に解決できますが、このコンテナの実装は、保存する要素のタイプに依存しますか?たとえば、文字列ではなく平面上の点を格納するには、このモジュールを書き直して機能を実現する必要がありますか?
そうでなければ、このコンテナのインタフェースを開発し、どのデータ型でも使用することができます.簡単に言えば、これがSTL容器の考え方です.
前言
プログラムがSTLを使用する場合は、適切な標準ヘッダファイル(#include)を含める必要があります.ほとんどのコンテナでは、標準ヘッダファイルの名前はコンテナ名と一致し、拡張子は必要ありません.たとえば、スタックを使用する場合は、プログラムの先頭に次の行のコードを追加します.
コンテナタイプ(アルゴリズム、演算子、すべてのSTLも同様)は、グローバルネーミングスペースではなく、stdという特殊なネーミングスペースで定義されます.すべてのヘッダファイルを含む後、コードを書く前に次の行を追加します.
コンテナタイプもテンプレートパラメータであることを覚えておいてください.テンプレートパラメータは、コードに「かっこ」(<'/'>')で指定します.例:
ネストされた構造を行う場合は、「かっこ」の間にスペースを残す位置が隣接していないことを確認します.(翻訳者:C++11新しいプロパティは、スペースを追加する必要がなくなり、2つのカッコの間に隣接することをサポートします)
一、Vector
最も簡単なSTL容器はvectorです.Vectorは拡張機能を持つ配列にすぎません.ちなみに、vectorはCコードを後方に互換性のある唯一のコンテナです.これは、vectorが実際に配列であり、いくつかの追加の特性を持っていることを意味します.
Vectorで最もよく使われる特性は、コンテナサイズを取得することです
まずsize()関数が返す値が符号なしであることに注意してください.この点はいくつかの問題を引き起こすことがあります.次に、コンテナが空かどうかを知りたい場合は、vectorのsize()の戻り値を0と比較するのは良い方法ではありません.empty()関数を使ったほうがいいです.
もう一つのvectorでよく使われる関数はpush_ですback.push_back関数はvectorの末尾に要素を追加し、コンテナの長さに1を追加します.次の例を考えてみましょう.
メモリ割り当ての問題を心配しないでください.vectorは一度に1つの要素の空間だけを割り当てません.逆に毎回push_backが新しい要素を追加すると、vectorが割り当てるメモリ領域は常に実際に必要とするよりも多くなります.あなたが心配すべき唯一のことはメモリの使用状況です.
vectorのサイズを変更する必要がある場合はresize()関数を使用します.
Resize()関数はvectorに必要な数の要素だけを格納させる.必要な要素の数がvectorが現在格納している数より少ない場合、残りの要素は削除されます.vectorを大きくする必要がある場合は、この関数を使用しても長さを拡大し、新しく作成した要素を0で埋めます.
注意、resize()を使用した後にpush_を使用した場合back()では、新しく追加された要素は、新しく割り当てられたメモリに格納されるのではなく、新しい割り当てられたメモリの後ろに配置されます.上記の例で得られたvectorサイズは25であり、2サイクル目でpush_を使用するとback()は、vectorのサイズが最後に30になります.
結果:
clear()関数を使用してvectorを空にします.この関数はvectorに0要素を含ませる.すべての要素の値を0にするわけではありません.注意してください.すべての要素を完全に削除し、空のコンテナになります.
vectorにデータを追加する最も簡単な方法はpush_を使用することです.back().しかし、もし私たちが末尾以外の場所にデータを追加したいなら?Insert()関数はこの目的を達成することができる.要素を削除するerase()関数もあります.しかし、私たちはまず反復器について話さなければなりません.
もう一つの重要なことを覚えておく必要があります.vectorがパラメータとして関数に渡されると、実際にはこのvector(つまり値伝達)がコピーされます.そうする必要がないときに新しいvectorを作成するには、多くの時間とメモリがかかります.実際には、vectorをパラメータとして渡すときにコピーするタスクを見つけるのは難しい.だから、いつまでもそう書かないでください.
代わりに、次のコンストラクションメソッド(リファレンス伝達)を使用します.
関数でvectorの要素値を変更する場合は、「const」修飾子を削除します.
C++プログラム猿になりたいわけではないかもしれませんが、このプログラミング言語の機能が強く、豊富なライブラリがあるからです(TopCoderの練習室やコンテストで非常にシンプルなソリューションをたくさん見たからかもしれません).
過去にかかわらず、この文章は役に立つだろう.ここでは、標準テンプレートライブラリ(Standard Template Library-STL、アルゴリズムコンテストで多くの時間を節約できる非常に有用なツール)のいくつかの強力な特性をレビューします.
STLに慣れるには、容器から始めるのが一番簡単です.
ようき
大量の要素を操作する必要がある場合でも、あるコンテナが使用されます.C言語には内蔵コンテナが1つしかありません.配列です.
問題は、配列に限界があることではありません(たとえば、実行時に配列サイズを決定することはできません).逆に、問題は主に多くのタスクがより強力なコンテナを必要としていることです.
たとえば、次の操作を1つ以上必要とします.
, 。
もちろん,これらの機能は通常の配列で実現できる.しかし、これらの些細な実現は非常に効果的ではありません.ツリー構造またはハッシュ構造を作成して問題を迅速に解決できますが、このコンテナの実装は、保存する要素のタイプに依存しますか?たとえば、文字列ではなく平面上の点を格納するには、このモジュールを書き直して機能を実現する必要がありますか?
そうでなければ、このコンテナのインタフェースを開発し、どのデータ型でも使用することができます.簡単に言えば、これがSTL容器の考え方です.
前言
プログラムがSTLを使用する場合は、適切な標準ヘッダファイル(#include)を含める必要があります.ほとんどのコンテナでは、標準ヘッダファイルの名前はコンテナ名と一致し、拡張子は必要ありません.たとえば、スタックを使用する場合は、プログラムの先頭に次の行のコードを追加します.
#include<stack>
コンテナタイプ(アルゴリズム、演算子、すべてのSTLも同様)は、グローバルネーミングスペースではなく、stdという特殊なネーミングスペースで定義されます.すべてのヘッダファイルを含む後、コードを書く前に次の行を追加します.
using namespace std;
コンテナタイプもテンプレートパラメータであることを覚えておいてください.テンプレートパラメータは、コードに「かっこ」(<'/'>')で指定します.例:
vector<int> N;
ネストされた構造を行う場合は、「かっこ」の間にスペースを残す位置が隣接していないことを確認します.(翻訳者:C++11新しいプロパティは、スペースを追加する必要がなくなり、2つのカッコの間に隣接することをサポートします)
vector<vector<int> > CorrectDefinition;
vector<vector<int>> WrongDefinition;
//Wrong: compiler may be confused by 'operator >>'
一、Vector
最も簡単なSTL容器はvectorです.Vectorは拡張機能を持つ配列にすぎません.ちなみに、vectorはCコードを後方に互換性のある唯一のコンテナです.これは、vectorが実際に配列であり、いくつかの追加の特性を持っていることを意味します.
vector<int> v(10); // ’v’ 10 vector<int> ,
// , vector<int> v vector
for(int i = 0; i < 10; i++) {
v[i] = (i+1)*(i+1);
cout<<v[i]<<endl;
}
for(int i = 9; i > 0; i--) {
v[i] -= v[i-1];
}
Vectorで最もよく使われる特性は、コンテナサイズを取得することです
int elements_count = v.size()
まずsize()関数が返す値が符号なしであることに注意してください.この点はいくつかの問題を引き起こすことがあります.次に、コンテナが空かどうかを知りたい場合は、vectorのsize()の戻り値を0と比較するのは良い方法ではありません.empty()関数を使ったほうがいいです.
もう一つのvectorでよく使われる関数はpush_ですback.push_back関数はvectorの末尾に要素を追加し、コンテナの長さに1を追加します.次の例を考えてみましょう.
vector<int> v1;
for(int i=1; i<10; i *= 2)
{
v1.push_back(i);//
}
for(unsigned int i=0; i<v1.size(); i++)
{
cout<<v1[i]<<endl;//
}
メモリ割り当ての問題を心配しないでください.vectorは一度に1つの要素の空間だけを割り当てません.逆に毎回push_backが新しい要素を追加すると、vectorが割り当てるメモリ領域は常に実際に必要とするよりも多くなります.あなたが心配すべき唯一のことはメモリの使用状況です.
vectorのサイズを変更する必要がある場合はresize()関数を使用します.
vector<int> v(20);
for(int i=0; i<20; i++)
{
v[i]=i+1;
}
v.resize(25);// vector
for(int i=20; i<25; i++)
{
v[i] = i*2;
}
Resize()関数はvectorに必要な数の要素だけを格納させる.必要な要素の数がvectorが現在格納している数より少ない場合、残りの要素は削除されます.vectorを大きくする必要がある場合は、この関数を使用しても長さを拡大し、新しく作成した要素を0で埋めます.
注意、resize()を使用した後にpush_を使用した場合back()では、新しく追加された要素は、新しく割り当てられたメモリに格納されるのではなく、新しい割り当てられたメモリの後ろに配置されます.上記の例で得られたvectorサイズは25であり、2サイクル目でpush_を使用するとback()は、vectorのサイズが最後に30になります.
int main()
{
vector<int> v(20);
for(int i=0; i<20; i++)
{
v[i]=i+1;
}
v.resize(25); /////////////
for(int i=20; i<25; i++)
{
v.push_back(i);/////////////////
}
for(unsigned int i=0; i<v.size(); i++)
{
cout<<v[i]<<" ";
}
cout<<endl<<v.size()<<endl;
return 0;
}
結果:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 0 0 0 0 20 21 22 23 24
30 // 30
clear()関数を使用してvectorを空にします.この関数はvectorに0要素を含ませる.すべての要素の値を0にするわけではありません.注意してください.すべての要素を完全に削除し、空のコンテナになります.
vectorにデータを追加する最も簡単な方法はpush_を使用することです.back().しかし、もし私たちが末尾以外の場所にデータを追加したいなら?Insert()関数はこの目的を達成することができる.要素を削除するerase()関数もあります.しかし、私たちはまず反復器について話さなければなりません.
もう一つの重要なことを覚えておく必要があります.vectorがパラメータとして関数に渡されると、実際にはこのvector(つまり値伝達)がコピーされます.そうする必要がないときに新しいvectorを作成するには、多くの時間とメモリがかかります.実際には、vectorをパラメータとして渡すときにコピーするタスクを見つけるのは難しい.だから、いつまでもそう書かないでください.
void some_function(vector<int> v) //
{
//Never do it unless you’re sure what you do!
}
代わりに、次のコンストラクションメソッド(リファレンス伝達)を使用します.
void some_function(const vector<int> &v) //!!!!!!
{
//OK//...
}
関数でvectorの要素値を変更する場合は、「const」修飾子を削除します.
int modify_vector(vector<int> &v)
{ //Correct
V[0]++;
}