идиоматический C ++ для создания std :: vector из последних n элементов std :: map - PullRequest
Новая
       24

идиоматический C ++ для создания std :: vector из последних n элементов std :: map

4 голосов
/ 22 февраля 2012

Что такое идиоматический способ C ++ для создания std :: vector из последних n элементов std :: map?

Меня не интересует сохранение порядка в векторе.

Я могу скопировать элементы следующим образом: 

    std::map< double, MyType > m;
    size_t n = 3;
    std::vector< MyType > v;
    std::map< double, MyType >::iterator it = m.end();
    while ( n-- ) { // assuming m.size() >= n
        it--;
        v.push_back(it->second);
    }

Но есть ли другой способ, более идиоматический, сделать это?

Ответы [ 6 ]

5 голосов
/ 22 февраля 2012

std::copy подойдет, если вы хотите скопировать типы без изменений. Однако std::map<T,U>::iterator_type::value_type - это не U (тип, который вы хотите скопировать), а std::pair<T,U> (другими словами, разыменование итератора карты дает пару типов ключ и значение), поэтому необработанная копия не будет работа.

Итак, нам нужно скопировать элементы, выполняя преобразование по пути. Вот для чего std::transform.

Для удобства я собираюсь предположить, что ваш компилятор поддерживает лямбда-выражения C ++ 11 и ключевое слово auto. В противном случае это может быть довольно тривиально переписано как функтор. Но мы ищем что-то вроде этого: 

std::transform(map_first, map_last, std::back_inserter(vec), [](std::pair<double,MyType> p) { return p.second; });

Теперь нам просто нужно заполнить два первых параметра: 

auto map_first = std::next(map.end(), -n); 
auto map_last = map.end();

Единственная сложность здесь заключается в том, что итераторы карты являются двунаправленными, но не произвольным доступом, поэтому мы не можем просто сказать map.end() - n. Оператор - не определен. Вместо этого мы должны использовать std::next (для двунаправленных операторов требуется линейное, а не постоянное время, но обходного пути нет).

(обратите внимание, я не пробовал компилировать этот код, поэтому может потребоваться небольшая настройка)

4 голосов
/ 22 февраля 2012

std::transform будет самым идиоматическим способом. Вам нужен функционал объект: 

template<typename PairType>
struct Second
{
    typename PairType::second_type operator()( PairType const& obj ) const
    {
        return obj.second;
    }
}

(Если вы много работаете с std::map или другими вещами, которые используют std::pair, вы будете иметь это в своем наборе инструментов.)

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

std::vector<MyType>
extractLastN( std::map<double, MyType> const& source, size_t n )
{
    std::vector<MyType> results;
    std::transform( source.begin(), source.end(),
                    std::back_inserter( results ),
                    Second<std::map<double, MyType>::value_type>() );
    if ( results.size() > n ) {
        results.erase( results.begin(), results.end() - n );
    }
    return results;
}

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

std::vector<MyType>
extractLastN( std::map<double, MyType> const& source, ptrdiff_t n )
{
    std::map<double, MyType>::const_iterator start
            = source.size() <= n
                ? source.begin()
                : std::prev( source.end(), n );
    std::vector<MyType> results;
    std::transform( start, source.end(),
                    std::back_inserter( results ),
                    Second<std::map<double, MyType>::value_type>() );
    return results;
}

(Если у вас нет доступа к C ++ 11, std::prev это просто: 

template<typename IteratorType>
IteratorType
prev( IteratorType start, ptrdiff_t n )
{
    std::advance( start, -n );
    return start;
}

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

3 голосов
/ 22 февраля 2012

Вот простая версия Boost.Range: 

#include <boost/range/iterator_range_core.hpp>
#include <boost/range/adaptor/map.hpp>
//#include <boost/range/adaptor/reversed.hpp> // comment in for 'reversed'
#include <map>
#include <vector>

struct X{};

int main(){
  std::map<int, X> m;
  unsigned n = 0;
  auto vec(boost::copy_range<std::vector<X>>(
    boost::make_iterator_range(m, m.size()-n, 0)
    | boost::adaptors::map_values
    //| boost::adaptors::reversed // comment in to copy in reverse order
  ));
}
2 голосов
/ 22 февраля 2012

Один из способов сделать это - использовать for_each: 

    map<int,double> m;
    vector<double> v;
    //Fill map
    auto siter = m.end();
    advance(siter, -3);
    for_each(siter, m.end(), [&](pair<int,double> p) { v.push_back(p.second); });

EDIT Еще более простой способ - использовать std::prev с for_each: 

    map<int,double> m;
    vector<double> v;
    //Fill map
    for_each(prev(m.end(), 3), m.end(), 
                  [&](pair<int,double> p) { v.push_back(p.second); });

Также, если вы хотите заполнить вектор в обратном порядке, вы можете использовать: 

for_each(m.rbegin(), next(m.rbegin(), 3), 
        [&](pair<int,double> p) { v.push_back(p.second); });
0 голосов
/ 22 февраля 2012

Во-первых, что мы хотим написать, чтобы быть идиоматическими? Я предлагаю: 

std::vector<Mytype> v;
v.reserve(n);
std::transform(
  limited(n, m.rbegin()), 
  limited_end(m.rend()),
  std::back_inserter(v),
  values_from(m)
);

Теперь нам нужно сделать этот код действительным.

Мы можем заменить values_from(m) на лямбду (которая не нуждается в m) или реализовать ее, используя класс Джеймса Канзе Second (в этом случае m используется для вывода типа): 

template <typename Map>
Second<Map::value_type> values_from(const Map &) {
    return Second<Map::value_type>();
}

Реализация limited немного болезненна. Это шаблонная функция, которая возвращает итератор. Тип итератора, который он возвращает, является шаблоном, который оборачивает другой тип итератора и передает ему все, кроме того, что он отслеживает n и действует как конечный итератор, когда он был продвинут n раз. limited_end возвращает конечный итератор того же типа, поэтому он сравнивается равным или , если базовые итераторы равны, или , если один из итераторов был создан с limited_end и другой побежал n до нуля.

У меня нет кода для этого, но в основном вы получаете _n эквивалентов всех стандартных алгоритмов, а не только copy_n. В этом случае нам нужно transform_n, но его нет.

Альтернативой transform будет использование copy_n с boost::transform_iterator, обернутым вокруг m.rbegin(). Я не буду здесь этого делать, потому что мне всегда нужно проверять документы, чтобы использовать transform_iterator.

0 голосов
/ 22 февраля 2012

Сделай это задом наперед: 

assert(n <= m.size());
std::copy(m.rbegin(), m.rbegin()+n, std::back_inserter(v));

двунаправленные итераторы FTW.

Хорошо, я, очевидно, еще не проснулся, и это было желаемое за действительное. Я все еще предпочитаю идти назад, чтобы получить последние n, поэтому рабочая версия выглядит так: 

#include <map>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

// I'm assuming it's ok to copy min(m.size(), n)
template <typename Iter>
Iter safe_advance(Iter begin, Iter const &end, int distance)
{
    while(distance-- > 0 && begin != end)
        ++begin;
    return begin;
}

void copy_last_n(map<double,int> const &m,
                 vector<int> &v, int n)
{
    transform(m.rbegin(), safe_advance(m.rbegin(), m.rend(), n),
              back_inserter(v),
              [](map<double,int>::value_type const &val)
              {
                return val.second;
              }
             );
}

Джеймс Канзе уже написал функтор Second - используйте его, если у вас нет доступа к лямбдам.

...