Как избежать перераспределения с использованием STL (C ++)

Question

Этот вопрос выводится из темы:

векторный резерв c ++

Я использую структуру данных типа vector<vector<vector<double> > >. Невозможно узнать размер каждого из этих векторов (кроме внешнего) до добавления элементов (double s). Я могу получить приблизительный размер (верхняя граница) количества элементов в каждом «измерении».

Возможно, стоит использовать решение с общими указателями, но я хотел бы попробовать решение, в котором vector<vector<vector<double> > > просто имеет .reserve() достаточно свободного места (или каким-то другим образом выделило достаточно памяти).

Будет A.reserve(500) (при условии, что 500 - это размер или, альтернативно, верхняя граница для размера) будет достаточно для того, чтобы содержать "двумерные" векторы большого размера, скажем, [1000] [10000]?

Причина моего вопроса в основном в том, что я не вижу способа разумно оценить размер внутренней части A во время .reserve(500).

Пример моего вопроса:

vector<vector<vector<int> > > A;
A.reserve(500+1);
vector<vector<int> > temp2;
vector<int> temp1 (666,666);
for(int i=0;i<500;i++)
{
  A.push_back(temp2);
  for(int j=0; j< 10000;j++)
  {
    A.back().push_back(temp1);
  }
}

Будет ли это гарантировать, что перераспределение для A не выполняется?

Если при создании были добавлены temp2.reserve(100000) и temp1.reserve(1000), это гарантирует, что перераспределение вообще не произойдет?

В вышесказанном не обращайте внимания на тот факт, что память может быть потеряна из-за консервативных вызовов .reserve().

Спасибо всем заранее!

Answer 1

Чтобы избежать копирования и перераспределения для структуры данных, такой как vector<vector<vector<double> > >, я бы предложил следующее:

vector<vector<vector<double> > > myVector(FIXED_SIZE);

для того, чтобы «присвоить» ему значение, не определяйте свои внутренние векторы, пока вы на самом деле не узнаете их требуемые измерения, а затем используйте swap () вместо присваивания:

vector<vector<double> > innerVector( KNOWN_DIMENSION );
myVector[i].swap( innerVector );

Обратите внимание, что push_back() выполнит операцию копирования и может вызвать перераспределение, а swap() - нет (при условии, что для обоих векторов используются одинаковые типы распределителей).

Answer 2

Однажды у меня была такая же проблема. Чистый способ сделать это (я думаю) - написать собственный Allocator и использовать его для внутренних векторов (последний параметр шаблона std::vector<>) Идея состоит в том, чтобы написать распределитель, который на самом деле не выделяет память, а просто возвращает правильный адрес в памяти вашего внешнего вектора. Вы можете легко узнать этот адрес, если знаете размер каждого из предыдущих векторов.

Answer 3

Функция reserve будет работать правильно для вас vector A, но не будет работать так, как вы ожидаете для temp1 и temp2.

Вектор temp1 инициализируется с заданным размером, поэтому он будет установлен с правильным capacity, и вам не нужно использовать reserve с этим, если вы планируете не увеличивать его размер.

Что касается temp2, атрибут capacity не переносится в копию. Учитывая, что когда вы используете функцию push_back, вы добавляете копию в vector, код, подобный этому

vector<vector<double>> temp2;
temp2.reserve(1000);
A.push_back(temp2); //A.back().capacity() == 0

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

vector<vector<double>> temp2;
A.push_back(temp2);
A.back().reserve(1000); //A.back().capacity() == 1000

Answer 4

ваш пример вызовет много копирования и выделения.

vector<vector<vector<double>>>  A;
 A.reserve(500+1);
 vector<vector<double>>  temp2; 
vector<double> temp1 (666,666);
 for(int i=0;i<500;i++) 
{
 A.push_back(temp2);
 for(int j=0; j< 10000;j++)
 {
 A.back().push_back(temp1);
 }
} 

В: Будет ли это гарантировать, что для A не будет перераспределения?
A: Да.

