2

我有这样的结构，带有 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：按值排序。

4

5 回答 5

6

Astd::map在这种情况下很好，考虑到您将 ID 映射到计数。

备查：

在此处输入图像描述

于 2013-02-12T10:47:42.593 回答
5

您可能想要制作一个结构或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; });
于 2013-02-12T10:54:57.900 回答
1

如果我必须在您建议的使用范围内执行此操作（维护一个键映射以快速更新计数器，然后转储排序结果），我可能会使用无序映射和指针向量。有了这个，我假设您首先需要一些索引键解决方案的主要原因是在更新计数时使数据处理速度显着加快。

换句话说，您希望从执行此操作的代码中获得良好的减速效果：

++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 而不是您的 map 键排序，这同样可以解决问题，尽管它确实会从您的容器中复制数据以实现最终目标：

#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
于 2013-02-12T11:43:03.750 回答
1

我通常通过以下方式进行：

创建两个 int 成员的类/结构

struct int_pair{
     int key;
     int value;
}

然后创建一个

   vector<int_pair> myvector;

然后创建两个布尔比较函数：

 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：对格式感到抱歉。从手机打字。

于 2013-02-12T14:59:56.647 回答
0

您可以简单地使用boost.bimap。理解它需要一点工作，但它的价值，我认为它完全适合你的用例。

于 2013-02-12T11:56:13.493 回答