У меня есть карта STL, которая имеет тип:
map<Object*, baseObject*>
где
class baseObject{ int ID; //other stuff };
Если бы я хотел вернуть список объектов (std::list), как лучше отсортировать его в порядке baseObject.ID?Я просто застрял, просматривая каждый номер или что-то? Я бы предпочел не менять карту на буст-карту, хотя я бы не был против того, чтобы делать что-то, что содержалось в возвращаемой функции, напримерGetObjectList(std::list<Object*> &objects) { //sort the map into the list } Редактировать: может быть, я должен перебрать и скопировать obj->baseobj в карту baseobj.ID->obj? 0 algorithm sorting stl map c++03 Источник Поделиться user371862 24 май '12 в 17:30 2012-05-24 17:30 2012-05-24 17:30 6 ответов Сначала я извлеку ключи (поскольку вы хотите только вернуть их) в вектор, а затем отсортируйте их: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 Предпочтительно, когда вы не собираетесь итерировать по нему, и если вам нужна гарантия того, что указатели и итераторы останутся действительными после изменения списка. 2 Источник Поделиться user33213 24 май '12 в 17:47 2012-05-24 17:47 2012-05-24 17:47 Я думаю, что вы будете в порядке с: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()); } 1 Источник Поделиться user100724 24 май '12 в 17:45 2012-05-24 17:45 2012-05-24 17:45 Первое, что я бы не использовал 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; } ); Опять же, это может быть быстрее или медленнее, чем в оригинальной версии... профиля. 1 Источник Поделиться user36565 24 май '12 в 17:49 2012-05-24 17:49 2012-05-24 17:49 Вот как сделать то, что вы сказали, "отсортировать по порядку 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 ↦ 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*), так что вам нужно только итерировать по карте один раз, не нужно искать вещи. Сортируйте пары, затем поместите второй элемент каждой пары в список. Это может быть преждевременной оптимизацией, но на практике это эффективный прием. 1 Источник Поделиться user13005 24 май '12 в 18:10 2012-05-24 18:10 2012-05-24 18:10 Я хотел бы создать новую карту, которая имела бы критерий сортировки, который использовал бы идентификатор компонента ваших объектов. Заполните вторую карту из первой карты (просто выполните итерацию или std::copy in). Затем вы можете прочитать эту карту по порядку, используя итераторы.Это имеет небольшие издержки с точки зрения вставки по сравнению с использованием вектора или списка (log(n) вместо постоянного времени), но позволяет избежать необходимости сортировки после создания вектора или списка, что является хорошим.Кроме того, вы сможете добавить больше элементов к нему позже в вашей программе, и он будет поддерживать свой порядок без необходимости прибегать к помощи. 0 Источник Поделиться user857994 24 май '12 в 17:45 2012-05-24 17:45 2012-05-24 17:45 Я не уверен, что полностью понимаю, что вы пытаетесь сохранить на своей карте, но, возможно, посмотрите здесьТретий аргумент шаблона std::map является менее функтором. Возможно, вы можете использовать это для сортировки данных, хранящихся на карте при вставке. Тогда это будет простой цикл на итераторе карты для заполнения списка 0 Источник Поделиться user1325084 24 май '12 в 18:02 2012-05-24 18:02 2012-05-24 18:02 Другие вопросы по тегам algorithm sorting stl map c++03
Я просто застрял, просматривая каждый номер или что-то? Я бы предпочел не менять карту на буст-карту, хотя я бы не был против того, чтобы делать что-то, что содержалось в возвращаемой функции, например
GetObjectList(std::list<Object*> &objects) { //sort the map into the list }
Редактировать: может быть, я должен перебрать и скопировать obj->baseobj в карту baseobj.ID->obj?
Сначала я извлеку ключи (поскольку вы хотите только вернуть их) в вектор, а затем отсортируйте их:
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 сначала достаточно места в векторе, вместо того, чтобы позволить ему постепенно расширяться.
reserve
(Также обратите внимание, что я не тестировал код, поэтому может потребоваться немного возиться)
Кроме того, я не знаю, что эта карта должна представлять, но наличие карты, в которой указатели и ключ, и тип значений являются указателями, действительно вызывает ощущение "плохого C++". Пахнет ручным управлением памятью и запутанной (или несуществующей) семантикой владения.
Вы упомянули получение вывода в list, но vector почти наверняка более эффективный вариант, поэтому я использовал это. Единственная ситуация, когда list Предпочтительно, когда вы не собираетесь итерировать по нему, и если вам нужна гарантия того, что указатели и итераторы останутся действительными после изменения списка.
list
vector
Я думаю, что вы будете в порядке с:
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()); }
Первое, что я бы не использовал std::list, а скорее std::vector, Теперь, что касается конкретной проблемы, вам нужно выполнить две операции: сгенерировать контейнер, отсортировать его по вашим критериям.
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::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; } );
Опять же, это может быть быстрее или медленнее, чем в оригинальной версии... профиля.
Вот как сделать то, что вы сказали, "отсортировать по порядку 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 ↦ 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 сам по себе не очень эффективен для большинства целей, поэтому вы ожидаете, что его установка будет дорогой.
std::list::sort
std::sort
Если вам нужно оптимизировать, вы можете создать вектор пар (int, Object*), так что вам нужно только итерировать по карте один раз, не нужно искать вещи. Сортируйте пары, затем поместите второй элемент каждой пары в список. Это может быть преждевременной оптимизацией, но на практике это эффективный прием.
(int, Object*)
Я хотел бы создать новую карту, которая имела бы критерий сортировки, который использовал бы идентификатор компонента ваших объектов. Заполните вторую карту из первой карты (просто выполните итерацию или std::copy in). Затем вы можете прочитать эту карту по порядку, используя итераторы.
Это имеет небольшие издержки с точки зрения вставки по сравнению с использованием вектора или списка (log(n) вместо постоянного времени), но позволяет избежать необходимости сортировки после создания вектора или списка, что является хорошим.
Кроме того, вы сможете добавить больше элементов к нему позже в вашей программе, и он будет поддерживать свой порядок без необходимости прибегать к помощи.
Я не уверен, что полностью понимаю, что вы пытаетесь сохранить на своей карте, но, возможно, посмотрите здесь
Третий аргумент шаблона std::map является менее функтором. Возможно, вы можете использовать это для сортировки данных, хранящихся на карте при вставке. Тогда это будет простой цикл на итераторе карты для заполнения списка