Questions about vectors.

[rabster]

I've been using vectors for a quite a while and have got pretty decent with them. However out of all the STL containers I don't really know how they work exactly? I know there pretty much an array that can grow, expand, shrink, and has random access but how? Arrays are static from what I know and so the only way I can think of the vector being able to expand would be it having to create a whole new array and then recopy all the elements into that array. But wouldn't that be extremely slow?

[Moschops]

But wouldn't that be extremely slow?
Yes. It is. They generally try to allow for room to grow, but when you add enough to the vector to fill it all the way up, there has to be new memory and copying.

[Peter87]

The vector allocates more memory than needed, it doesn't have to reallocate each time you add a new element, so on average it's usually not that much slower.

https://en.wikipedia.org/wiki/Dynamic_array

[Chervil]

I did a test once, out of curiosity. Repeatedly did push_back() to add one element at a time and printed out the vector size and capacity. One compiler increased the capacity by 100% every time there was a need to re-allocate, another compiler increased capacity by 50%.

Though this operation may be slow, it usually doesn't need to take place very often. Also you can use reserve() to request a large capacity right from the start, to allow room for it to grow without reallocation - if you can predict how large it will eventually need to be.

[JLBorges]

> the vector being able to expand would be it having to create a whole new array and then recopy all the elements into that array.

Yes. Move if the type is nothrow_move_constructible, copy otherwise.


> But wouldn't that be extremely slow?

It is not as slow as most programmers imagine it to be, if the items can be moved.

For instance, while copying many strings from one location to another would be slow, moving them is relatively inexpensive.

#include <iostream>
#include <string>
#include <vector>
#include <ctime>
#include <fstream>
#include <iterator>

std::vector<std::string> rev_copy_one_by_one( const std::vector<std::string>& seq, bool reserve, int& num_relocs, int& num_strings_moved )
{
    std::vector<std::string> cpy ;
    if(reserve) cpy.reserve( seq.size() ) ;
    num_relocs = 0 ;
    num_strings_moved = 0 ;

    for( const auto& str : seq )
    {
        if( cpy.size() == cpy.capacity() ) 
        {
            ++num_relocs ;
            num_strings_moved += cpy.size() ;
        }
        cpy.emplace_back( str.rbegin(), str.rend() ) ;
    }
    
    return cpy ;
}

int main() 
{
    // create a test vector of about a million strings
    const std::string path = "/usr/include/elf.h" ;
    std::ifstream file(path) ;
    const std::vector<std::string> seq { std::istream_iterator<std::string>{file}, std::istream_iterator<std::string>{} } ;
    std::vector<std::string> test_vec ;
    while( test_vec.size() < 1'000'000 ) test_vec.insert( test_vec.end(), seq.begin(), seq.end() ) ;
    std::cout << "test vector has " << test_vec.size() << " strings\n" ; 
    
    {
        const auto start = std::clock() ;
        int relocs = 0 ;
        int moves = 0 ;
        const auto cpy = rev_copy_one_by_one( test_vec, true, relocs, moves ) ;
        const auto end = std::clock() ;
        std::cout << "   with reserve: " << relocs << " relocations, " << moves << " strings were moved, " << (end-start) * 1000.0 / CLOCKS_PER_SEC << " milliseconds\n" ;
    }
    
    {
    {
        const auto start = std::clock() ;
        int relocs = 0 ;
        int moves = 0 ;
        const auto cpy = rev_copy_one_by_one( test_vec, false, relocs, moves ) ;
        const auto end = std::clock() ;
        std::cout << "without reserve: " << relocs << " relocations, " << moves << " strings were moved, " << (end-start) * 1000.0 / CLOCKS_PER_SEC << " milliseconds\n" ;
    }
    }
}

==== LLVM =====
test vector has 1010460 strings
   with reserve: 0 relocations, 0 strings were moved, 70 milliseconds
without reserve: 21 relocations, 1048575 strings were moved, 100 milliseconds
===== GNU ======
test vector has 1010460 strings
   with reserve: 0 relocations, 0 strings were moved, 50 milliseconds
without reserve: 21 relocations, 1048575 strings were moved, 100 milliseconds

http://coliru.stacked-crooked.com/a/7d0e522415b069ac

[AbstractionAnon]

@aliyu967 - For the second time, DO NOT HIJACK SOMEONE ELSE'S THREAD.

[MikeyBoy]

Fore those confused about AbstractionAnon's post - I reported aliyu967's post, and it was deleted.

[rabster]

Thanks everyone for the information! Definitely helped give me more insight into what is truly going on behind the scenes with a vector.