c++ - 保存と並べ替えに使用するのに適したデータ構造構造？

Question

私はIDとその数を持つそのような構造を持っています:

product[38] = 10;
product[22] = 7;
product[39] = 18;

そのために何らかの構造を使用する必要があります。しかし、何がより良いサービスを提供するべきかわからない ( map, unordered_map, set, vector)。

私は使用しようとしていました：

map<int, int> product;

しかし、それが最良の選択かどうかはわかりません。私がそれですべき唯一のことは、並べ替えです。

その結果、次のものが必要です。

product[39] = 18;
product[38] = 10;
product[22] = 7;

UPD:値で並べ替えます。

score 6 · Accepted Answer

std::mapID をカウントにマッピングしていることを考えると、この場合はAで問題ありません。

今後の参考のために：

ここに画像の説明を入力

score 5 · Accepted Answer

構造体またはstd::pairを作成し、それらをstd::vectorに格納したい場合があります

std::vector<std::pair<int, int>> product;

product.push_back(std::pair<int,int>(38, 27));
product.push_back(std::pair<int,int>(22, 7));
product.push_back(std::pair<int,int>(39, 18));

値でソート:

std::sort(product.begin(), product.end(), 
  [](const std::pair<int,int>& p1, const std::pair<int,int>& p2){ return p1.second < p2.second; });

score 1 · Accepted Answer

提案された使用法の範囲内でこれを行う必要がある場合 (カウンターをすばやく更新するためにキーマップを維持し、並べ替えられた結果をダンプする)、順序付けられていないマップとポインターベクトルを使用する可能性があります。これにより、最初にいくつかのインデックス付きキーソリューションが必要な主な理由は、カウントの更新時にデータ処理を大幅に高速化することであると想定しています。

言い換えれば、これを行うコードから適切なスピードバンプを得ようとしているということです。

++product[ id ]; // increment counter for product 'id' in our keyed-container.

ただし、ID ではなく、各 ID の累積カウントでソートされた出力をレポートすることはできます。そうは言っても、次の例は少し複雑ですが、まさにそれを行います。

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <unordered_map>
#include <iterator>
#include <iomanip>
using namespace std;

int main(int argc, char *argv[])
{
    typedef std::unordered_map<int, int> Products;
    Products product;

    // fill with random data for our test.
    std::srand((unsigned)time(0));
    for (int i=1;i<20;++i)
    {
        product[i] = rand() % 50 + 1;
        cout << setw(3) << i << " ==> " << product[i] << endl;
    }
    cout << endl;


    // now setup a one-shot sort. we're using a vector of
    //  pointers to our map value type
    std::vector<const Products::value_type*> data;
    data.reserve(product.size());
    std::transform(product.begin(), product.end(), std::back_inserter(data),
                   [](const Products::value_type& obj) { return std::addressof(obj); });

    // sort the vector by value (second)
    std::stable_sort(data.begin(), data.end(),
                     [](const Products::value_type* left, const Products::value_type* right)
                     { return left->second < right->second; });

    // results are in the vector as pointers. the original map is unchanged.
    for (auto ptr : data)
        cout << setw(3) << ptr->first << " ==> " << ptr->second << endl;

    return EXIT_SUCCESS;
};

サンプルラン

  1 ==> 42
  2 ==> 18
  3 ==> 35
  4 ==> 1
  5 ==> 20
  6 ==> 25
  7 ==> 29
  8 ==> 9
  9 ==> 13
 10 ==> 15
 11 ==> 6
 12 ==> 46
 13 ==> 32
 14 ==> 28
 15 ==> 12
 16 ==> 42
 17 ==> 46
 18 ==> 43
 19 ==> 28
 20 ==> 37

  4 ==> 1
 11 ==> 6
  8 ==> 9
 15 ==> 12
  9 ==> 13
 10 ==> 15
  2 ==> 18
  5 ==> 20
  6 ==> 25
 14 ==> 28
 19 ==> 28
  7 ==> 29
 13 ==> 32
  3 ==> 35
 20 ==> 37
  1 ==> 42
 16 ==> 42
 18 ==> 43
 12 ==> 46
 17 ==> 46

私は過去にこの方法を使用しました。これは、並べ替えのために一時的なコンテナーにコピーするのにコストがかかる、より複雑な構造の場合に非常に効率的であるためです。最後のポインタベクトルがマップ内の実際のデータを参照するということは、この特定の問題に対してはやり過ぎかもしれませんが、一般的な解決策として確かにメリットがあります。

そうは言っても、必要なのが int-to-int ダンプであり、マップキーではなく second-int でソートされている場合、これも同様にうまくいきますが、最終目標を達成するためにコンテナーからデータをレプリケートします。 :

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <unordered_map>
#include <iterator>
#include <iomanip>
using namespace std;

int main(int argc, char *argv[])
{
    typedef std::unordered_map<int, int> Products;
    Products product;

    // fill with random data for our test.
    std::srand((unsigned)time(0));
    for (int i=1;i<20;++i)
    {
        product[i] = rand() % 50 + 1;
        cout << setw(3) << i << " ==> " << product[i] << endl;
    }
    cout << endl;

    // copy the values from the map to a sort bed.
    std::vector<std::pair<int,int>> vals;
    std::copy(product.begin(), product.end(), back_inserter(vals));
    std::stable_sort(vals.begin(), vals.end(),
        [](const std::pair<int,int>& left, const std::pair<int,int>& right)
        { return left.second < right.second; });

    // dump to stdout
    for (auto val : vals)
        cout << setw(3) << val.first << " ==> " << val.second << endl;

    return EXIT_SUCCESS;
}

サンプル出力

  1 ==> 48
  2 ==> 30
  3 ==> 25
  4 ==> 32
  5 ==> 34
  6 ==> 21
  7 ==> 26
  8 ==> 6
  9 ==> 50
 10 ==> 28
 11 ==> 50
 12 ==> 32
 13 ==> 35
 14 ==> 17
 15 ==> 33
 16 ==> 30
 17 ==> 13
 18 ==> 1
 19 ==> 50

 18 ==> 1
  8 ==> 6
 17 ==> 13
 14 ==> 17
  6 ==> 21
  3 ==> 25
  7 ==> 26
 10 ==> 28
  2 ==> 30
 16 ==> 30
  4 ==> 32
 12 ==> 32
 15 ==> 33
  5 ==> 34
 13 ==> 35
  1 ==> 48
  9 ==> 50
 11 ==> 50
 19 ==> 50

score 1 · Accepted Answer

私は通常、次の方法で行います。

2 つの int メンバーのクラス/構造体を作成する

struct int_pair{
     int key;
     int value;
}

次に作成します

   vector<int_pair> myvector;

次に、2 つの bool 比較関数を作成します。

 bool sort_by_key(int_pair left, int_pair right){
      return left.key<right.key;
 }

 bool sort_by_value(int_pair left, int_pair right){
     return left.value<right.value;
 }

次に、std::sort とそれらの bool 関数を使用して並べ替えます。

 std::sort (myvector.begin(), myvector.end(), sort_by_key);

ps: フォーマットについて申し訳ありません。携帯から入力。

score 0 · Accepted Answer

単にboost.bimapを使用できます。それを理解するのは少し手間がかかりますが、その価値と私はそれがあなたのユースケースにぴったり合っていると思います。

c++ - 保存と並べ替えに使用するのに適したデータ構造構造？

5 に答える 5

Related

Reference