好的算法把STL的地图变成基于数值

Question

我有一个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的映射中？

Answer 1

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

这对于使用向量或列表（log（n）时间而不是常量时间）的插入有轻微的开销，但它避免了在创建好的向量或列表之后进行排序的需要。

此外，您可以在稍后的程序中添加更多元素，并且它将保持其顺序而不需要度假村。

Answer 2

我想你会做罚款：

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()); 
} 

Answer 3

我会做的是先提取键（因为你只想要回那些）为载体，然后那种：

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; }); 

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

对于性能，我最初可能会在向量中有足够的空间，而不是让它逐渐扩大。

（另请注意，我没有测试过的代码，因此它可能需要摆弄了一点点）

而且，我不知道这是什么地图是要象征，而是拿着地图，键和值类型都是指针真的设置我的“坏C++”感刺痛。它闻到手动内存管理和混乱（或不存在）所有权语义。

您提到在list中获得输出，但vector几乎肯定是更好的选择，因此我使用了该选项。唯一的情况是list是最好的，当你无意迭代它时，以及如果需要保证指针和迭代器在修改列表后保持有效。

Answer 4

首先，我不会使用std::list，而是使用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表达式，如果您在返回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; 
       }); 

同样，这可能比更快或更慢原始版本...个人资料。

Answer 5

我不知道我完全理解你想在你的地图存储什么，但也许look here

性病的第三个模板参数::地图是一个不太仿函数。也许你可以利用它来对存储在地图上的数据进行排序。那么这将是一个map迭代器直向前循环来填充列表

Answer 6

这里是如何做到你所说的，“在顺序排序它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)); 
} 

这ISN” t绝对有效率：它在地图中查找的次数比绝对必要的要多，并且操作std::list::sort中的列表节点可能比std::sort稍微慢一些，它们将操纵随机存取指针容器。但是，对于大多数用途而言，std::list本身并不是非常有效，所以你期望它的设置昂贵。

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