0

我有一个类型为 stl 的地图：

map<Object*, baseObject*>

在哪里

class baseObject{
    int ID;
    //other stuff
};

如果我想返回一个对象列表（std::list< Object* >），那么按照 baseObject.ID 的顺序对其进行排序的最佳方法是什么？

我只是一直在寻找每个数字或其他东西吗？我不想将地图更改为提升地图，尽管我不一定反对做一些自包含在返回函数中的事情，比如

GetObjectList(std::list<Object*> &objects)
{
   //sort the map into the list
}

编辑：也许我应该遍历并将 obj->baseobj 复制到 baseobj.ID->obj 的映射中？

4

6 回答 6

2

我要做的是首先将键（因为您只想返回它们）提取到向量中，然后对其进行排序：

std::vector<baseObject*> out;
std::transform(myMap.begin(), myMap.end(), std::back_inserter(out), [](std::pair<Object*, baseObject*> p) { return p.first; });
std::sort(out.begin(), out.end(), [&myMap](baseObject* lhs, baseObject* rhs) { return myMap[lhs].componentID < myMap[rhs].componentID; });

如果您的编译器不支持 lambda，只需将它们重写为自由函数或函数对象。我只是为了简洁而使用 lambdas。

为了性能，最初我可能会reserve在向量中留出足够的空间，而不是让它逐渐扩展。

（另请注意，我没有测试代码，所以它可能需要一点点摆弄）

另外，我不知道这个映射应该代表什么，但是持有一个键和值类型都是指针的映射确实让我的“糟糕的 C++”感觉刺痛。它闻起来有手动内存管理和混乱（或不存在）的所有权语义的味道。

您提到在 a 中获取输出list，但 avector几乎可以肯定是一个性能更好的选项，所以我使用了它。a 更可取的唯一情况list是，当您不打算对其进行迭代时，并且如果您需要保证指针和迭代器在修改列表后保持有效。

于 2012-05-24T17:47:22.270 回答
1

这是您所说的“按baseObject.ID的顺序对其进行排序”的方法：

typedef std::map<Object*, baseObject*> MapType;
MapType mymap; // don't care how this is populated
               // except that it must not contain null baseObject* values.

struct CompareByMappedId {
    const MapType &map;
    CompareByMappedId(const MapType &map) : map(map) {}
    bool operator()(Object *lhs, Object *rhs) {
        return map.find(lhs)->second->ID < map.find(rhs)->second->ID;
    }
};

void GetObjectList(std::list<Object*> &objects) {
    assert(objects.empty()); // pre-condition, or could clear it
    // or for that matter return a list by value instead.

    // copy keys into list
    for (MapType::const_iterator it = mymap.begin(); it != mymap.end(); ++it) {
        objects.push_back(it->first);
    }
    // sort the list
    objects.sort(CompareByMappedId(mymap));
}

这并不是非常有效：它在映射中的查找比严格必要的要多，并且在其中操作列表节点std::list::sort可能比std::sort在操作指针的随机访问容器时要慢一些。但是，std::list对于大多数用途而言，它本身并不是很有效，因此您预计设置一个会很昂贵。

如果您需要优化，您可以创建一个成对的向量(int, Object*)，这样您只需遍历地图一次，无需查找。对这些对进行排序，然后将每对的第二个元素放入列表中。这可能是一个过早的优化，但它在实践中是一个有效的技巧。

于 2012-05-24T18:10:45.677 回答
1

我认为你会做得很好：

GetObjectList(std::list<Object*> &objects)
{
  std::vector <Object*> vec;
  vec.reserve(map.size());
  for(auto it = map.begin(), it_end = map.end(); it != it_end; ++it)
    vec.push_back(it->second);
  std::sort(vec.begin(), vec.end(), [](Object* a, Object* b) { return a->ID < b->ID; });
  objects.assign(vec.begin(), vec.end());
}
于 2012-05-24T17:45:30.943 回答
1

第一件事是我不会使用 a std::list，而是使用 a std::vector。现在对于特定问题，您需要执行两个操作：生成容器，根据您的标准对其进行排序。

// Extract the data:
std::vector<Object*> v;
v.reserve( m.size() );
std::transform( m.begin(), m.end(), 
                std::back_inserter(v),
                []( const map<Object*, baseObject*>::value_type& v ) {
                     return v.first;
                } );
// Order according to the values in the map
std::sort( v.begin(), v.end(), 
           [&m]( Object* lhs, Object* rhs ) {
               return m[lhs]->id < m[rhs]->id;
           } );

如果没有 C++11，您将需要创建仿函数而不是 lambda，如果您坚持返回 a，std::list那么您应该使用std::list<>::sort( Comparator ). 请注意，这可能效率低下。如果性能是一个问题（在你得到这个工作并且你分析并知道这实际上是一个瓶颈之后）你可能需要考虑使用中间map<int,Object*>：

std::map<int,Object*> mm;
for ( auto it = m.begin(); it != m.end(); ++it )
   mm[ it->second->id ] = it->first;
}
std::vector<Object*> v;
v.reserve( mm.size() );                  // mm might have less elements than m!
std::transform( mm.begin(), mm.end(), 
                std::back_inserter(v),
                []( const map<int, Object*>::value_type& v ) {
                     return v.second;
                } );

同样，这可能比原始版本...配置文件更快或更慢。

于 2012-05-24T17:49:15.250 回答
0

我不确定我是否完全理解您要在地图中存储的内容，但也许请看这里

std::map 的第三个模板参数是一个 less 函子。也许您可以利用它在插入时对存储在地图中的数据进行排序。然后它将是地图迭代器上的直接循环来填充列表

于 2012-05-24T18:02:52.543 回答
0

我将创建一个新地图，该地图具有使用对象的组件 ID 的排序标准。从第一个映射填充第二个映射（只需迭代或 std::copy in）。然后您可以使用迭代器按顺序阅读此地图。

与使用向量或列表（log(n) 时间而不是常数时间）相比，这在插入方面有一点开销，但它避免了在创建向量或列表之后进行排序的需要，这很好。

此外，您稍后可以在程序中向其添加更多元素，并且无需使用手段即可维持其顺序。

于 2012-05-24T17:45:07.107 回答