Есть ли ограничение позиции на подсказку вставки для std:: map?

Ответ 1

Он может быть от begin() до end(). Если вы передадите итератор, соответствующий идеальной позиции вставки, вы можете значительно увеличить стоимость вставки, чтобы найти правильное местоположение.

На веб-сайте SGI STL

Сложность гарантирует

Вставка с подсказкой логарифмическая в общий, но он амортизируется постоянным время, когда t вставляется немедленно до p.

Чтобы понять, почему это так, подумайте о применяемом алгоритме. std::map имеет элементы, расположенные в определенном порядке, и для того, чтобы найти правильную точку вставки, элементы должны пройти до тех пор, пока не найдет позицию, где один элемент ( "A" ) должен предшествовать новым данным и следующему элементу ( "B" ) должны следовать за ним. Учитывая это местоположение заранее, поиск можно устранить.

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

Как определить местоположение? Нужно знать, что увядает A или B. Как указывает Кубби, и обсуждаемый в alt.comp.lang.learn.c-cpp, стандарт 2003 отличается тем, что должен быть намек. В документации SGI предлагается, чтобы B был необходим, в то время как стандарт предлагает A. Возможно (учитывая, что std::map имеет битрисеральные итераторы), это не имеет значения. Я бы предположил, однако, что положение нижнего элемента (A) было бы лучше, так как вы всегда можете рассчитывать на возможность продолжить поиск вперед.

ОБНОВЛЕНИЕ: Поскольку образовательные догадки бесполезны до тех пор, пока не будут проверены, вот быстрый тест:

#include <ctime>
#include <map>
#include <iostream>

int main() {
    typedef std::map<unsigned int,unsigned int> map;

    const unsigned int k=100000;
    const unsigned int reps=10;

    // Avoid edge cases by padding either end
    map srcMap;
    {
        for(unsigned int i=0; i!=k;++i) {
            srcMap.insert(std::make_pair(i,i));
        }
        unsigned int l=3*k;
        for(unsigned int i=2*k; i!=l;++i) {
            srcMap.insert(std::make_pair(i,i));
        }
    }

    std::cout << "Hint is always the position of the preceding value\n";
    for(unsigned int i=0; i!=reps;++i)
    {
        map testMap(srcMap);
        map::iterator p=testMap.lower_bound(k-1);
        unsigned int l=2*k;
        std::clock_t start = std::clock();
        for(unsigned int i=k; i!=l;++i) {
            p=testMap.insert(p,std::make_pair(i,i));
        }
        std::clock_t end = std::clock();
        std::cout << static_cast<double>((end - start) ) << " ";
    }
    std::cout << std::endl;

    std::cout << "Hint is always the position of the following value\n";
    for(unsigned int i=0; i!=reps;++i)
    {
        map testMap(srcMap);
        map::iterator p=testMap.lower_bound(2*k);
        unsigned int l=k-1;
        std::clock_t start = std::clock();
        for(unsigned int i=2*k-1; i!=l;--i) {
            p=testMap.insert(p,std::make_pair(i,i));
        }
        std::clock_t end = std::clock();
        std::cout << static_cast<double>((end - start) ) << " ";
    }
    std::cout << std::endl;

    std::cout << "Hint is always the start of the container\n";
    for(unsigned int i=0; i!=reps;++i)
    {
        map testMap(srcMap);
        unsigned int l=2*k;
        std::clock_t start = std::clock();
        for(unsigned int i=k; i!=l;++i) {
            testMap.insert(testMap.begin(),std::make_pair(i,i));
        }
        std::clock_t end = std::clock();
        std::cout << static_cast<double>((end - start)) << " ";
    }
    std::cout << std::endl;

    std::cout << "No hint\n";
    for(unsigned int i=0; i!=reps;++i)
    {
        map testMap(srcMap);
        unsigned int l=2*k;
        std::clock_t start = std::clock();
        for(unsigned int i=k; i!=l;++i) {
            testMap.insert(std::make_pair(i,i));
        }
        std::clock_t end = std::clock();
        std::cout << static_cast<double>((end - start)) << " ";
    }
    std::cout << std::endl;

    return 0;
}

На моем маленьком нетбуке, работающем с MinGW GCC 4.5, я получил:

Подсказка всегда является позицией предыдущего значения
   94 109 109 109 109 109 110 110 110 94
   Подсказка всегда является позицией следующего значения
   109 94 109 94 110 110 109 109 110 110
   Подсказка всегда начинается с контейнера
   188 172 172 187 172 172 235 187 172 187
   Нет подсказки
   172 171 172 172 172 172 172 172 171 172

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

Ответ 2

Из Концепция Unique Sorted Associative Container:

Вставка с подсказкой является логарифмической в ​​целом, но она амортизируется постоянным временем, если t вставляется непосредственно перед p.

И только это о итераторе подсказки:

Аргумент p - это подсказка: он указывает на место начала поиска.