Хороший алгоритм для превращения карты stl в отсортированный список ключей на основе числового значения.

Что бы я сделал, это сначала извлечь ключи (поскольку вы хотите только вернуть их) в вектор, а затем отсортировать это:

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

Если ваш компилятор не поддерживает лямбда-выражения, просто перепишите их как свободные функции или объекты функций. Я просто использовал лямбды для краткости.

Для производительности я бы, вероятно, изначально reserve имел достаточно места в векторе, вместо того, чтобы позволить ему постепенно расширяться.

(Также обратите внимание, что я не тестировал код, поэтому, возможно, потребуется немного повозиться)

Кроме того, я не знаю, что должна представлять эта карта, но наличие карты, где и ключ, и тип значения являются указателями, на самом деле вызывает покалывание в моем «плохом C++». Пахнет ручным управлением памятью и запутанной (или несуществующей) семантикой владения.

Вы упомянули получение вывода в list, но vector почти наверняка является более эффективным вариантом, поэтому я использовал его. Единственная ситуация, когда list предпочтительнее, - это когда вы не собираетесь когда-либо перебирать его, и если вам нужна гарантия того, что указатели и итераторы останутся действительными после изменения списка.

Во-первых, я бы использовал не 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 вам нужно будет создавать функторы вместо лямбда-выражений, и если вы настаиваете на возврате 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;
                } );

Опять же, это может быть быстрее или медленнее, чем исходная версия... профиль.

Я думаю, вы справитесь с:

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

Вот как сделать то, что вы сказали, "отсортировать по порядку 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*), так что вам нужно будет перебирать карту только один раз, не нужно искать что-то. Отсортируйте пары, затем поместите второй элемент каждой пары в список. Это может быть преждевременной оптимизацией, но на практике это эффективный трюк.

Я бы создал новую карту с критерием сортировки, в котором использовался идентификатор компонента ваших объектов. Заполните вторую карту из первой карты (просто выполните итерацию или std::copy). Затем вы можете прочитать эту карту по порядку, используя итераторы.

Это имеет небольшие накладные расходы с точки зрения вставки по сравнению с использованием вектора или списка (логарифмическое время (n) вместо постоянного времени), но позволяет избежать необходимости сортировки после того, как вы создали вектор или список, что приятно.

Кроме того, вы сможете добавить к нему больше элементов позже в своей программе, и он будет поддерживать свой порядок без необходимости прибегать.

Я не уверен, что полностью понимаю, что вы пытаетесь сохранить на своей карте, но, возможно, посмотрите здесь

Третий аргумент шаблона std::map — функтор less. Возможно, вы можете использовать это для сортировки данных, хранящихся на карте при вставке. Тогда это будет прямой цикл на итераторе карты для заполнения списка