Frost

Эффективное использования STL vector-а

Использование STL контейнера vector. Производительность vector-а
Использование контейнеров стандартной библиотеки C++, всегда обусловлено простотой и удобством, производительностью. Но как и всякий "инструмент" его нужно использовать правильно, ведь хороший и эффективный инструмент в неумелых руках может быть бесполезен или неэффективен. В этой небольшой статье, я поведаю, как его использовать максимально эфективно и какие проблемы, подводные камни могут возникнут при первом знакомстве.
[spoiler]

Начнем пожалуй с самого истока
STL - стандартаная библиотека шаблонов. То есть, все то, что в стандартной библиотеке выражено шаблоном(ами), и есть STL. Но по большей части STL-ем принято считать именно контейнеры, алгоритмы и итераторы.
STL уже давно вошла в стандартную библиотеку C++, но все же не все пользуются ей в полной мере во основном из-за незнания о существовании тех или иных шаблонных классов.

И так вернемся конкретно к вектору.
Контейнер vector - это то же массив, который может содержать в себе любой встроенный или пользовательский тип. Но по сравнению со встроенным массивом у него есть ряд преимуществ.

- Он сам знает свой размер, (метод size())
- Можно легко менять размер(добавлять, удалять элементы), во время выполнения
- При удалении, очистки он вызывает деструкторы классов(ну это преимущество спорно=))

Пробежимся по основным методам.

Пора увидеть его в действии!

/*http://esate.ru, Flashhell*/


// подключаем заголовки
#include <iostream> // подключаем для ввода-вывода(cout, cin ...)
#include <vector> // подключаем сам vector

// подключаем стандартное пространство имен, чтоб не писать std::vector или std::cout
using namespace std; 

int main(int argc, char **argv)
{
  vector<int> vec; // вектор int-ов, в этих скобочках <параметр шаблона(тип масива)>      =)
  for (int i = 0; i < 100; ++i)
  {
    vec.push_back(i); // добавляем в int i конец
  }

  for (unsigned int i = 0; i < vec.size(); ++i) // обычный вариант перебора vector-а
  {
    cout<<vec[i]<<"  "; // получаем элемент по индексу и выводим его
  }

      cout<<"\n";

      for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) // перебор вектора через итераторы
      {
           cout<<*(it)<<"  "; // получаем элемент из итератора и выводим его
      }

  return 0;
}

При переборе вектора через итераторы, нужно приучить себя писать преинкремент(++it), так он эфективнее.

Создание статического вектора:

Самый частый случай, проблем с созданием статического вектора - создание его в классе.
Чтобы создать в классе статический вектор, нужно его описать в .h и определить в .cpp. В данном случаи я поместил все в один файл, только ради простоты. Так можно создавать не только статический вектор, но и любой другой статический контейнер.

/*http://esate.ru, Flashhell*/


#include <iostream>
#include <vector>

using namespace std;

class myClass
{
public:
  void addDigit(int digit){ vec.push_back(digit); }
  int getDigitCount() const { return vec.size(); }
private:
  static vector<int> vec; // описание статического вектора
};

vector<int> myClass::vec; // определение статического вектора

int main(int argc, char **argv)
{

  myClass obj1;// создаем два объекта myClass со статическим вектором
  myClass obj2;

  obj1.addDigit(1); // добавляем пару цифр в первый объект
  obj1.addDigit(1);
  cout<<"Digit count obj1: "<<obj1.getDigitCount()<<"\n"; // выводим количество цифр в объекте
  obj2.addDigit(1);// добавляем одну цифру во второй объект
  cout<<"Digit count obj1: "<<obj1.getDigitCount()<<"\n";// выводим количество цифр в первом объекте
  cout<<"Digit count obj2: "<<obj2.getDigitCount()<<"\n";// выводим количество цифр во втором объекте

  // запустив проект, мы увидим одинаковое количество цифр и в первом и во втором объекте)
  return 0;
}

Теперь об эффективности

Вектор эффективен, в случаях если Вам нужен контейнер, в которые вы будете накапливать элементы. То есть - добавлять. Вектор эффективен при добавлении в конец методом push_back(), и при удалении с конца pop_back().
При вставке или удалении в произвольном месте (методы insert() и erase()), эффективность вектора хуже в сравнении со списком(list) или двусторонней очередью(deque). Связанно это с тем что, вектор хранит данные в памяти последовательно, что дает быстрый произвольный доступ и возможность использовать вектор, как обычный массив. К примеру в те же функции OpenGL вместо указателя на C массив, можно указать &имя_вектора.
У вектора есть не только размер(size()), но и емкость(capacity()), емкость это максимальное количество элементов которые при добавлении не вызовет переспраделении внутреннего буфера. При превышении этого значения вектор выделяет новый внутренней буфер(allocator), и копирует все элементы из старого буфера в новый, удаляя при этом из старого. То, есть если мы храним в нем большие объекты классов, то это операция будет довольно дорогостоящая. Особенно остро это "почувствуется" на больших объектах со сложным деструктором.
Емкость задана самой реализацией стандартной библиотеки.

/*http://esate.ru, Flashhell*/


  vector<double> vec(10); // создаем вектор из 10 элементов, по умолчанию они забиваются нулями
  vec.push_back(1);
  vec.push_back(1);
  vec.push_back(1);

  // я использовал Visual Studio 2008(компилятор этой IDE=)), если Вы использовали другой компилятор, У Вас могут выйти другие результаты
  cout<<"vec.size() "<<vec.size()<<"\n"; // размер   у меня выдало(13)
  cout<<"vec.capacity() "<<vec.capacity()<<"\n"; // емкость   у меня выдало(15)

Если же хранит в векторе указатели на объекты, то это очень повышает эффективность хранения в векторе, особенно больших объектов.
Хранить не большие объекты или встроенные типы в векторе, довольно эффективно.

Вывод
Если вы не собираетесь часто удалять элементы контейнера, и Вам не нужно вставлять элементы в начало и середину. И Вы собираетесь хранить не большие объекты, встроенные типы, или указатели на любые объекты(большие или не очень=)). То лучше предпочесть вектор, и помнить какие операции с ним, что делают, внутри него, в том числе. И какие из них будут не слишком дорогостоящие.

7651

20.07.2012

Эффективное использования STL vector-а

Сохраните страницу!