Стандартные множители перераспределения контейнеров в популярных наборах инструментов - PullRequest
Новая
       16

Стандартные множители перераспределения контейнеров в популярных наборах инструментов

6 голосов
/ 23 марта 2011

Контейнеры типа std::basic_string и std::vector выполняют автоматическое перераспределение при исчерпании внутренней емкости.Стандарт определяет, что после перераспределения .capacity() >= .size().

Каковы некоторые из фактических множителей, используемых основными инструментальными цепочками при выполнении перераспределений?

Обновление

Пока у меня есть:

Dinkumware: 1,5 (поставляется с MSVS и, возможно, ICC)

GNU libstdc ++: 2 (поставляется с GCC и, возможно, ICC)

RW / Apache stdcxx: 1.618 (он же φ)

STLport: 2

Ответы [ 2 ]

4 голосов
/ 23 марта 2011

Dinkumware STL (поставляется с Visual Studio) использует множитель 1,5, Gcc использует 2. Я не могу сказать, в остальном, но я думаю, что это наиболее часто используемые числа.(IIRC, я прочитал однажды, что большинство реализаций использовали 2)

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

3 голосов
/ 28 декабря 2014

Новый ответ на старый вопрос.

Обоснование: На этот вопрос можно ответить программно, а с помощью онлайн-компиляторов - относительно легко.Вот программа, которая может помочь вам ответить на этот вопрос: 

#include <climits>
#include <cstddef>
#include <cstdlib>
#ifndef _MSC_VER
#   include <cxxabi.h>
#endif
#include <iostream>
#include <memory>
#include <string>
#include <typeinfo>
#include <type_traits>
#include <limits>
#include <vector>
#include <string>

template <typename T>
std::string
type_name()
{
    typedef typename std::remove_reference<T>::type TR;
    std::unique_ptr<char, void(*)(void*)> own
           (
#ifndef _MSC_VER
                abi::__cxa_demangle(typeid(TR).name(), nullptr,
                                           nullptr, nullptr),
#else
                nullptr,
#endif
                std::free
           );
    std::string r = own != nullptr ? own.get() : typeid(TR).name();
    if (std::is_const<TR>::value)
        r += " const";
    if (std::is_volatile<TR>::value)
        r += " volatile";
    if (std::is_lvalue_reference<T>::value)
        r += "&";
    else if (std::is_rvalue_reference<T>::value)
        r += "&&";
    return r;
}

template <class C>
void
test()
{
    C c;
    std::cout << type_name<C>() << ":\n";
    std::size_t c0 = c.capacity();
    std::cout << "    Initial capacity is " << c0 << '\n';
    c.resize(c0);
    for (int i = 0; i < 10; ++i)
    {
        c.push_back(typename C::value_type{});
        std::size_t c1 = c.capacity();
        if (c0 != 0)
        {
            float f = static_cast<float>(c1)/c0;
            std::cout << "    growth factor appears to be " << f << '\n';
        }
        c0 = c1;
        c.resize(c0);
    }
}

int
main()
{
    test<std::vector<int>>();
    test<std::string>();
}

Большая часть сложности немного излишня, так как просто заставить type_name работать.

libstdc ++:

http://melpon.org/wandbox/permlink/njaIG2uiR2vlCLZz

, по-видимому, отвечает за твердое число 2 как для вектора, так и для строки.

VS:

http://webcompiler.cloudapp.net

очень близко к 1,5 для вектора и строки.

libc ++

http://melpon.org/wandbox/permlink/mXshrLJHgNuvE1mD

isочень близко к 2 как для вектора, так и для строки.

Обратите внимание, что эта программа также сообщает, что буфер короткой строки предназначен для string: 15 для libstdc ++ и VS и 22 для libc ++.

...