Типы и функции контейнеров. Специальные операции над ассоциативными контейнерами

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

   
Функции, перечисленные ниже, представляют собой специализированные реализации соответствующих алгоритмов STL,
которые мы опишем позже. Они превосходят унифицированные алгоритмы по скорости, поскольку в них учитывается тот факт, что
элементы ассоциативных контейнеров автоматически сортируются. На практике эти функции обеспечивают логарифмическую
сложность вместо линейной. Например, при поиске в контейнере, содержащем 1000 элементов, в среднем требуется не более 10
сравнений.

  size_type контейнер::count (const T& value) const

Возвращает количество элементов со значением, равным value. Это специализированная версия алгоритма count().
Т - тип сортируемых данных:

  • для множеств и мультимножеств - тип элемента;
  • для отображений и мультиотображений - тип ключа.

Сложность линейная. Поддерживается множествами, мультимножествами, отображениями, мультиотображениями.

  iterator контейнер::find (const T& value) 
  const_iterator контейнер::find (const T& value) const

Обе версии возвращают позицию первого элемента со значением, равным value.
Если элемент не найден, возвращается end(). Это специализированные версии алгоритма find().
Т - тип сортируемых данных:

  • для множеств и мультимножеств - тип элемента;
  • для отображений и мультиотображений - тип ключа.

Сложность логарифмическая. Поддерживаются множествами, мультимножествами, отображениями, мультиотображениями.

  iterator контейнер::lower_bound (const T& value) 
  const_iterator контейнер::lower_bound (const T& value) const

Обе версии возвращают первую позицию, в которой была бы вставлена копия value в соответствии с критерием сортировки.
Возвращаемое значение представляет позицию первого элемента со значением, равным или большим value (или end()).
Если элемент не найден, обе версии возвращают end(). Это специализированные версии алгоритма lower_bound().
Т - тип сортируемых данных:

  • для множеств и мультимножеств - тип элемента;
  • для отображений и мультиотображений - тип ключа.

Сложность логарифмическая. Поддерживаются множествами, мультимножествами, отображениями, мультиотображениями.

  iterator контейнер::upper_bound (const T& value) 
  const_iterator контейнер::upper_bound (const T& value) const

Обе версии возвращают последнюю позицию, в которой была бы вставлена копия value в соответствии с критерием сортировки.
Возвращаемое значение представляет позицию первого элемента со значением, большим value (или end()).
Если элемент не найден, обе версии возвращают end(). Это специализированные версии алгоритма upper_bound().
Т - тип сортируемых данных:

  • для множеств и мультимножеств - тип элемента;
  • для отображений и мультиотображений - тип ключа.

Сложность логарифмическая. Поддерживаются множествами, мультимножествами, отображениями, мультиотображениями.

  pair<iterator, iterator> контейнер::equal_range (const T& value) 
  pair<const_iterator, const_iterator>
             контейнер::equal_range (const T& value) const

Обе версии возвращают первую и последнюю позиции, в которых была бы вставлена копия value в соответствии с критерием
сортировки.
Возвращаемое значение определяет интервал элементов со значением, равным value. Результат вызова эквивалентен следующему:

  make_pair(lower_bound(value),upper_bound(value))

Это специализированные версии алгоритма equal_range(). Т - тип сортируемых данных:

  • для множеств и мультимножеств - тип элемента;
  • для отображений и мультиотображений - тип ключа.

Сложность логарифмическая. Поддерживаются множествами, мультимножествами, отображениями, мультиотображениями.

  key_compare контейнер::key_comp ()

Возвращает критерий сравнения.
Поддерживается множествами, мультимножествами, отображениями, мультиотображениями.

  value_compare контейнер::value_comp ()

Возвращает объект, используемый в качестве критерия сравнения.

  • Для множеств и мультимножеств - эквивалент key_comp.
  • Для отображений и мультиотображений - вспомогательный класс для критерия сравнения, при котором сравниваются
    только ключевые части двух элементов.

Поддерживается множествами, мультимножествами, отображениями, мультиотображениями.

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



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

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