Какой способ копирования vector в list наиболее быстрый?

Question

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

// 1. Range Constructor
#include <iostream>
#include <vector>
#include <list>

int main()
{
    // input vector of integers
    std::vector<int> src({ 1, 2, 3, 4, 5 });

    std::list<int> dest(src.begin(), src.end());

    for (const int &i: dest) {
        std::cout << i << " ";
    }

    return 0;
}

-

// 2. std::copy
#include <iostream>
#include <vector>
#include <list>

int main()
{
    // input vector of integers
    std::vector<int> src({ 1, 2, 3, 4, 5 });

    std::list<int> dest;
    std::copy(src.begin(), src.end(), std::back_inserter(dest));

    for (const int &i: dest) {
        std::cout << i << " ";
    }

    return 0;
}

-

// 3. std::list::insert
#include <iostream>
#include <vector>
#include <list>

int main()
{
    // input vector of integers
    std::vector<int> src({ 1, 2, 3, 4, 5 });

    std::list<int> dest;
    dest.insert(dest.begin(), src.begin(), src.end());

    for (const int &i: dest) {
        std::cout << i << " ";
    }

    return 0;
}

-

// 4. std::list::assign
#include <iostream>
#include <vector>
#include <list>

int main()
{
    // input vector of integers
    std::vector<int> src({ 1, 2, 3, 4, 5 });

    std::list<int> dest;
    dest.assign(src.begin(), src.end());

    for (const int &i: dest) {
        std::cout << i << " ";
    }

    return 0;
}

-

// 5. Naive Solution
#include <iostream>
#include <vector>
#include <list>

int main()
{
    // input vector of integers
    std::vector<int> src({ 1, 2, 3, 4, 5 });

    std::list<int> dest;
    for (const int &i: src) {
        dest.push_back(i);
    }

    for (const int &i: dest) {
        std::cout << i << " ";
    }

    return 0;
}

Как видите, здесь лишь 5 элементов, а если у нас ~134217728 элементов?

Также важно, чтобы алгоритм при этом НЕ затрачивал при этом много дополнительной памяти.

Answer 1

Ну в чем проблема? Опять же, пишем программу и сравниваем... Программирование - наука экспериментальная :)

Для VC++ 2017 с оптимизациями на моей машине (время в миллисекундах для вашего количества 134217728 элементов...)

На что может затрачиваться дополнительная память - вообще не вижу, думаю, что все одинаковы... Хотите - проверьте сами.

copy1: 6155
copy2: 7062
copy3: 6933
copy4: 7250
copy5: 7258

У себя - ну, проверьте сами:

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <list>
#include <algorithm>
#include <iterator>
#include <chrono>

using namespace std;

list<int> copy1(const vector<int>& src)
{
    return list<int>(src.begin(), src.end());
}

list<int> copy2(const vector<int>& src)
{
    list<int> dest;
    copy(src.begin(), src.end(), back_inserter(dest));
    return dest;
}
list<int> copy3(const vector<int>& src)
{
    list<int> dest;
    dest.insert(dest.begin(), src.begin(), src.end());
    return dest;
}
list<int> copy4(const vector<int>& src)
{
    list<int> dest;
    dest.assign(src.begin(), src.end());
    return dest;
}

list<int> copy5(const vector<int>& src)
{
    list<int> dest;
    for (const int &i: src) {
        dest.push_back(i);
    }
    return dest;
}

int test(const vector<int>& v, list<int> (*cop)(const vector<int>&), const char * name)
{
    using Clock = std::chrono::high_resolution_clock;
    Clock::time_point start_ = Clock::now(), stop_;

    list<int> d = cop(v);

    stop_ = Clock::now();

    cout << name << ": " <<
        chrono::duration_cast<chrono::milliseconds>(stop_-start_).count() << endl;
    return *d.begin();
}

int main(unsigned long long argc, const char * argv[])
{
    vector<int> v(134217728);

    test(v,copy1, "copy1");
    test(v,copy2, "copy2");
    test(v,copy3, "copy3");
    test(v,copy4, "copy4");
    test(v,copy5, "copy5");
}

БЛОГ НА HUSL

Какой способ копирования vector в list наиболее быстрый?

Ответы (1 шт):