C/C++: эффективный способ использования вектора, возвращаемого функцией

Предположим, у нас есть вектор с именем V типа vector<int>, который является закрытым членом класса.

У нас также есть эта публичная функция класса:

 vector<int> getV(){ return V; }

теперь, если у меня есть экземпляр этого класса, и все, что я хотел сделать, это прочитать значения и найти сумму всех значений внутри вектора,

Я мог бы сказать что-то вроде этого:

 MyClass obj;
 //update vector
 size_t i, size;
 size = obj.getV().size();
 int sum = 0;
 for(size_t i = 0; i < size; i++){
     sum += obj.getV().at(i);
 }

или я мог бы сказать что-то вроде этого:

  MyClass obj;
 //update vector
 size_t i, size;
 vector<int> myV = obj.getV();
 size = myV.size();
 int sum = 0;
 for(size_t i = 0; i < size; i++){
     sum += myV[i];
 }

во втором случае мы копируем весь вектор в вектор myV. Тем не менее, я не уверен, что именно происходит в первом случае, используем ли мы вектор в том виде, в котором он уже есть, или мы фактически копируем вектор каждый раз, когда вызываем функцию getV()?

Если копирования не происходит, то я считаю, что первая версия более эффективна.

Однако я не знаю на 100%, что именно происходит.

Думаю, мы могли бы вообще избежать копирования, если бы вернули ссылку на вектор V. Таким образом, мы могли бы иметь следующую функцию:

vector<int>* getV { return &V; }

а потом

 MyClass obj;
 //update vector
 size_t i, size;
 vector<int> * myV = obj.getV();
 size = myV->size();
 int sum = 0;
 for(size_t i = 0; i < size; i++){
     sum += myV->at(i);
 }

однако я хотел бы знать, что именно происходит в первом случае. Копируется ли что-нибудь? Даже в третьем случае мы возвращаем указатель, так что происходит какое-то копирование.

заранее спасибо


c++ vector pass-by-reference move-semantics pass-by-value
person ksm001    schedule 08.05.2013    source источник
comment
Другой альтернативой является создание функции, которая принимает индекс в качестве параметра и возвращает соответствующее значение вектора. Что-то вроде int getValue( int index ){ reutrn v[index]; }   -  person olevegard    schedule 08.05.2013
comment
Обратитесь к документации по вектору‹T› - оператор = и конструктор копирования   -  person Chethan    schedule 08.05.2013
comment
@olevegard Или предоставить две функции, которые возвращают итераторы begin() и end() (или const_iterators) вектора.   -  person James Kanze    schedule 08.05.2013
comment
Похоже, вы хотите читать только из вектора, и поэтому возврата ссылки на const должно быть достаточно, или вы можете быть немного более общим и вернуть std::pair, содержащую итератор начала и окончания (оба константы, конечно). Это позволит вам изменить внутреннюю структуру данных, читай более гибкую.   -  person thecoshman    schedule 08.05.2013

Ответы (5)


arrow_upward
3
arrow_downward

В принципе, в первом случае вы получаете копию всего вектора, вызывая для него size(), и тогда он сразу же выходит из области видимости.

На практике это настолько распространено, что современные компиляторы могут распознать его и полностью оптимизировать копию. Подробнее об этом можно прочитать, например, здесь. Единственный способ узнать, что происходит на вашей машине, это прочитать скомпилированный ассемблерный код. РЕДАКТИРОВАТЬ: или сделать трассировку стека, как это сделал Named. :)

В третьем случае вы копируете только значение указателя, которое равно 4 или 8 байтам (8 в 64-битной операционной системе).

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

person Corey    schedule 08.05.2013

arrow_upward
1
arrow_downward

Первый случай очень плохой, потому что он может копировать ваш вектор несколько раз. Компилятор может оптимизировать (или нет) ваш код и скрыть эту проблему (это зависит от используемого вами компилятора). Лучшее решение - определить метод, который возвращает ссылку на константу, например

const std::vector<int> & getV() const { return V; }

и используйте следующий код

const vector<int> & myV = obj.getV();
int sum = 0;
for(size_t i = 0, size = myV.size(); i < size; ++i){
 sum += myV[i];
}

кстати, код, который суммирует вектор, можно заменить на:

int sum = std::accumulate(myV.begin(), myV.end(), 0);
person nosleduc    schedule 08.05.2013

arrow_upward
1
arrow_downward

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

Я не думаю, что RVO здесь возможен, поскольку V является членом класса а не самостоятельная переменная.

Вот пример того, что происходит . Из вывода трассировщика для вектора из 3 элементов.

starting loop

[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer& Tracer::operator=(const Tracer&)
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()

[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer& Tracer::operator=(const Tracer&)
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()

[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer& Tracer::operator=(const Tracer&)
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()

Ending loop

Как видите, весь вектор (3 элемента) копируется на каждой итерации.

---------------------------------------------------------------------------------------------

Намного лучшей реализацией было бы возвращение ссылки на вектор.

 vector<int>& getV(){ return V; }
           ^^^

Теперь вы не будете делать никаких копий. Вот что происходит с этой версией. А это вывод трассировщика.

starting loop
[(none)]    Tracer& Tracer::operator=(const Tracer&)
[(none)]    Tracer& Tracer::operator=(const Tracer&)
[(none)]    Tracer& Tracer::operator=(const Tracer&)
Ending loop
person stardust    schedule 08.05.2013

arrow_upward
1
arrow_downward

Можно было бы рассказать две разные истории. Один с включенной оптимизацией, другой с отключенной оптимизацией. Эта статья Хотите скорость? Pass by Value может пролить свет.

person Arun    schedule 08.05.2013

arrow_upward
-1
arrow_downward

Как насчет расширения вашего класса путем наследования, тогда вы можете использовать все алгоритмы STL с MyClass. Вы определяете MyClass как расширение контейнера последовательности, после чего вы наследуете открытый интерфейс последовательности, и ваш объект может работать с алгоритмами STL. Написание собственных циклов — это нормально, но использование STL в полной мере приведет к более читаемому и легкому в сопровождении коду, вам нужно только быть осторожным при работе с алгоритмами, чтобы обеспечить эффективность (например, использование функций-членов диапазона по сравнению с одноэлементными) .

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

template
<
    typename Type, 
    template
    <
        typename Element, 
        typename Allocator=std::allocator<Element>
    > class Sequence
>
class MyClass
:
    public Sequence<Type>
{
    public: 

        MyClass()
            :
                Sequence<Type>()
        {}

        template<typename Iterator>
        MyClass(Iterator begin, Iterator end)
        :
            Sequence<Type>(begin, end)
        {}
};

template<typename Type>
class add_element 
{
    Type const& t_; 

    public: 

        add_element(Type const& t)
            :
                t_(t)
        {}

        template<typename Element>
        void operator()(Element & lhs)
        {
            lhs += t_; 
        }
};

using namespace std;

int main(int argc, const char *argv[])
{
    MyClass<int, vector> m;

    m.push_back(0);
    m.push_back(1);
    m.push_back(2);
    m.push_back(3);

    copy(m.begin(), m.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    for_each(m.begin(), m.end(), add_element<int>(-10));

    copy(m.begin(), m.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    MyClass<int,vector>::value_type sum = accumulate(m.begin(), m.end(), 0); 

    cout << "sum = " << sum << endl;


    return 0;
}

Выходы:

0 1 2 3 
-10 -9 -8 -7 
sum = -34

Точно так же теперь вы можете работать с std::accumulate для вычисления суммы элементов, std::sort для сортировки MyObject и т. д.

person tmaric    schedule 08.05.2013