среда, 8 февраля 2012 г.

Конструкторы Си++ и загадки std::vector



Случилось мне недавно объяснять особенности применения конструкторов Си++. Ситуация рядовая - если вы пришли из языков оперирующих ссылками на объекты (как то Java, например), то конструктор копирования для вас в новинку.

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

Результаты получились интересными наглядными и поучительными. Поэтому я решил изложить их в своем блоге. Написанное далее может оказаться интересным не только новичкам, но и может быть использовано как материал для собеседования по языку Си++, так как требует не только понимания использования конструкторов, но и особенностей работы контейнеров типа std::vector.

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

#include <iostream>
#include <vector>

using namespace std;

class A
{
public:
    A();           // конструктор по умолчанию
    A(int x);      // конструктор с параметром
    A(const A &a); // конструктор копирования
    ~A();          // деструктор

    void operator = (const A &a);  // оператор присваивания

    int x() { return m_x; }
    void set_x(int x) { m_x = x; }

    int id() { return m_id; }

private:
    int m_x;

    static int counter;
    int m_id;
};

int A::counter = 0;

A::A(): m_x(0), m_id(++counter) {
    cout << "  Default constructor A. x = " << m_x 
         << ", id = " << m_id << endl;
}

A::A(int x): m_x(x), m_id(++counter) {
    cout << "  Param constructor A. x = " << m_x 
         << ", id = " << m_id << endl;
}

// В конструкторе копирования умышленно изменяем x
A::A(const A &a): m_x(a.m_x + 3), m_id(++counter) {
    cout << "  Copy constructor A. x = " << m_x 
         << ", id = " << m_id << endl;
}

A::~A() {
    cout << "  Destructor A. x = " << m_x 
         << ", id = " << m_id << endl;
}

// В операторе присваивания умышленно изменяем x
void A::operator = (const A &a) {
    m_x = a.m_x + 1;
    // id не копируем. Сохраним оригинальный  
    cout << "  Class A. Operator =. dest x = " << m_x 
         << ", src x = " << a.m_x << endl; 
} 

int main (int argc, char *argv[])
{
    cout << "Constructors test" << endl;

    cout << "\nMark 1" << endl;
    cout << "Log for 'A a1;'" << endl;
    A a1;
    cout << "Result: a1.x = " << a1.x() 
         << ", a1.id = " << a1.id() << endl;
 
    cout << "\nMark 2" << endl;
    cout << "Log for 'A a2(5);'" << endl;
    A a2(5);
    cout << "Result: a2.x = " << a2.x() 
         << ", a2.id = " << a2.id() << endl;

    cout << "\nMark 3" << endl;
    cout << "Log for 'A a3 = a2;'" << endl;
    A a3 = a2;
    cout << "Result: a3.x = " << a3.x() 
         << ", a3.id = " << a3.id() << endl;

    cout << "\nMark 4" << endl;
    cout << "Log for 'A a4; a4 = a3;'" << endl;
    A a4;
    a4 = a3;
    cout << "Result: a4.x = " << a4.x() 
         << ", a4.id = " << a4.id() << endl;

    cout << "\nMark 5. 'vector<A> vA;'" << endl;
    vector<A> vA;
 
    cout << "\nLog for 'vA.push_back(a1);'" << endl;
    vA.push_back(a1);    

    cout << "\nLog for 'vA.push_back(a2);'" << endl;
    vA.push_back(a2);    

    cout << "\nLog for 'vA.push_back(a3);'" << endl;
    vA.push_back(a3);    

    cout << "\nLog for 'vA.push_back(a4);'" << endl;
    vA.push_back(a4);    

    cout << "\nLog for 'vA.push_back(A(100));'" << endl;
    vA.push_back(A(100)); 
    {
        vector<A>::iterator it;
        for(it = vA.begin(); it != vA.end(); ++it) {
            cout << "Item vA: x = " << (*it).x() 
                 << ", id = " << (*it).id() << endl; 
        }
    }

    cout << "\nMark 6. 'vector vpA;'" << endl;
    vector<A*> vpA;

    cout << "\nLog for 'vpA.push_back(&a1);'" << endl;
    vpA.push_back(&a1);        

    cout << "\nLog for 'vpA.push_back(&a2);'" << endl;
    vpA.push_back(&a2);        

    cout << "\nLog for 'vpA.push_back(&a3);'" << endl;
    vpA.push_back(&a3);        

    cout << "\nLog for 'vpA.push_back(&a4);'" << endl;
    vpA.push_back(&a4);        

    cout << "\nLog for 'vpA.push_back(new A(200));'" << endl;
    vpA.push_back( new A(200)); 
    {
        vector<A*>::iterator it;
        for(it = vpA.begin(); it != vpA.end(); ++it) {
            cout << "Item vpA: x = " << (*it)->x() 
                 << ", id = " << (*it)->id() << endl;
        }
    }
 
    cout << "\nMark 7. EOP\n" << endl;

    return 0;
}

