c++ - 重新排序 C++ 基于映射的集合的有效方法

Question

我有一个大的(大约 ->100K)集合，将用户标识符(一个整数)映射到他们购买的不同产品的数量(也是一个整数)。我需要尽可能高效地重新组织数据可以找出有多少用户拥有不同数量的产品。例如，有多少用户拥有 1 种产品，有多少用户拥有两种产品等。

我通过将原始数据从 std::map 反转为 std::multimap 来实现这一点(其中键和值被简单地反转了。)我然后可以使用 count(N) 找出拥有 N 产品的用户数量(尽管我也将这些值唯一地存储在一个集合中，因此我可以确定确切的数量我正在迭代的值及其顺序)

代码如下所示:

// uc is a std::map<int, int> containing the  original
// mapping of user identifier to the count of different
// products that they've bought.
std::set<int> uniqueCounts;
std::multimap<int, int> cu; // This maps count to user.

for ( map<int, int>::const_iterator it = uc.begin();
        it != uc.end();  ++it )
{
    cu.insert( std::pair<int, int>( it->second, it->first ) );
    uniqueCounts.insert( it->second );
}

// Now write this out
for ( std::set<int>::const_iterator it = uniqueCounts.begin();
        it != uniqueCounts.end();  ++it )
{
    std::cout << "==> There are "
            << cu.count( *it ) << " users that have bought "
            << *it << " products(s)" << std::endl;
}

我只是觉得这不是最有效的方法。有人知道这样做的巧妙方法吗？

我的局限在于我不能使用 Boost 或 C++11 来执行此操作。

哦，还有，以防万一有人想知道，这既不是作业，也不是面试题。

Answer 1

假设您知道单个用户可以购买的最大产品数量，您可能会发现仅使用 vector 来存储操作结果会获得更好的性能。实际上，您将需要为原始 map 中的几乎每个条目进行分配，这可能不是最快的选择。

它还会减少 map 上的查找开销，获得内存局部性的好处，并用 vector 的恒定时间查找替换对多重映射(这不是恒定时间操作)的计数调用。

所以你可以这样做:

std::vector< int > uniqueCounts( MAX_PRODUCTS_PER_USER );

for ( map<int, int>::const_iterator it = uc.begin();
        it != uc.end();  ++it )
{
    uniqueCounts[ uc.second ]++;
}

// Now write this out
for ( int i = 0, std::vector< int >::const_iterator it = uniqueCounts.begin();
        it != uniqueCounts.end();  ++it, ++i )
{
    std::cout << "==> There are "
            << *it << " users that have bought "
            << i << " products(s)" << std::endl;
}

即使您不知道产品的最大数量，您似乎也可以猜测最大值并根据需要调整此代码以增加 vector 的大小。无论如何，它肯定会导致比您的原始示例更少的分配。

当然，所有这些都是假设您在处理完这些数据后实际上不需要用户 ID(正如下面的评论中指出的那样，为每个用户购买的产品数量相对较小 &连续集。否则你最好使用 map 代替 vector - 你仍然会避免调用 multimap::count 函数，但可能会失去一些其他好处)