std::copy n элементов или до конца

Я хотел бы скопировать до N элементов.

template< class InputIt, class Size, class OutputIt>
OutputIt myCopy_n(InputIt first, InputIt last, Size count, OutputIt result)
{
    Size c = count;
    while (first != last && c > 0) {
        *result++ = *first++;
        --c;
    }
    return result;
}

есть ли способ сделать это с помощью стандартных функций? Я мог бы также:

template< class InputIt, class Size, class OutputIt>
OutputIt myCopy_n(InputIt first, InputIt last, Size count, OutputIt result)
{
    if(std::distance(first, last) > count)
        return std::copy_n(first,count,result);
    return std::copy(first,last,result);
}

однако, помимо громоздкости, он дважды преодолевает диапазон (расстояние, копирование). Если я использую итератор преобразования или фильтрующий итератор, это O (N) ненужных вызовов моей функции фильтрации/преобразования.

template <class InputIt, class OutputIt>
OutputIt copy_n_max(InputIt begin, InputIt end, OutputIt last, size_t count)
{
    return std::copy_if(begin, end, last, 
                        [&count](typename std::iterator_traits<InputIt>::reference)
                        { return count--> 0; });
}

int main()
{
    std::vector<int> v({1,2,3,4,5,6,7,8,9}), out;
    copy_n_max(v.begin(), v.end(), std::back_inserter(out), 40);
    for(int i : out) std::cout <<i << " ,";
}

выходы 1,2,3,4,5,6,7,8,9,

однако это будет продолжаться до конца и не будет учитываться количество раз. так что еще больше ненужных вызовов моей функции фильтра/преобразования...


person aivision2020    schedule 30.09.2014    source источник
comment
Можете ли вы быть более конкретным в отношении того, что вы пытаетесь сделать?   -  person    schedule 30.09.2014
comment
@remyabel Мне это кажется довольно специфичным.   -  person Neil Kirk    schedule 30.09.2014
comment
Честно говоря, ваше первое решение кажется самым простым; назовите это чем-то вроде copy_upto_n() и закройте его; Он проходит через диапазон только один раз (наименьшее количество ограничений) и никогда не делает ничего, кроме подсчета разыменований ввода, в отличие от третьего решения. Я был действительно удивлен, что copy_n не ведет себя таким образом...   -  person Stefan Atev    schedule 30.09.2014
comment
Как и @Stefan, мне больше всего нравится твой myCopy_n. Как оказалось, это именно то, что я предложил в stackoverflow.com/questions/54254075/ сегодня. Другие решения кажутся слишком сложными и/или чрезмерно ограниченными. ЦЕЛОВАТЬ.   -  person Lightness Races in Orbit    schedule 18.01.2019


Ответы (4)


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

std::vector<int> v1, v2;
std::copy_n(v2.begin(), std::min(NUM, v2.size()), std::back_inserter(v1));

Если у вас есть доступ только к итераторам, я не знаю, как это сделать, используя только стандартные функции без вычисления расстояния. Это дешево для итераторов с произвольным доступом, но дубликаты работают для других типов.

std::vector<int>::iterator i_begin, i_end, o_begin;
std::copy_n(i_begin, std::min(NUM, std::distance(i_begin, i_end)), o_begin);
person Neil Kirk    schedule 30.09.2014
comment
да, ваш способ менее громоздкий, но время выполнения такое же. Я думаю, это лучшее, что мы собираемся получить. придется копировать самому или платить цену за расстояние, если функция фильтра/преобразования незначительна. кажется позором, что copy_n защищен конечным итератором. - person aivision2020; 30.09.2014
comment
@user2232888 user2232888 Сложность std::distance постоянна для итераторов произвольного доступа. Таким образом, либо std::distance бесплатен, либо вы заранее знаете размер контейнера, и первое решение Neil Kirk будет Работа. - person Jonathan Mee; 30.09.2014
comment
Джохатан Ми, это неправильно, когда все, что у вас есть, это итераторы. Вызов ++ может быть дорогим, если вы используете итераторы фильтра/преобразования... - person aivision2020; 30.09.2014
comment
@user2232888 user2232888 Если у вас есть только итераторы без произвольного доступа, а производительность критична, я бы использовал свою собственную функцию. - person Neil Kirk; 30.09.2014

Я бы пошел на что-то вроде этого:

template <class InputIt, class OutputIt>
OutputIt copy_n_max(InputIt begin, InputIt end, OutputIt last, size_t count)
{
    return std::copy_if(begin, 
                        end, 
                        last, 
                        [&count](typename std::iterator_traits<InputIt>::reference) -> bool 
                        {
                            if (count > 0)
                            {
                                --count;
                                return true;
                            }
                            return false;
                        });
}

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

Живой пример на IDEOne

person Johan    schedule 30.09.2014
comment
Я почти уверен, что компилятор упростит это. И я нахожу это более читабельным. - person Johan; 30.09.2014
comment
decltype(*begin)& =› нет, не совсем так. Вам нужен typename std::iterator_traits<InputIt>::reference, просто чтобы он работал с прокси (как в std::vector<bool>). В C++14 вы также можете использовать auto& и не оглядываться назад. - person Matthieu M.; 30.09.2014
comment
@MatthieuM. Я не понимаю проблемы с declatype(*begin)&, можете ли вы показать мне пример, когда это не сработает? - person Johan; 30.09.2014
comment
@MatthieuM. Извините, я прочитал слишком быстро (опять же) :( Спасибо за информацию, все обновляю. - person Johan; 30.09.2014
comment
Разве это не потребляет весь итератор ввода? - person Ben Jackson; 30.09.2014
comment
@BenJackson Действительно. Это, безусловно, будет проблемой, если итерация будет дорогостоящей. - person Johan; 01.10.2014
comment
@Johan Если это, например, stdin, это приведет к потере данных. - person Ben Jackson; 01.10.2014
comment
@BenJackson и даже бесконечный цикл, нет? - person Johan; 02.10.2014

Есть простой способ использовать std::copy_if-перегрузку, добавленную С++ 11 для вашей задачи (требуются только InputIterators):

template< class InputIt, class Size, class OutputIt>
OutputIt myCopy_n(InputIt first, InputIt last, Size count, OutputIt result)
{
    return std::copy_if(first, last, result,
        [&](typename std::iterator_traits<InputIt>::reference)
        {return count && count--;});
}

Кстати: в С++ 14 это становится еще лучше, нет необходимости в переменной или таком сложном аргументе:

std::copy_if(first, last, result,
    [count = some_complicated_expression](auto&&) mutable
    {return count && count--;});
person Deduplicator    schedule 30.09.2014
comment
Единственное раздражение — это ненужные проверки, когда count больше, чем размер диапазона. - person jrok; 30.09.2014
comment
Ну да, можно было бы добавить какой-нибудь шаблон со всеми оптимизациями и ярлыками, используемыми в стандартной библиотеке. Я думаю, что перегрузка для std::copy_n должна работать. - person Deduplicator; 30.09.2014
comment
@Дедупликатор: Ах! Я полностью умалчивал об этом факте! Действительно, это copy_if, а не copy_until. - person Matthieu M.; 30.09.2014
comment
почему вы возвращаете count && count-- ? почему бы просто не считать --›0? Мне придется изучить это [count = some_complicated_expression]. у этой штуки есть имя? - person aivision2020; 01.10.2014
comment
@user2232888 user2232888 Я возвращаю это, потому что не знаю, подписан ли счет или нет. Может даже сделать раннее возвращение более вероятным, хотя не знаю. И это инициализатор, необходимый для использования, например, семантики перемещения и части С++ 14. - person Deduplicator; 01.10.2014
comment
Вы можете избежать сложности в С++ 11 с помощью (...) для списка аргументов. - person StilesCrisis; 01.10.2014
comment
@StilesCrisis: Да, но потом я делаю бесполезную копию. - person Deduplicator; 01.10.2014
comment
Любой приличный компилятор встраивает предикат и полностью оптимизирует передачу аргументов, не так ли? Посмотрим правде в глаза, STL обычно требует достойного оптимизатора у руля для любой эффективности. - person StilesCrisis; 01.10.2014
comment
@StilesCrisis: если он может доказать, что ни copy-ctor, ни dtor не имеют наблюдаемого поведения, то да, он может и должен. Нет гарантии выше определенного уровня сложности. Зачем бросать кости? - person Deduplicator; 01.10.2014
comment
Это итератор. Лучше не иметь большой сложности. - person StilesCrisis; 01.10.2014
comment
@Stiles: Но предикат получает указатель этого итератора, как бы он этого ни хотел: как скопированное значение или по ссылке. - person Deduplicator; 01.10.2014

Вы можете использовать copy_if с настраиваемым предикатором, и он работает для более старых версий c++.

#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>


struct LimitTo
{
    LimitTo( const int n_ ) : n(n_)
    {}

    template< typename T >
    bool operator()( const T& )
    {
        return n-->0;
    }

    int n;
};

int main()
{
    std::vector< int > v1{ 1,2,3,4,5,6,7,8 };
    std::vector< int > v2;

    std::copy_if( std::begin(v1), std::end(v1), std::back_inserter(v2), LimitTo(3) );

    std::copy( std::begin(v1), std::end(v1), std::ostream_iterator<int>(std::cout,", ") );
    std::cout << std::endl;
    std::copy( std::begin(v2), std::end(v2), std::ostream_iterator<int>(std::cout,", ") );
    std::cout << std::endl;
}

Этот пример копирует n элементов, используя предикат LimitTo.

person BЈовић    schedule 30.09.2014