Хороший алгоритм для преобразования карты STL в отсортированный список ключей, основанный на числовом значении

Question

У меня есть карта STL, которая имеет тип:

map<Object*, baseObject*>

где

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

Если бы я хотел вернуть список объектов (std::list

Answer 1

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

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 Предпочтительно, когда вы не собираетесь итерировать по нему, и если вам нужна гарантия того, что указатели и итераторы останутся действительными после изменения списка.

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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