24と25のリビジョン間の差分
2011-02-16 13:21:40時点のリビジョン24
サイズ: 9848
編集者: y3eadgbe
コメント:
2014-12-07 04:47:10時点のリビジョン25
サイズ: 9810
編集者: y3eadgbe
コメント:
削除された箇所はこのように表示されます。 追加された箇所はこのように表示されます。
行 61: 行 61:
  * 配列のような書き方も出来る(が、atの方が早いらしい)   * 配列のような書き方も出来る

【C++】STL for TopCoder

  • TopCoderを始めて、最初にSTLの使い方でつまづいたので、最低限必要なものを備忘録を兼ねて簡単に解説します

  • コードとコメントをひと通り読めば、大体の使い方が分かる、ということを目指して書いています
  • 間違いなどありましたら指摘をお願いします
  • 詳しい使い方は http://www.cppll.jp/cppreference/ 等のリファレンス参照

更新記録

  • 2011/2/16 algorithmのnext_permutationについて追記
  • 2011/2/2 string ,algorithmについて追記(stringのソート)

目次

vector

  • ある型の値を複数もつ
  • 主な用途
    • 可変長配列として
  • 使い方

   1 #include <iostream>
   2 #include <vector>
   3 using namespace std;
   4 
   5 int main() {
   6         /*
   7          * vector<>の宣言
   8          * 空のvector<>が作られる
   9          */
  10         vector<int> v;
  11 
  12         /*
  13          * 要素の追加
  14          * v.push_back(val)
  15          * vectorの最後尾に値が追加される
  16          */
  17         v.push_back(10);
  18         for (int i = 0; i < 20; i++)
  19         {
  20                 v.push_back(i);
  21         }
  22 
  23         /*
  24          * vectorの要素数
  25          * v.size()
  26          */
  27         cout << "v contains " << v.size() << " integers" << endl;
  28 
  29         /*
  30          * 要素へのアクセス
  31          * v.at(i)
  32          * nのi番目の要素が取り出される
  33          */
  34         int x = v.at(0);
  35         cout << x << endl;
  36 
  37         /*
  38          * 配列のような書き方も出来る
  39          */
  40         for (int i = 1; i < v.size(); i++)
  41         {
  42                 cout << v[i] << " ";
  43         }
  44         cout << endl;
  45         
  46         return 0;
  47 }

string

  • 文字列
  • 主な用途
    • 可変長の文字列として
  • 使い方

   1 #include <iostream>
   2 #include <string>
   3 #include <algorithm>
   4 using namespace std;
   5 
   6 int main() {
   7         /*
   8          * stringの宣言
   9          */
  10         string str;             //空文字列
  11         string str2("Hello World!");    //初期値あり
  12 
  13         /*
  14          * stringの演算子
  15          */
  16         str = "I'm hungry";             //代入
  17         cout << str << endl;
  18 
  19         char ch = str[2];               //要素(char)へのアクセス(str.at(2)でも可)
  20         putchar(ch);
  21         cout << endl;
  22 
  23         str = str + " and thirsty";     //結合(str += " and thirsty"; でも可)
  24         cout << str << endl;
  25 
  26         if (str == str2)        //比較(完全一致)
  27         {
  28                 cout << "str is equal to str2" << endl;
  29         } else {
  30                 cout << "str is NOT equal to str2" << endl;
  31         }
  32 
  33         str = "abc";
  34         str2 = "bac";
  35         if (str < str2)         //比較(辞書順)
  36         {
  37                 cout << "str is less than str2" << endl;
  38         } else {
  39                 cout << "str is NO less than str2" << endl;
  40         }
  41 
  42         /*
  43          * stringの文字数
  44          * str.size()
  45          */
  46         cout << "str contains " << str.size() << " characters" << endl; //str.length()も使える
  47 
  48         /*
  49          * stringのソート(要<algorithm>)
  50          * ASCIIコードでソートされることに注意
  51          */
  52         str = "gfedcbagfedcba";
  53         sort(str.begin(), str.end());
  54         cout << str << endl;
  55 
  56 
  57         /*
  58          * その他、文字列の出現位置の検索、トリムなどの機能もある(詳細は割愛)
  59          */
  60         str = "abcdefg";
  61         str2 = "cde";
  62         cout << "found str2 in str (from index of " << str.find(str2) << ")" << endl;
  63 
  64         cout << str.substr(3,3) << endl;
  65 
  66         return 0;
  67 }

