2012/10/20

C++で2種類のコンテナを同時にソートする

C++でデータを扱っていると,2種類のコンテナを同時にソートしたい場合が時々出てくる.どういうことかというと,
int main() {
    int keys[]   = {5, 3, 1, 2, 4};
    int values[] = {1, 2, 3, 4, 5};
    aoba::sort_by_key(keys, keys+5, values);
    for(int i=0; i<5; ++i) {
        std::cout << keys[i] << " ";   // 1 2 3 4 5
    }
    std::cout << std::endl;
    for(int i=0; i<5; ++i) {
        std::cout << values[i] << " "; // 3 4 2 5 1
    }
    std::cout << std::endl;
    return 0;
}
と,片方のソート結果を元にもう片方をソートするような感じ.これはCUDAライブラリであるthrustに標準搭載されており,sort_by_keyという名前がついている.

さて,こういうときに一からソートアルゴリズムを組み直すなんてことは馬鹿らしい.じゃあどうするか.基本的には既存のstd::sortに渡すイテレータを変形することで,なんとか解決しようとする.そうなると,boostにzip_iteratorが存在することに気付けば,イテレータをboost::tupleの組で表現することによって,まとめてソートさせればいいような気がしてくる.こんな風に:
std::sort(
    boost::make_zip_iteator(
        boost::make_tuple(
            keys_first, values_first)),
    boost::make_zip_iterator(
        boost::make_tuple(
            keys_last, values_last)),
    compare_functor());
しかし,そうは問屋が降ろさない.何故なら,boost::zip_iteratorはWritableではない.これはソートアルゴリズムの要件を満たしていないため,適用させようとしてもコンパイルエラーが発生してしまう!

それじゃあどのようにして解決するかというと,一番楽な方法としてはWritableなコンセプトを満たしたzipイテレータを新しく作ってやって,それを用いてstd::sortを行うのがいい.とはいっても,C++でそれをやるのは若干手間のかかる作業になる.具体的にはこんな感じで実装した:
実装したといっても,実際には『Sorting two arrays simultaneously』の内容を若干手直しするだけなので基本的にはそんなに大変じゃないし,ただ利用するぶんには単純にsort_by_key()を呼び出すだけでよい.

しかし,なんでこんなにC++は行数が多くなってしまうのか.haskellなんか一行で済むのに.

3 件のコメント:

ark adobe ramp さんのコメント...

misleading tutorial perhaps, like all others, do not emphasize that key is stored along with value inside a hash table at the hash index rather than only storing the value. This leads to people being confused how collisions get resolved, since buckets and probe sequences cannot be disambiguated without knowing the key to match against(to search for the value). A bucket with 100 values or a hash table with 10000 values 10 of which are the same probe sequence collision cannot be disambiguated without knowing the key. This may seem obvious to some, and completely impossible to wrap their mind around to others(since they have not been told this explicitly). You're welcome that confused guy from 2017.

eu4 console commands さんのコメント...

I couldn't get the 'rand' function to work, it kept telling me it hadn't been defined. I googled, and found that I needed to add #include . I'm not sure why yours worked fine without it and mine didn't, but I thought I'd share in case anyone else was having this issue.

carb cycling meal plan pdf|Carb Cycling: A Daily Meal Plan to Get Started – Daily Burn さんのコメント...

It seems like some people (or just a couple), are getting a little confused about why you need to have an Object before and a Class. Maybe this explanation will help:

To start off a Class is what makes up the Object, the class gives the Object it's functions and tells the Object what it can do. For example, if you were building a house lets say, the class would be the blue print to that house. It would say where all of the infrastructure would be, the water pipes, etc... However, you cannot live in a blueprint, and that blue print is not actually a house. The actually Object would be the house, and that house's physical appearance would be based on the blueprint (Class). So once again, for example, lets say I wanted to make a Dog object, and this Object would essentially draw a 2D image of a dog on the screen. You would first have to create a Class and in that Class is where you would specify things like how tall the dog would be, what colour certain parts of the dog are, where on the screen the dog is located. Then, the actual process of making an Object would allow my dog Object to be created, and allow me to have a picture of a dog on my screen.

So, one might still be asking, "Okay, but why did the people at Microsoft still make us create an Object? Why can't C++ just look at the class we made and think 'Well, that person made a class, so he obviously wants to use it as an Object, so I'll just create it into an Object' ". Here's the thing, the reason why you go about and type what you want to call you're object (The variable name of you're object), is because if you created more than 1 Object from the same class, you could differentiate between one or another. Imagine if I wanted to make 2 dogs appear on the screen, so I try using the Dog Object (as mentioned before) twice. And lets also assume that C++ will simply just make the class into an Object so we can just type out Dog.drawOnScreen, or something of the sort if you wanted to draw a dog on the screen. Well, here's the thing, you would essentially end up drawing those two dogs you wanted, on the exact same location of the screen. You probably couldn't make them different colours, couldn't give them each a different hight, so essentially, it would look like you just had one dog on the screen because they are virtually identical and are over lapping each other. Now, lets say that instead, we had to create our own Objects, so something like: Dog dogFred; and Dog dogAl (I'm creating 2 Dog Objects. One is called dogFred, the other dogAl (These are just some dog names)). Now, lets say that you wanted to call a function from one of the Dog Objects that would change its location to the upper-lefthand corner of the screen (In this case, dogAl). You could type dogAl.move(topLeftOfScreen) (Or something along those lines). In the past, if you tried to move you're second Dog Object, it would essentially affect both Object's location, but now, only the dogAl Object will move relocated and dogFred will stay put. Now imagine if you wanted 10 Dog Objects, you can now control each individuals location, colour, height, maybe even breed if you wanted to incorporate that.