Два коротких вопроса о std :: vector

Question

1. Когда создается вектор, он имеет размер выделения по умолчанию (возможно, это неправильный термин, может быть, размер шага?).Когда количество элементов достигает этого размера, вектор изменяется.Этот компилятор размера специфичен?Могу ли я контролировать это?Это хорошая идея?

2. Повторные вызовы vector::size() пересчитывают количество элементов (O(n) вычисление) или это значение где-то хранится (O(1) поиск).Например, в приведенном ниже коде

   // Split given string on whitespace
   vector<string> split( const string& s )
   {
       vector<string> tokens;
       string::size_type i, j;
       i = 0;
       while ( i != s.size() ) {
           // ignore leading blanks
           while ( isspace(s[i]) && i != s.size() ) {
               i++;
           }
           // found a word, now find its end
           j = i;
           while ( !isspace(s[j]) && j != s.size() ) {
               j++;
           }
           // if we found a word, add it to the vector
           if ( i != j ) { 
               tokens.push_back( s.substr(i, j-i) );
               i = j;
           }
       }
       return tokens;
   }
   

при условии, что s может быть очень большим, я должен вызвать s.size() только один раз и сохранить результат?

Спасибо!

Answer 1

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

По крайней мере, в каждом случае, о котором я знаю, std::vector::size() просто возвращает сохраненное значение, поэтому оно имеет постоянную сложность. Теоретически стандарт C ++ позволяет делать это иначе. Есть причины разрешить иное для некоторых других контейнеров, в первую очередь std::list, и вместо того, чтобы делать особый случай для них, они просто рекомендуют постоянное время для всех контейнеров вместо того, чтобы требовать его для любых. Я не могу представить себе vector::size, который насчитывал бы элементы, хотя - я почти никогда не существовал.

P.S., более простой способ сделать то, что делает ваш код выше, выглядит примерно так:

std::vector<string> split(std::string const &input) {
    vector<string> ret;
    istringstream buffer(input);

    copy(istream_iterator<string>(input),
         istream_iterator<string>(),
         back_inserter(ret));

    return ret;
}

Редактировать: IMO, Стандартная библиотека C ++ , автор Николас Йосуттис - прекрасный справочник по таким вещам.

Answer 2

Фактический размер приращения емкости зависит от реализации, но он должен быть (примерно) экспоненциальным, чтобы соответствовать требованиям сложности контейнера. Например, стандартная библиотека Visual C ++ выделит именно то пространство, которое требуется для первых нескольких элементов (пять, если я правильно помню), а затем увеличит размер экспоненциально.

Размер должен быть как-то сохранен в векторе, иначе он не знает, где находится конец последовательности! Однако, это не обязательно может быть сохранено как целое число. Реализация Visual C ++ (опять же, в качестве примера) хранит три указателя:

1. указатель на начало базового массива,
2. указатель на текущий конец последовательности и
3. указатель на конец базового массива.

Размер может быть вычислен из (1) и (2); емкость может быть вычислена из (1) и (3).

Другие реализации могут хранить информацию по-другому.

Answer 3

Не имеет отношения к вашим актуальным вопросам, но вот более «STL» способ делать то, что вы делаете:

vector<string> split(const string& s)
{
    istringstream stream(s);
    istream_iterator<string> iter(stream), eos;
    vector<string> tokens;
    copy(iter, eos, back_inserter(tokens));
    return tokens;
}

Answer 4

Когда количество элементов достигает этого размера, вектор изменяется.Этот компилятор размера специфичен?Могу ли я контролировать это?Это хорошая идея?

В общем, это специфичное для библиотеки поведение, но вы можете иметь возможность повлиять на это поведение, указав пользовательский распределитель, который неТривиальная работа.

Повторные вызовы vector :: size () пересчитывают количество элементов (O (n) вычисление) или это значение хранится где-то (поиск O (1)).

В большинстве реализаций размер сохраняется как член.Это одно чтение памяти.

Answer 5

1. Механизм изменения размера обычно фиксирован. (Большинство компиляторов удваивают размер вектора, когда он достигает предела.) Стандарт C ++ не определяет способа управления этим поведением.

2. Размер внутренне обновляется всякий раз, когда вы вставляете / удаляете элементы, а когда вы вызываете size(), он возвращается немедленно. Так что да, это O (1) .

Answer 6

1. Это зависит от библиотеки. Возможно, вы сможете контролировать добавочное распределение, но не сможете.

2. Размер сохраняется, поэтому его очень быстро (с постоянным временем) восстановить. Как еще это может работать? C не может вообще знать, является ли ячейка памяти «реальными данными» или нет.