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

Question

Я только что обнаружил, что std :: map.insert может принять итератор в качестве первого параметра в качестве подсказки поиска для процесса вставки, например map.insert(hintIterator, insertElement);.Но есть ли какое-либо требование позиции для элемента подсказки?Это должно быть непосредственно перед или после позиции вставки?Кстати, насколько сильно влияет позиция итератора подсказки на эффективность вставки?

Answer 1

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

С сайта SGI STL

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

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

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

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

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

Answer 2

С Уникальный отсортированный ассоциативный контейнер Концепция:

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

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

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