В: Если temp2.reserve (100000) и temp1.reserve (1000), добавленные при создании, гарантируют, что перераспределение вообще не произойдет?
A: Здесь temp1 уже знает свою собственную длину во время создания и не будет изменяться, поэтому добавление temp1.reserve (1000) вызовет только ненужное перераспределение.
Я не знаю, что векторные классы копируют в свои копии ctor, для этого примера должно работать A.back (). Reserve (10000).
Обновление: Только что протестировано с g ++, емкость temp2 не будет скопирована. Поэтому temp2.reserve (10000) работать не будет.

И, пожалуйста, используйте форматирование исходного кода, когда вы публикуете код, чтобы сделать его более читабельным: -).

Answer 5

Как может быть забронировано 500 записей в A заранее для [1000] [1000]?

Вам необходимо зарезервировать> 1000 для A (что является вашим фактическим верхним значением), а затем всякий раз, когда вы добавляете запись в A, резервируйте в it еще 1000 или около того (опять же, верхняя граница, но для значение секунда ).

т.е.

A.reserve(UPPERBOUND);

for(int i = 0; i < 10000000; ++i)
   A[i].reserve(UPPERBOUND);

Кстати, резерв резервирует количество элементов, а не количество байтов.

Answer 6

Ответ был более или менее здесь . Итак, ваш код будет выглядеть примерно так:

vector<vector<vector<double> > > foo(maxdim1,
    vector<vector<double> >(maxdim2,
    vector<double>(maxdim3)));

Answer 7

Если матрица становится действительно большой и свободной, я бы тоже попробовал разреженную матричную библиотеку. В противном случае, прежде чем связываться с распределителями, я бы попробовал заменить vector на deque. Deque не перераспределяется при росте и предлагает почти такой же быстрый произвольный доступ, как и вектор.

Answer 8

Почему бы не создать подклассы внутренних контейнеров и reserve () в конструкторах?

Answer 9

Хорошо, теперь я провел небольшое тестирование самостоятельно. Я использовал «2DArray», полученный из http://www.tek -tips.com / faqs.cfm? Fid = 5575 , чтобы представить структуру, выделяющую статическую память. Для динамического размещения я использовал векторы почти так, как указано в моем исходном посте.

Я протестировал следующий код (hr_time - это временная процедура, найденная в сети, которую я, к сожалению, не могу опубликовать из-за антиспама, но благодарю Дэвида Болтона за ее предоставление)

#include <vector>
#include "hr_time.h"
#include "2dArray.h"
#include <iostream>
using namespace std;

int main()
{
    vector<int> temp;

    vector<vector<int> > temp2;

    CStopWatch mytimer;

    mytimer.startTimer();

    for(int i=0; i<1000; i++)
    {
        temp2.push_back(temp);
        for(int j=0; j< 2000; j++)
        {
            temp2.back().push_back(j);
        }
    }

    mytimer.stopTimer();

    cout << "With vectors without reserved: " << mytimer.getElapsedTime() << endl;

    vector<int> temp3;

    vector<vector<int> > temp4;

    temp3.reserve(1001);

    mytimer.startTimer();

    for(int i=0; i<1000; i++)
    {
        temp4.push_back(temp3);
        for(int j=0; j< 2000; j++)
        {
            temp4.back().push_back(j);
        }
    }

    mytimer.stopTimer();

    cout << "With vectors with reserved: " << mytimer.getElapsedTime() << endl;

    int** MyArray = Allocate2DArray<int>(1000,2000);

    mytimer.startTimer();
    for(int i=0; i<1000; i++)
    {
        for(int j=0; j< 2000; j++)
        {
            MyArray[i][j]=j;
        }
    }


    mytimer.stopTimer();

    cout << "With 2DArray: " << mytimer.getElapsedTime() << endl;

    //Test
    for(int i=0; i<1000; i++)
    {
        for(int j=0; j< 200; j++)
        {
            //cout << "My Array stores :" << MyArray[i][j] << endl;
        }
    }

    return 0;
}

Получается, что для этих размеров есть коэффициент около 10. Поэтому я должен пересмотреть вопрос о том, подходит ли динамическое распределение для моего приложения, поскольку скорость имеет первостепенное значение!

Answer 10

Мне кажется, вам нужен реальный матричный класс вместо вложенных векторов. Взгляните на boost, который имеет несколько сильных классов разреженных матриц.