map

  • ある型の値からある型の値への写像
  • 主な用途
    • 連想配列として
  • 使い方

   1 #include <iostream>
   2 #include <string>
   3 #include <map>
   4 using namespace std;
   5 
   6 int main() {
   7         /*
   8          * map<,>の宣言
   9          * 平衡二分木で実装されているらしい(のでけっこう遅い)
  10          */
  11         map<string,int> m;      //空のmap(この場合stringからintへの対応)
  12 
  13         /*
  14          * 要素の追加
  15          * おそらくメソッドを使ったほうが早いが、めんどくさいので[]演算子を使う
  16          */
  17         m["one"] = 1;
  18         m["two"] = 2;
  19         m["three"] = 3;
  20 
  21         /*
  22          * 要素へのアクセス
  23          */
  24         cout << m["two"] << endl;
  25 
  26         /*
  27          * 要素の削除
  28          * m.erase(key);
  29          */
  30         m.erase("one");
  31 
  32         /*
  33          * mapの要素数
  34          * m.size();
  35          */
  36         cout << "m contains " << m.size() << " elements" << endl;
  37 
  38         /*
  39          * 要素の検索
  40          * m.find(key);
  41          * keyが存在しない場合に、mapの最後尾へのイテレータが返ってくるので、
  42          * keyの有無を確認する場合に使える
  43          */
  44         if (m.find("one") == m.end())
  45         {
  46                 cout << "one does not exist as a key" << endl;
  47         }
  48 
  49         /*
  50          * 要素の列挙
  51          * イテレータを使用して、mapの要素を列挙する
  52          */
  53         m["five"] = 5;
  54         m["four"] = 4;
  55         m["ten"] = 10;
  56         m["eight"] = 8;
  57         map<string,int>::iterator it;   //イテレータの宣言
  58         for (it = m.begin(); it != m.end(); ++it)
  59         {
  60                 cout << it->first << " -> " << it->second << endl;      //ポインタのように使う
  61         }
  62 
  63         return 0;
  64 }

stack,queue,priority_queue

  • スタック、キュー、優先度付きキュー
  • 主な用途
    • そのままスタック、キュー、優先度付きキューとして
  • 使い方

   1 #include <iostream>
   2 #include <stack>
   3 #include <queue>
   4 using namespace std;
   5 
   6 int main() {
   7         /**
   8          * stack<>,queue,<>priority_queue<>の宣言
   9          */
  10         stack<int> st;
  11         queue<int> qu;
  12         priority_queue<int> pqu_desc;   //デフォルトでは降順
  13         priority_queue<int, vector<int>, greater<int> > pqu_asc;        //昇順のpriority_queue
  14 
  15         /*
  16          * 要素の追加
  17          * push(val);
  18          */
  19         st.push(1);
  20         st.push(2);
  21         st.push(3);
  22 
  23         qu.push(1);
  24         qu.push(2);
  25         qu.push(3);
  26 
  27         pqu_desc.push(2);
  28         pqu_desc.push(3);
  29         pqu_desc.push(1);
  30 
  31         pqu_asc.push(2);
  32         pqu_asc.push(3);
  33         pqu_asc.push(1);
  34 
  35         /**
  36          * 一番上の要素にアクセス
  37          * st.top();
  38          * qu.front();
  39          * pqu_desc.top();
  40          *
  41          * 一番上の要素を取り除く
  42          * pop();
  43          *
  44          * 要素が空か判定(空ならtrue)
  45          * empty();
  46          */
  47         cout << "stack (First In Last Out)" << endl;
  48         while (!(st.empty()))
  49         {
  50                 cout << st.top() << endl;
  51                 st.pop();
  52         }
  53 
  54         cout << "queue (First In First Out)" << endl;
  55         while (!(qu.empty()))
  56         {
  57                 cout << qu.front() << endl;
  58                 qu.pop();
  59         }
  60 
  61         cout << "priority_queue (DESC)" << endl;
  62         while (!(pqu_desc.empty()))
  63         {
  64                 cout << pqu_desc.top() << endl;
  65                 pqu_desc.pop();
  66         }
  67 
  68         cout << "priority_queue (ASC)" << endl;
  69         while (!(pqu_asc.empty()))
  70         {
  71                 cout << pqu_asc.top() << endl;
  72                 pqu_asc.pop();
  73         }
  74         return 0;
  75 }

