Рубрики

Вставка элементов в std :: map (insert, emplace и operator [])

Условие: карта в STL

Карта — это контейнер, как следует из названия, используется для хранения пары ключ-значение . Карта имеет преимущество перед другими контейнерами в том, что поиск в карте , определяемой «ключом», занимает всего O (1) сложность времени, что делает его полезным в различных областях кодирования. Вставка обсуждается в этой статье.

  1. Использование insert () : функция вставки используется для вставки пары ключ-значение в карту. После вставки происходит переупорядочение элементов, и карта сортируется по ключу.
    Эта функция реализована тремя способами:
    • insert (pair) : эта функция вставляет пару в карту. Вставка происходит только тогда, когда переданный ключ еще не установлен.
      Возвращает пару указателей. Первый элемент, указывающий на уже существующую или вновь вставленную пару. Второй элемент, возвращающий логическое состояние «истина» или «ложь».
      Временная сложность: log (n), где n — размер карты
    • insert (подсказка, пара) : в этой реализации указатель подсказки отправляется с парой для вставки. Использование указателя подсказки помогает insert () знать, где должна происходить фактическая вставка. Отсюда и попытка сократить время на выделение пары.
      Указатель подсказки не заставляет вставку в определенную позицию. Эта функция возвращает указатель на позицию, где вставлена пара.
      Сложность по времени: log (n), где n — размер карты, если подсказка является оптимальной, то O (1)
    • insert (beg_ptr, end_ptr) : этот тип вставки необходим для вставки пар другого контейнера в карту. Повторяющиеся пары не вставляются, если они присутствуют в контейнере назначения.
      Временная сложность: k * log (n), где n — размер карты, k — нет. вставленных элементов

    // C ++ код для демонстрации работы insert ()

      
    #include<iostream>
    #include<map> // for map operations

    using namespace std;

      

    int main()

    {

        // объявляем карту

        // из char и int

        map< char, int > mp;

          

        // объявляем итераторы

        map<char, int>::iterator it ;

        map<char, int>::iterator it1;

        map<char, int>::iterator it2;

          

        // объявляем пару для возвращаемого значения карты, содержащей

        // карта итератора и bool

        pair <map<char, int>::iterator, bool> ptr;

          

        // используя insert () для вставки одной пары

        // вставляем 'a' с 20

        ptr = mp.insert( pair<char, int>('a', 20) );

          

        // проверка, если ключ уже присутствовал или недавно вставлен

        if(ptr.second)

            cout << "The key was newly inserted" ;

        else 

            cout << "The key was already present" ;

          

        cout << endl ;

          

        // печать пар карт после вставки

        cout << "The map pairs after 1st insertion are : \n";

          

        for (it1 = mp.begin(); it1!=mp.end(); ++it1)

            cout << it1->first << "->" << it1->second << endl;

          

        it = mp.begin();

          

        // вставляем пару карт, используя подсказку

        mp.insert(it, pair<char, int>('b', 24) );

          

        cout << endl ;

          

        // печать пар карт после вставки

        cout << "The map pairs after 2nd insertion are : \n";

          

        for (it1 = mp.begin(); it1!=mp.end(); ++it1)

            cout << it1->first << "->" << it1->second << endl;

          

        // инициализация другой карты

        map<char, int> mp2;

          

        // используя insert (beg_iter, end_iter) для копирования всех элементов

        mp2.insert(mp.begin(), mp.end());

          

        cout << endl ;

          

        // печать новых пар карт после вставки

        cout << "The new map pairs after insertion are : \n";

          

        for (it1 = mp2.begin(); it1!=mp2.end(); ++it1)

            cout << it1->first << "->" << it1->second << endl;

          
    }

    Выход:

    The key was newly inserted
    The map pairs after 1st insertion are : 
    a->20
    
    The map pairs after 2nd insertion are : 
    a->20
    b->24
    
    The new map pairs after insertion are : 
    a->20
    b->24
    

  2. Использование emplace : emplace также используется для вставки пар в карту. Эта функция аналогична «insert ()», рассмотренной выше, с той лишь разницей, что создание пары «in-place» происходит в месте вставки элемента, в отличие от insert (), который копирует или воспроизводит существующий объект.
    • emplace () : вставляет пары, используя стратегию построения на месте. Увеличивает размер карты на 1. возвращает пару указателей. Первым элементом которого является итератор, указывающий на позицию вставленной пары. 2nd возвращает логическую переменную, указывающую на уже существующую или вновь созданную пару.
      Временная сложность: log (n) (n — размер карты)
  3. emplace_hint () : принимает «hint_iterator», чтобы получить подсказку о позиции вставки, чтобы, возможно, сократить время, необходимое для вставки вставленной пары. Это не влияет на положение вставки. Это происходит там, где это определено внутренне.
    Сложность по времени: log (n) (n — размер карты), если подсказка является оптимальной, то O (1)
  4. // C ++ код для демонстрации работы emplace ()
    // и emplace_hint ()
    #include<iostream>
    #include<map> // for map operations

    using namespace std;

      

    int main()

    {

        // объявляем карту

        map<char, int> mp;

          

        // объявляем итераторы

        map<char, int>::iterator it;

        map<char, int>::iterator it1;

        map<char, int>::iterator it2;

          

        // объявляем пару для возвращаемого значения карты, содержащей

        // карта итератора и bool

        pair< map<char, int>::iterator, bool> ptr;

          

        // используя emplace () для вставки парного элемента

        // вставляем 'a' в 24

        // не требуется "пара", конструкция на месте

        ptr = mp.emplace('a', 24);

          

        // проверка, если пара уже присутствовала или недавно вставлена

        // возвращает истину недавно вставленный

        if (ptr.second)

            cout << "The key was newly inserted" ;

        else 

            cout << "The key was already present" ;

          

        cout << endl;

          

        // печать пар карт после вставки

        cout << "The map pairs after 1st insertion are : \n";

          

        for (it1 = mp.begin(); it1!=mp.end(); ++it1)

            cout << it1->first << "->" << it1->second << endl;

          

        cout << endl ;

          

        // используя emplace () для вставки одной пары

        // вставляем в 24 // не вставляем на этот раз

        ptr = mp.emplace('a', 24);

          

        // проверка, если ключ уже присутствовал или недавно вставлен

        // возвращает ложь уже вставлен

        if(ptr.second)

            cout << "The key was newly inserted" ;

        else 

            cout << "The key was already present" ;

          

        cout << endl ;

          

        // печать пар карт после вставки

        cout << "The map pairs after 2nd insertion are : \n";

          

        for (it1 = mp.begin(); it1!=mp.end(); ++it1)

            cout << it1->first << "->" << it1->second << endl;

          

        it = mp.begin();

          

        // вставляем пару карт, используя подсказку

        mp.emplace_hint(it, 'b', 20);

          

        cout << endl ;

          

        // печать пар карт после вставки

        cout << "The map pairs after 3rd insertion are : \n";

          

        for (it1 = mp.begin(); it1!=mp.end(); ++it1)

            cout << it1->first << "->" << it1->second << endl;

      

          
    }

    Выход:

    The key was newly inserted
    The map pairs after 1st insertion are : 
    a->24
    
    The key was already present
    The map pairs after 2nd insertion are : 
    a->24
    
    The map pairs after 3rd insertion are : 
    a->24
    b->20
    
  5. Используя оператор [] : «[]» также можно использовать для вставки элементов в карту. Аналогичен приведенным выше функциям и возвращает указатель на вновь созданный элемент. Разница в том, что этот оператор всегда создает новый элемент, т. Е. Даже если значение не сопоставлено с ключом, вызывается конструктор по умолчанию, который присваивает ключу «нулевое» или «пустое» значение. Размер карты всегда увеличивается на 1 .
    Временная сложность: log (n), где n — размер карты

    // C ++ код для демонстрации работы оператора []

      
    #include<iostream>
    #include<map> // for map operations

    using namespace std;

      

    int main()

    {

        // объявляем карту

        map<char, int> mp;

          

        // используя [] для присвоения ключа значению

        mp['a'] = 5;

        mp['b'] = 6;

        mp['c'] = 2;

          

        // печать значений

        cout << "The element keys to a is : ";

        cout << mp['a'] << endl;

          

        cout << "The element keys to b is : ";

        cout << mp['b'] << endl;

          

        cout << "The element keys to c is : ";

        cout << mp['c'] << endl;

          

        // конструктор по умолчанию вызывается

        // печатает 0

        cout << "The element keys to d is : ";

        cout << mp['d'] << endl;

          

          
    }

    Выход:

    The element keys to a is : 5
    The element keys to b is : 6
    The element keys to c is : 2
    The element keys to d is : 0
    

Статья по теме : Поиск в карте STL C ++

Эта статья предоставлена Манджитом Сингхом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Вставка элементов в std :: map (insert, emplace и operator [])

0.00 (0%) 0 votes