• ベストアンサー

件数が少ない場合のSTLのmapかvectorの選択

mapは検索は早いと聞いていますが、 件数が少ない場合にvectorで１から順番に検索する方法とどれくらいの差が発生するのでしょうか

質問者が選んだベストアンサー

  • ベストアンサー
回答No.1

件数をNとすると、vectorの時間計算量はO(N), mapはO(logN)です。 が、Nが小さい時は大差ありません。

ritomo
質問者

お礼

そうですか、参考になりました。 回答ありがとうございました。

その他の回答 (1)

  • jacta
  • ベストアンサー率26% (845/3158)
回答No.2

件数が少ないと行っても実際にどのくらいなのか、使用する処理系（および使用するライブラリ）、そしてコンパイルオプション等で実行速度は変わってきます。正確なことは実測してみるしかないでしょう。

ritomo
質問者

お礼

そうですね、測定してみます。ありがとうございました

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • STL MAPのキー

    ３種類のキーを持ったデータの検索をしたいのですが、 mapで実現する場合、どんな方法があるのでしょうか キー int A、キー int B、キー string C、VOL=クラスX 検索はA,B,Cでそれぞれ行うとした場合、以下のようなmapのtypedefを３種類設定することになるのでしょうか？ map<int, クラスX> aa; map<int, クラスX> bb; map<string, クラスX> cc; これですと削除がする場合には３箇所mapを修正するひつようがありますので１箇所で処理でしないのでしょうか？

  • STLのmapについて

    いつもお世話になっております。 今回はmapについてお聞きしたいです。 現在mapを使っていますが、mapを構造体に入れようと struct PARAM { 　　int　　i; 　　char　 str; 　　map<int, int>　　map; }； のようにしていますが、<が不正です、のようなことを言われてうまくいきません。 構造体にmapを入れることは可能なのでしょうか？ 可能ならばその方法を教えていただけると幸いです。 以上、ご教授願います。 環境は　OS WindowsXP SP2 VC++6.0 です。

  • ベクターマップの矢印の向きについて．．．

    ベクターマップの矢印の向きについて．．． 最近分子生物学を習い始めた者です。ベクターマップについて質問です。マップ上の逆向きになった矢印はどういった意味で、何を示しているんですか？とても初歩的なことで恐縮ですがどうかご教授ください。

  • サイトマップの最大件数はどのくらいですか？

    よろしくお願いします。 GoogleやYahoo!向けのサイトマップをxmlで作成しています。 自動的に作るプログラムで行っているのですが、けっこう大きなサイトなのでサイトマップ内に記載されるURLの数が4万件にもなってしまいました。 こんなに長いサイトマップをアップロードして大丈夫でしょうか。 長すぎるでしょうか？ 最大件数などご存知の方がいらっしゃいましたら教えてください。

  • map(stl)の引数を知りたい

    C++です。 map <int, int> i; により、整数→整数のmapを作ったとします。 そのときに、引数の整数値の最小値を知りたいのですが、 簡単な方法はありますか？ perlで言うところの、$ARGV[0]です。

  • vectorの中にmap

    vectorの中にmapを入れて 添字：ノードID [どのノードから来たのか｜それまでのコスト] を表現しようと考えています． #include<iostream> #include<vector> #include<map> #include<list> // MACROS #define UNDEF -1 // PROTOTYPE DCLARE void init_path(std::vector<std::map<char, int> >, int size); int main(void) { //source -> source node // //size -> the number of node // //path -> store path infomation // ex: // path[1]: 1 is node id // char : from node id // cost : how cost from source to here // //adj -> show adjacency list eace node int source; int size; std::vector<std::map<char, int> > path; std::vector<std::list<char> > adj; size = 5; std::cout << "before" << std::endl; init_path(path, size); std::cout << "after" << std::endl; std::map<char, int>::iterator it; for(int i = 0; i < size; i++) { it = path[i].begin(); // std::cout << it->first << ":" << it->second << std::endl; } return 0; } void init_path(std::vector<std::map<char, int> > path, int size) { std::map<char, int> init; init.insert( std::map<char, int>::value_type('-', UNDEF) ); for(int i = 0; i < size ; i++) { path.push_back(init); } return; } ＊結果 before after Segmentation fault となり初期化をする所までは正常に動いたっぽいのですが どこが悪いのかわかりません（おそらくイテレータあたりかと思うのですが・・・・ 具体的にどうしたらいいのか分からないのでご指導ねがいます．

  • STLのvectorの削除

    STLのvectorの削除を行う場合に vector<myclass> v; ・・・ v.erase(it); ・・・ というように削除するiteratorを渡しますが、 任意のインデックスのvectorを削除した場合は、 どのようにそのiteratorを取得するのでしょうか。 例えばｖ[5]を削除したのですが、 vector<myclass>::iterator it=v.begin(); for(int i=0;i<5;i++) it++; v.erase(it); というbegin()やend()からのインクリメント・デクリメントで取得するしかないのでしょうか？ ご教示願います。

  • VectorなどSTL?テンプレートの使い方

    戻り値がポインタの場合、関数から抜け出すと値の保証が無いので、それを使用する場合は、変数にコピーして使うと値は残る（アクセス可能）と理解しています。 char tmp[128]; strcpy(tmp, test()); それで、次のような vector??を使った場合、表示の場合は問題ないかもしれませんが、その後、値を使い続ける場合、ポインタのままでよいのか疑問に思っています。 以下のソースは勝手気ままに記述したものですが、 VC++6でエラーなく動作（とりあえず動く）しているのですが、今後発生する問題など知りたいです。 #include "stdafx.h" #include <string> #include <iostream> #include <vector> #include <sstream> using namespace std; class A { string str; vector<A *> v_cls; public: A(){ } // デフォルトコンストラクタが必要？ A(string s){ str = s; } void PrintData(void){ // 表示 cout << str << endl; } // １から９までの[0]-[9]の文字列を作成 vector<A *> ArraySet(void){ stringstream ss; for (int i=0; i < 10; i++){ ss.str(""); ss << "function [" << i << "]\n"; v_cls.push_back( new A( ss.str() ) ); } return v_cls; } }; void main(void){ // １から９までの[0]-[9]の文字列を作成 // これは問題ないと思う vector<A *> v; stringstream ss; for (int i=0; i < 10; i++){ ss.str(""); ss << "[" << i << "]\n"; v.push_back( new A( ss.str() ) ); } v[1]->PrintData(); v[3]->PrintData(); ////cout << v.size(); // クラス自身にvector配列？を返す処理 // とりあえず動いているだけ？？？ A x; vector<A *> ret = x.ArraySet(); // このような代入でも問題ないのでしょうか？ ret[5]->PrintData(); // 表示だけなので、問題なし？ ret[0]->PrintData(); // vやret, xの解放仕方とタイミングはどうすればよいのでしょうか？ }

  • グーグルマップをベクタライズしてCADに取り込みたい。

    グーグルマップをベクタライズしてCADに取り込みたい。 私は建築関係のものです。 基本的にautoCADに敷地図を取り込んでなぞっています。 しかし、広範囲になると面倒なので、wintopoのような画像をベクタライズするソフトを使おうと思いました。 地図はグーグルマップや、ＧＩＳのものを使用しています。 2階調化してwintopoに取り組むのですが、元の地図がグレーの部分がかなりあったりするのでんかなかうまくいきません。 コンペに提出したりするので、きれいに取り込みたいです。 建築関連の方は特にどうしているのか教えていただけるとありがたいです。 うまくいく方法をおしえてください！！

  • STL mapでアクセス違反

    VC++2005 Express Editionを使用しています。 （Platform SDKを別途インストールしています。） STL mapの変数を宣言すると、その部分でアクセス違反が発生します。 これだけのコードも動きません。 #include <map> using namespace std; int main() { map<int, int> m; m.insert(pair<int, int>(0,10)); return 0; } グローバル宣言するれば、実行直後に止まります。 なにか対策があればよろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する