algorithm

  • イテレータを使った各種アルゴリズムの実装
  • 主な用途
    • max,min関数、sortなど
  • 使い方

   1 #include <iostream>
   2 #include <vector>
   3 #include <algorithm>
   4 using namespace std;
   5 
   6 int main() {
   7         int array[8]={4,7,1,2,6,5,8,3};
   8         vector<int> v;
   9         for (int i=0; i<8; i++)
  10         {
  11                 v.push_back(array[i]);
  12         }
  13         /**
  14          * min,max関数
  15          */
  16         cout << min(5,10) << endl;
  17         cout << max(5,10) << endl;
  18 
  19         /**
  20          * 区間の中で最大/最小の値のイテレータを返す
  21          * max_element(from, to)
  22          * min_element(from, to)
  23          * 区間の最初のイテレータ(ポインタ)と、最後(ソートする最後の要素の次)のイテレータを指定する。
  24          */
  25         cout << *(max_element(array, array + 8)) << endl;
  26         cout << *(min_element(v.begin(), v.end())) << endl;
  27 
  28         /**
  29          * 値を(破壊的に)ソートする
  30          * sort(from, to(, comp))
  31          * 区間の最初のイテレータと最後のイテレータ(と比較関数のポインタ)を指定する。(デフォルトは昇順)
  32          */
  33         sort(array, array + 8);
  34         cout << "sort array" << endl;
  35         for (int i=0; i<8; i++)
  36         {
  37                 cout << array[i] << " ";
  38         }
  39         cout << endl;
  40 
  41         cout << "sort vector" << endl;
  42         sort(v.begin(), v.end());       //vectorもok
  43         for (int i=0; i<v.size(); i++)
  44         {
  45                 cout << v[i] << " ";
  46         }
  47         cout << endl;
  48 
  49         cout << "sort array (DESC)" << endl;
  50         sort(array, array + 8, greater<int>()); //降順にする
  51         for (int i=0; i<8; i++)
  52         {
  53                 cout << array[i];
  54         }
  55         cout << endl;
  56 
  57         /*
  58          * stringのソート
  59          * ASCIIコードでソートされることに注意
  60          */
  61         cout << "sort string" << endl;
  62         string str = "gfedcbagfedcba";
  63         sort(str.begin(), str.end());
  64         cout << str << endl;
  65 
  66         return 0;
  67 }

next_permutation

  • 順列を生成する関数
  • 使い方

   1 #include <iostream>
   2 #include <vector>
   3 #include <string>
   4 #include <algorithm>
   5 
   6 using namespace std;
   7 
   8 int main(){
   9         /*
  10          * 配列のnext_permutation
  11          * next_permutationを実行すると、配列の中身が辞書順で次の順列になる
  12          * 一番最後の順列でnext_permutationを実行すると、一番初めの順列に戻る
  13          * その際の関数の返り値だけfalseであるので、次のようにして全順列を列挙できる
  14          */
  15         int arr[3]={0,1,2};
  16         do {
  17                 cout << arr[0] << "," << arr[1] << "," << arr[2] << endl;
  18         } while (next_permutation(arr ,arr + 3));
  19         cout << endl;
  20 
  21         /*
  22          * vectorのnext_permutation
  23          */
  24         vector<int> v;
  25         for (int i=0; i<3; i++)
  26         {
  27                 v.push_back(i);
  28         }
  29         do {
  30                 cout << v[0] << "," << v[1] << "," << v[2] << endl;
  31         } while (next_permutation(v.begin() ,v.end()));
  32         cout << endl;
  33 
  34         /*
  35          * stringのnext_permutation
  36          */
  37         string str="ABC";
  38         do {
  39                 cout << str << endl;
  40         } while (next_permutation(str.begin() ,str.end()));
  41 
  42         return 0;
  43 }


Category読み物

y3eadgbe/【C++】STL for TopCoder (最終更新日時 2014-12-07 04:47:10 更新者 y3eadgbe)