stlにおけるアルゴリズムの使い方
最近 stdのalgorithmの使い方を理解する必要があるプログラムの練習問題に出会いました。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2242
リンク先の問題です。
1 年号の名前と年号が続いた年数と終わった年のデータを読み込みます。
2 年を入力されるとそれに対応した年号を返す
というシンプルな問題(誤読してなければですが)です。
解くだけなら簡単なのですが、どうせなら勉強と思い、ＳＴＬ特有のfindなどのアルゴリズムを使って解こうと思ったのですが、アルゴリズム関係は初めて使うのでどう書いたらいいかわからない状態です。
書きかけのプログラムはこちらです。
http://www14.atwiki.jp/c21coterie/?
cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=2242EraName2.txt
年号データを保存したクラスのあるvectorから、STLのアルゴリズムを使いバイナリサーチで対応する年号を見つけたいのです。
ＳＴＬのアルゴリズムを使うとしてどのような記述が好ましいのでしょうか？
根本的に方法が間違ってるならその峰ご指摘お願いします。
vector内に西暦順に並べておいて lower_bound あたりで検索できそうです。
返答ありがとうございます。
lower_boundを使う方法が分からなかったので、自分でわかる簡単な方法で解いてしまいました。
うーん、この問題0.0012秒で解いたのですが、私よりも早くしかも欠片もメモリを全く使わないで解いている人がいます。
高速化する方法がわかりませんでした。
もしかして単純に端から見た方が早い（？＿？）のかな。
どうやってメモリ確保を抑えたのかかなり疑問です。
最速の人は単純に配列のバイナリサーチだろうか。
とりあえずlower_boundの検索基準となる関数オブジェクト(であってるかな)の作り方や使い方をお教えいただけたらと思います。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=2242EraName3.txt
すいませんリンク張り間違えました。
一般的には
1.専用コードよりSTLの方が遅い
2.専用コードよりSTLの方がメモリを多く消費する
です。STLは汎用コードなので当然ですね。
> とりあえずlower_boundの検索基準となる関数オブジェクト(であってるかな)の作り方や使い方をお教えいただけたらと思います。
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
/*
果物を価格の順に並べたとき、200円のリンゴはどこに納まるか
*/
struct fruit {
string name;
int price;
fruit(string n, int p) : name(n), price(p) {}
};
int main() {
vector<fruit> fruits;
fruits.push_back(fruit("すいか", 500));
fruits.push_back(fruit("いちご", 400));
fruits.push_back(fruit("みかん", 100));
fruits.push_back(fruit("メロン", 800));
fruits.push_back(fruit("バナナ", 150));
// 価格順に並べるための比較関数オブジェクト
auto comp = [](const fruit& x, const fruit& y) { return x.price < y.price; };
// coutにfruitを書く関数オブジェクト
auto print = [](const fruit& f) { cout << f.name << '(' << f.price << ") ";};
// 価格順に並べ、
sort(fruits.begin(), fruits.end(), comp);
// リンゴの位置を求める
fruit target("リンゴ",200);
auto position = lower_bound(fruits.begin(), fruits.end(), target, comp);
for_each( fruits.begin(), position, print);
cout << "の次に ";
print(target);
cout << "そして ";
for_each( position, fruits.end(), print);
}
ありがとうございます。
ＢＣＣではコンパイルできなかったので自分なりに修正して理解してみました。
| ツイート |  |