Чтобы код проще читался, попробуйте скопировать его в редактор, который умеет делать подстветку для кода на языке Си++.

Итак, что есть в коде.

Использованы все три вида конструкторов языка Си++ (конструктор по умолчанию, параметрический конструктор и конструктор копирования). Так же использован оператор присваивания без которого нельзя продемонстрировать присваивание объектов. Для новичков следует пояснить, что инициализация отличается от присваивания в Си++ и выглядит следующим образом.

A a3 = a2; // инициализация (используется конструктор копирования)
A a4;      // создание объекта класса через конструктор по умолчанию
a4 = a3;   // копирование (используется оператор копирования)

Теперь обратимся к результатам работы этой программы на моем компьютере. Я проверял все это на ноутбуке с установленным Linux Ubuntu 11.04.

Итак, по первому блоку.

Mark 1
Log for 'A a1;'
  Default constructor A. x = 0, id = 1
Result: a1.x = 0, a1.id = 1

Все предсказуемо. Вызывается конструктор по умолчанию.

Далее, блок два.

Mark 2
Log for 'A a2(5);'
  Param constructor A. x = 5, id = 2
Result: a2.x = 5, a2.id = 2

Тоже все как в учебнике. Вызывается параметрический конструктор.

Блок три

Mark 3
Log for 'A a3 = a2;'
  Copy constructor A. x = 8, id = 3
Result: a3.x = 8, a3.id = 3

Здесь может быть ловушка для новичков. Это не присвоение, а инициализация. Как результат - вызов конструктора копирования.

Блок четыре

Mark 4
Log for 'A a4; a4 = a3;'
  Default constructor A. x = 0, id = 4
  Class A. Operator =. dest x = 9, src x = 8
Result: a4.x = 9, a4.id = 4

Тоже все логично. Создаем объект конструктором по умолчанию, а потом выполняем присваивание через перегруженный оператор присваивания объектов данного типа.

А вот теперь блок пять и первые сюрпризы.

Mark 5. 'vector<A> vA;'

Log for 'vA.push_back(a1);'
  Copy constructor A. x = 3, id = 5

Log for 'vA.push_back(a2);'
  Copy constructor A. x = 8, id = 6
  Copy constructor A. x = 6, id = 7
  Destructor A. x = 3, id = 5

Log for 'vA.push_back(a3);'
  Copy constructor A. x = 11, id = 8
  Copy constructor A. x = 9, id = 9
  Copy constructor A. x = 11, id = 10
  Destructor A. x = 6, id = 7
  Destructor A. x = 8, id = 6

Log for 'vA.push_back(a4);'
  Copy constructor A. x = 12, id = 11

Log for 'vA.push_back(A(100));'
  Param constructor A. x = 100, id = 12
  Copy constructor A. x = 103, id = 13
  Copy constructor A. x = 12, id = 14
  Copy constructor A. x = 14, id = 15
  Copy constructor A. x = 14, id = 16
  Copy constructor A. x = 15, id = 17
  Destructor A. x = 9, id = 9
  Destructor A. x = 11, id = 10
  Destructor A. x = 11, id = 8
  Destructor A. x = 12, id = 11
  Destructor A. x = 100, id = 12
Item vA: x = 12, id = 14
Item vA: x = 14, id = 15
Item vA: x = 14, id = 16
Item vA: x = 15, id = 17
Item vA: x = 103, id = 13

