Операции над множествами и мультимножествами. Вставка и удаление элементов

   
На этом шаге мы рассмотрим вставку элементов.

   
В таблице 1 перечислены операции вставки и удаления элементов в множествах и мультимножествах.

Таблица 1. Операции вставки и удаления для множеств и мультимножеств

Операция Описание
c.insert(elem) Вставляет копию elem и возвращает позицию нового элемента; для множеств также возвращается признак успешного выполнения операции
c.insert(pos,elem) Вставляет копию elem и возвращает позицию нового элемента (pos определяет рекомендуемую позицию, с
которой следует начинать поиск позиции вставляемого элемента)
c.insert(beg,end) Вставляет копию всех элементов интервала [beg,end) (и не возвращает значения)
c.erase(elem) Удаляет все элементы со значением elem и возвращает количество удаленных элементов
c.erase(pos) Удаляет элемент в позиции итератора pos (не возвращает значения)
c.erase(beg,end) Удаляет все элементы из интервала [beg,end) (не возвращает значения)
c.clear() Удаляет все элементы (контейнер остается пустым)

   
Как это обычно бывает при использовании STL, правильность аргументов обеспечивается вызывающей стороной. Итераторы
должны ссылаться на правильные позиции, конец интервала не должен предшествовать началу, а элементы не должны удаляться из
пустого контейнера.

   
Вставка и удаление выполняются быстрее, если группа элементов обрабатывается одним вызовом вместо нескольких последовательных
вызовов.

   
Обратите внимание на тип возвращаемого значения функций вставки:

  • Интерфейс множеств:
      pair<iterator,bool> insert(const value_type& elem);
      iterator            insert(iterator pos_hint,const valut_type& elem);
    
  • Интерфейс мультимножеств:
      iterator      insert(const value_type& elem);
      iterator      insert(iterator pos_hint,const valut_type& elem);
    

   
Различия в типах возвращаемых значений обусловлены тем, что дубликаты разрешены в мультимножествах, но запрещены в множествах.
Следовательно, вставка элемента в множество может завершиться неудачей, если множество уже содержит элемент с таким же
значением. Из-за этого возвращаемым значением множества является значение типа pair (структура pair рассматривается на
56 шаге), то есть возвращаются два значения:

  • в поле second структуры pair возвращается признак успешного выполнения вставки;
  • в поле first структуры pair возвращается позиция вставленного или существующего элемента. Во всех
    остальных случаях функции возвращают позицию нового элемента (или существующего элемента, если множество уже содержит
    элемент с таким значением).

   
Ниже приведен пример использования этого интерфейса при вставке. В множество c вставляется новый элемент со значением 3.3:

  std::set<double> c;
  .   .   .   .
  if (с.insert(3.3).second) {
    std::cout << "3.3 inserted" << std::endl;
  } else {
    std::cout << "3.3 already exists" << std::endl; 
  }

   
Если программа должна дополнительно обработать новую или старую позицию элемента, программа усложняется:

  // Определение переменной для возвращаемого значения insert() 
  std::pair<std::set<float>::iterator,bool> status;
  // Вставка элемента с присваиванием возвращаемого значения 
  status = c.insert(value);
  // Обработка возвращаемого значения 
  if (status.second) {
    std::cout << value << "inserted as element "
  } else {
    std::cout << value << "already exists as element " }
  std::cout << std::distance(c.begin(),status,first) + 1 << std::endl;

   
Результат вызова первых двух функций в этом фрагменте может выглядеть так:

  8,9 inserted as element 4
  7,7 already exists as element 3

   
Обратите внимание: типы возвращаемых значений для функций вставки с дополнительным параметром позиции не зависят от типа
контейнера. Эти функции возвращают один итератор как для множеств, так и для мультимножеств. Тем не менее вызов этих функций
приводит к таким же результатам, как и вызов функции без параметра позиции. Они отличаются только по скорости работы.

   
Функции можно передать позицию итератора, но эта позиция воспринимается только как рекомендация для оптимизации быстродействия.
Если элемент вставляется сразу же за позицией, переданной в первом аргументе, сложность операции изменяется от логарифмической
до амортизированной постоянной (сложность операций рассматривается на 42 шаге). Тот факт, что
тип возвращаемого значения функций вставки с дополнительным параметром позиции не зависит от типа контейнера, как в случае
функций вставки без параметра, гарантирует, что функция вставки обладает одинаковым интерфейсом для всех типов контейнеров.
Этот интерфейс используется несколькими общими итераторами вставки.

   
На следующем шаге мы закончим изучение этого вопроса.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий