Разделение диапазона на поддиапазоны

У меня есть контейнер std::vector, и я хотел бы эффективно разделить его на поддиапазоны с x элементами в каждом. Исходный контейнер не нужен, поэтому элементы следует перемещать, а не копировать в поддиапазоны.

Мне удалось выполнить разделение с помощью копирования, однако я не уверен, как это сделать с помощью перемещений?

    range.insert(range.end(), new_items.begin(), new_items.end());
    while(range.size() >= x)
    {
        sub_ranges.push_back(std::vector<int>(range.begin(), range.begin() + x));
        range = std::vector<int>(range.begin() + x, range.end());
    }

РЕДАКТИРОВАТЬ:

Некоторый прогресс ... все еще не совсем там, и немного уродливый

    while(range.size() >= x)
    {
        std::vector<short> sub_range(x); // Unnecessary allocation?
        std::move(range.begin(), range.begin() + x, sub_range.begin());
        sub_ranges_.push_back(std::move(sub_range));

        std::move(range.begin() + x, range.end(), range.begin());
        range.resize(range.size() - x);
    }

c++ range move c++11 move-semantics
person ronag    schedule 09.11.2010    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете использовать std::make_move_iterator в <iterator>, чтобы обернуть свой итератор в move_iterator. Этот итератор будет std::move результатом разыменования своего базового итератора, что позволит переместить его в другое место.

// assuming I understand your code, which I don't
range.insert(range.end(), new_items.begin(), new_items.end());
while(range.size() >= x)
{
    auto first = std::make_move_iterator(range.begin());
    auto last = std::make_move_iterator(range.begin() + x);

    sub_ranges.push_back(std::vector<int>(first, last));
    range = std::vector<int>(range.begin() + x, range.end());
}

РЕДАКТИРОВАТЬ: И, как вы уже обнаружили, есть сопоставление между std::move() и make_move_iterator:

std::move(first, last, out); // is the same as
std::copy(std::make_move_iterator(first), std::make_move_iterator(last), out);

Итак, что вы найдете более чистым, зависит от вас. (Первый, для меня.)

person GManNickG    schedule 09.11.2010

arrow_upward
3
arrow_downward

Один вопрос: слышали ли вы когда-нибудь о концепции View.

Идея состоит в том, что вместо того, чтобы фактически перемещать данные, вы просто создаете «представление» (шаблон прокси), которое будет ограничивать/изменять ваше восприятие его.

Например, для диапазона очень простой реализацией будет:

template <typename Iterator>
struct Range
{
  Iterator mBegin, mEnd;
};

Boost.Range предлагает толстую версию, в которой много всего.

Преимуществ в этом случае масса. среди которых:

  • Один vector, таким образом, лучшая локализация памяти
  • Разделение выполняется легко и не требует перемещения/копирования данных.

Вот split с этим методом:

typedef Range<std::vector<int>::iterator> range_type;

std::vector<range_type> split(std::vector<int> const& range, size_t x)
{
  std::vector<range_type> subRanges;
  for (std::vector<int>::iterator it = range.begin(), end = range.end();
       it != end; it += std::min(x, (size_t)std::distance(it,end)))
  {
    subRanges.push_back(range_type(it,end));
  }
  return subRanges;
}

Конечно, это работает только в том случае, если вы можете держать объект range рядом.

Что касается вашего исходного алгоритма: использование цикла while здесь ложно и заставляет вас использовать гораздо больше move, чем необходимо. Цикл for, который я создал, должен быть намного лучше в этом отношении.

person Matthieu M.    schedule 10.11.2010