Кто из вас ожидал априори такой серии вызовов конструкторов копирования и деструкторов для, казалось бы, простой операции? Лично я не ожидал. Не ожидал, но могу это объяснить, так как сам неоднократно писал разного рода контейнеры и немного интересовался теорией на этот счет.

Объяснение элементарное. Дело в работе механизма распределения памяти в векторе std::vector. Точнее, в его конкретной реализации. А работает он, в данном примере по следующей простой схеме. Каждый раз он удваивает размер контейнера для хранения объектов начиная с распределения памяти под один элемент. Т.е. размер контейнера для размещения вектора сначала был нулевым при создании, потом при помещении первого элемента стал равным единицы, потом увеличился до двух, потом до четырех и, закончился рост контейнера нашего вектора на восьми при добавлении пятого элемента.

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

Теперь блок шесть и опять сюрпризы.

Mark 6. 'vector<A*> vpA;'

Log for 'vpA.push_back(&a1);'

Log for 'vpA.push_back(&a2);'

Log for 'vpA.push_back(&a3);'

Log for 'vpA.push_back(&a4);'

Log for 'vpA.push_back(new A(200));'
  Param constructor A. x = 200, id = 18
Item vpA: x = 0, id = 1
Item vpA: x = 5, id = 2
Item vpA: x = 8, id = 3
Item vpA: x = 9, id = 4
Item vpA: x = 200, id = 18

Организовав в векторе хранение указателей на объекты вместо самих объектов мы изменили количество вызываемых конструкторов и деструкторов при заполнении вектора. Почему? Вектор стал по другому работать?

Конечно же все просто. Ловушка для неискушенных :) Вектор по прежнему работает в схеме распределения памяти { 0, 1, 2, 4, 8 }, однако теперь, при копировании элементов из старого контейнера в новый, копируются не сами объекты, вызовом соответствующих конструкторов копирования и уничтожением скопированных объектов, а копируются указатели на эти объекты. Разумеется, копирование указателей не связано с такими затратами.

Просто имейте это в виду при написании собственных программ. Собственно в этом и состоит цель этой заметки :)

В программе есть еще один вывод. Блок семь. Автоматическое уничтожение объектов при завершении программы. Видим деструкторы всех оставшихся в памяти объектов.

Mark 7. EOP

  Destructor A. x = 12, id = 14
  Destructor A. x = 14, id = 15
  Destructor A. x = 14, id = 16
  Destructor A. x = 15, id = 17
  Destructor A. x = 103, id = 13
  Destructor A. x = 9, id = 4
  Destructor A. x = 8, id = 3
  Destructor A. x = 5, id = 2
  Destructor A. x = 0, id = 1

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

Если для блока пять мы заменим std::vector на std::list (стандартный контейнер работающий по схеме связанного списка) то мы получим следующий вариант вывода по блоку пять.

Mark 5. 'list<A> vA;'

Log for 'vA.push_back(a1);'
  Copy constructor A. x = 3, id = 5

Log for 'vA.push_back(a2);'
  Copy constructor A. x = 8, id = 6

Log for 'vA.push_back(a3);'
  Copy constructor A. x = 11, id = 7

Log for 'vA.push_back(a4);'
  Copy constructor A. x = 12, id = 8

Log for 'vA.push_back(A(100));'
  Param constructor A. x = 100, id = 9
  Copy constructor A. x = 103, id = 10
  Destructor A. x = 100, id = 9
Item vA: x = 3, id = 5
Item vA: x = 8, id = 6
Item vA: x = 11, id = 7
Item vA: x = 12, id = 8
Item vA: x = 103, id = 10

Обратите внимание, что изменить надо и строку описания объекта vA, и строку описания итератора по vA.

Если же все-таки использовать контейнер std::vector, то избавиться от троекратного (для нашего случая) перераспределения памяти можно с помощью метода reserve(). Так как нам нужно зарезервировать место под пять объектов, то можно сразу после определения объекта vA написать следующее.

vector<A> vA;
vA.reserve(5);

Не путайте метод reserve() c методом resize()!!! Интереса ради можете посмотреть, что получится и попробовать объяснить результат.

Комментариев нет: