1

我已经定义了这样的地图

typedef   std::vector< int > aVector;
typedef std::map< int, aVector > aMap;
aMap theMap;

假设地图最终包含一些像这样的元素

10 [0 3 7] size=3
12 [40 2 30 3 10] size=5
20 [5 10] size=2
25 [6] size=1

我想对向量的大小进行排序（例如 theMap->second.size()）。所以结果将是

5 3 2 1

最快的方法是什么？基本思想是将大小推到另一个向量上，然后调用 sort()，像这样

aVector v, sorted;
aMap::iterator it = theMap.begin();
for (; it != theMap.end(); ++it) {
  v.push_back(it->second.size());
}
// using std sort!!

有没有更好的选择？

4

3 回答 3

1

当您需要快速查找std::map或std::hash_map以特定顺序管理它时，有一项非常常见的任务。在这种情况下，您可以在主集合上使用一种“索引”集合： 

aMap theMap;
std::map<size_t, std::list<aMap::iterator> > sizes;

// add item
auto r = theMap.insert(key, std::vector<int>());
if (!r->second)
{
    sizes[r->first->second.size()].remove(r->first);
}
r->first->second->push_back(item);
sizes[r->first->second.size()].push_back(r->first);
于 2013-06-23T20:07:56.783 回答
1

为什么不将向量作为键并使用自定义键比较函数/仿函数来比较键大小？

您可以在http://www.cplusplus.com/reference/map/map/map/中看到这样的示例？

我现在还没有使用 C++ 编译器，但它会是这样的：

#include <map>

struct aComparisonStruct {
    bool operator() (const aVector& lhs, const aVector& rhs) const {
        return lhs.size > rhs.size;
    }
};

int main () {
    typedef std::vector<int> aVector;
    typedef std::map<aVector, int, aComparisonStruct> aMap;

    // Use your map

    return 0;
}

但是有一个问题：您不能再使用单键存在的属性，并且您将无法多次添加相同的向量。也许另一种实现会更合适？

此外，使用指针作为键肯定会更好，但由于我无法编译，我不想混淆指针和引用并给你一些可能不起作用的东西。

于 2013-06-23T19:13:30.320 回答
0

标准排序声明如下：

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

所以你可以传入一个comp：

struct comp {
    bool operator() (const aVector& lhs, const aVector& rhs) {
      return (lhs.size() < rhs.size());
    }
} mycomp;

std::sort(theMap, comp)

请注意，最好将 comp 作为输入传递，而不是在声明地图时修复它。在这种情况下，当您只想更改组合时，您不必声明不同的地图。

于 2013-06-23T19:26:11.360 回答