Как я могу эффективно заказать карту по стоимости?

Рассмотрим std::map<K,V>, Я хочу переупорядочить карту по значению прибыли в соответствующем контейнере std::C<V*> или же std::C<V&>таким образом, чтобы не было никаких копий значений для хранения элементов в C. Кроме того, элементы в C должны быть отсортированы в соответствии с результатом int f(V&) применяется к каждому элементу. Несмотря на мои усилия, я не смог найти подходящий C и достаточно эффективный способ его построения. У вас есть какое-нибудь решение? Небольшой пример будет высоко ценится.

Источник

6 ответов

Решение

Кажется достаточно простым.

std::map<K,V> src;
int f(V&) {return 0;}

V* get_second(std::pair<const K,V> &r) {return &(r.second);} //transformation
bool pred(V* l, V* r) { return f(*l)<f(*r); }   //sorting predicate

std::vector<V*> dest(src.size());  //make destination big enough
std::transform(src.begin(), src.end(), dest.begin(), get_second); //transformcopy
std::sort(dest.begin(), dest.end(), pred); //sort

Если вы не имели в виду, что C должен быть другой картой:

std::pair<K,V*> shallow_pair(std::pair<const K,V> &r) 
{return std::pair<K,V*>(r.first, &(r.second));}

std::map<K, V*> dest2;
std::transform(src.begin(), src.end(), 
               std::inserter(dest2,dest2.end()), shallow_pair);

http://ideone.com/bBoXq

Это требует, чтобы предыдущая карта оставалась в области действия дольше, чем destи не имеют пар, удаленных до dest разрушен. Иначе src нужно будет иметь какие-то умные указатели.

Источник

Ты можешь использовать std::reference_wrapper, как это:

#include <map>
#include <string>
#include <algorithm>
#include <functional>

#include <prettyprint.hpp>
#include <iostream>

template <typename T>
std::ostream & operator<<(std::ostream & o, std::reference_wrapper<T> const & rw)
{
  return o << rw.get();
}

int main()
{
  std::map<int, std::string> m { { 1, "hello"}, { 2, "aardvark" } };
  std::cout << m << std::endl;

  std::vector<std::reference_wrapper<std::string>> v;
  for (auto & p : m) v.emplace_back(p.second);
  std::cout << v << std::endl;

  std::sort(v.begin(), v.end(), std::less<std::string>); // or your own predicate
  std::cout << v << std::endl;

  v.front().get() = "world";
  std::cout << m << std::endl;
}

Это печатает:

[(1, hello), (2, aardvark)]
[hello, aardvark]
[aardvark, hello]
[(1, hello), (2, world)]
Источник

Похоже, вы используете несколько контейнеров для представления нескольких представлений в одном наборе данных. Проблема с этим подходом состоит в том, чтобы синхронизировать контейнеры и избежать проблем с указателями. Boost.MultiIndex был сделан именно для этой цели. boost::multi_index Контейнер хранит только одну копию каждого элемента, но позволяет получить доступ к элементам через несколько индексов.

Пример:

#include <iterator>
#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/global_fun.hpp>
#include <boost/multi_index/member.hpp>

typedef std::string Key;
typedef int Value;

struct Record
{
    Record(const Key& key, Value value) : key(key), value(value) {}
    Key key;
    Value value;
};

inline std::ostream& operator<<(std::ostream& os, const Record& rec)
{
    os << rec.key << " " << rec.value << "\n";
    return os;
}

inline int sortFunc(const Record& rec) {return -rec.value;}

struct ByNumber{}; // tag

namespace bmi = boost::multi_index;
typedef bmi::multi_index_container<
  Record,
  bmi::indexed_by<
    // sort by key like a std::map
    bmi::ordered_unique< bmi::member<Record, Key, &Record::key> >,

    // sort by less<int> on free function sortFunc(const Record&)
    bmi::ordered_non_unique<bmi::tag<ByNumber>, 
                            bmi::global_fun<const Record&, int, &sortFunc> >
  > 
> RecordSet;

typedef RecordSet::index<ByNumber>::type RecordsByNumber;

int main()
{
    RecordSet rs;
    rs.insert(Record("alpha", -1));
    rs.insert(Record("charlie", -2));
    rs.insert(Record("bravo", -3));

    RecordsByNumber& byNum = rs.get<ByNumber>();

    std::ostream_iterator<Record> osit(std::cout);

    std::cout << "Records sorted by key:\n";
    std::copy(rs.begin(), rs.end(), osit);

    std::cout << "\nRecords sorted by sortFunc(const Record&):\n";
    std::copy(byNum.begin(), byNum.end(), osit);
}

Результат:

Записи отсортированы по ключу:
альфа -1
браво -3
Чарли -2

Записи отсортированы по sortFunc(const Record&):
альфа -1
Чарли -2
браво -3
Источник

Я бы начал с того, что:

  • посмотрите на Boost:: BIMAP
  • создайте упорядочение из V -> K через объект функции сравнения, который оценивает f(V&), как вы предложили. (например, как в std::map<K,V,C> где С - класс компаратора)
Источник

Как насчет чего-то вроде этого (непроверенный псевдокод):

V* g(pair<K,V> &v) { return &v.second; }
bool cmp(V* a, V* b) { return f(*a) < f(*b); }

map<K,V> map;
vector<V*> vec;
vec.reserve(map.size());
transform(map.begin(), map.end(), back_inserter(vec), g);
sort(vec.begin(), vec.end(), cmp);
Источник

Как насчет,

std::set<boost::shared_ptr<V>, compfunc>

где compfunc - это функтор, который принимает два объекта shared_ptr и применяет логику в вашей функции?

Извините за форматирование, не очень хорошо на моем телефоне.

Источник
Другие вопросы по тегам