Standard Template Library Programmer's Guide
Здесь есть возможность читать онлайн «Standard Template Library Programmer's Guide» весь текст электронной книги совершенно бесплатно (целиком полную версию без сокращений). В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. Жанр: Программирование, Справочники, на английском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.
- Название:Standard Template Library Programmer's Guide
- Автор:
- Жанр:
- Год:неизвестен
- ISBN:нет данных
- Рейтинг книги:4 / 5. Голосов: 1
-
Избранное:Добавить в избранное
- Отзывы:
-
Ваша оценка:
Standard Template Library Programmer's Guide: краткое содержание, описание и аннотация
Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «Standard Template Library Programmer's Guide»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.
Standard Template Library Programmer's Guide — читать онлайн бесплатно полную книгу (весь текст) целиком
Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «Standard Template Library Programmer's Guide», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.
Интервал:
Закладка:
In addition to the expressions defined in Associative Container, the following expressions must be valid.
| Name | Expression | Return type |
|---|---|---|
| Default constructor | X() X a; |
|
| Constructor with bucket count | X(n) X a(n); |
|
| Constructor with hash function | X(n, h) X a(n, h); |
|
| Constructor with key equal | X(n, h, k) X a(n, h, k); |
|
| Hash function | a.hash_funct() |
X::hasher |
| Key equal | a.key_eq() |
X::key_equal |
| Erase key | a.erase(k) |
size_type |
| Erase element | a.erase(p) |
void |
| Erase range | a.erase(p, q) |
void |
| Find | a.find(k) |
iterator if a is mutable, otherwise const_iterator |
| Count | a.count(k) |
size_type |
| Equal range | a.equal_range(k) |
pair if a is mutable, otherwise pair . |
| Bucket count | a.bucket_count() |
X::size_type |
| Resize | a.resize(n) |
void |
| Name | Expression | Precondition | Semantics | Postcondition |
|---|---|---|---|---|
| Default constructor | X() X a; |
Creates an empty container, using hasher() as the hash function and key_equal() as the key equality function. | The size of the container is 0 . The bucket count is an unspecified default value. The hash function is hasher() , and the key equality function is key_equal() . | |
| Constructor with bucket count | X(n) X a(n); |
Creates an empty container with at least n buckets, using hasher() as the hash function and key_equal() as the key equality function. | The size of the container is 0 . The bucket count is greater than or equal to n . The hash function is hasher() , and the key equality function is key_equal() . | |
| Constructor with hash function | X(n, h) X a(n, h); |
Creates an empty container with at least n buckets, using h as the hash function and key_equal() as the key equality function. | The size of the container is 0 . The bucket count is greater than or equal to n . The hash function is h , and the key equality function is key_equal() . | |
| Constructor with key equal | X(n, h, k) X a(n, h, k); |
Creates an empty container with at least n buckets, using h as the hash function and k as the key equality function. The size of the container is 0 . | The bucket count is greater than or equal to n . The hash function is h , and the key equality function is k . | |
| Hash function | a.hash_funct() |
Returns the hash function used by a . | ||
| Key equal | a.key_eq() |
Returns the key equal function used by a . | ||
| Erase key | a.erase(k) |
Destroys all elements whose key is the same as k , and removes them from a . [2]The return value is the number of elements that were erased, i.e. the old value of a.count(k) . | a.size() is decremented by a.count(k) . a contains no elements with key k . | |
| Erase element | a.erase(p) |
p is a dereferenceable iterator in a . | Destroys the element pointed to by p , and removes it from a . | a.size() is decremented by 1. |
| Erase range | a.erase(p, q) |
[p, q) is a valid range in a . | Destroys the elements in the range [p,q) and removes them from a . | a.size() is decremented by the distance from i to j . |
| Find | a.find(k) |
Returns an iterator pointing to an element whose key is the same as k , or a.end() if no such element exists. | Either the return value is a.end() , or else the return value has a key that is the same as k . | |
| Count | a.count(k) |
Returns the number of elements in a whose keys are the same as k . | ||
| Equal range | a.equal_range(k) |
Returns a pair P such that [P.first, P.second) is a range containing all elements in a whose keys are the same as k . [3] If no elements have the same key as k , the return value is an empty range. | The distance between P.first and P.second is equal to a.count(k) . If p is a dereferenceable iterator in a , then either a lies in the range [P.first, P.second) , or else *a has a key that is not the same as k . | |
| Bucket count | a.bucket_count() |
Returns the number of buckets in a . | ||
| Resize | a.resize(n) |
Increases the bucket count of a . | The bucket count of a will be at least n . All iterators pointing to element in a will remain valid. [3] |
The default constructor, constructor with bucket count, constructor with hash function, and constructor with key equal, are all amortized constant time.
Hash Function and Key Equal are amortized constant time.
Average complexity for Erase Key is O(count(k)) . Worst case is linear in the size of the container.
Erase Element is amortized constant time.
Average complexity for Erase Range is O(N) , where N is the length of the range being erased. Worse case is linear in the size of the container.
Average complexity for Find is constant time. Worst case is linear in the size of the container.
Average complexity for Equal Range is O(count(k)) . Worst case is linear in the size of the container.
Average complexity for Count is O(count(k)) . Worst case is linear in the size of the container.
Bucket Count is amortized constant time.
Resize is linear in the size of the container.
• hash_set
• hash_map
• hash_multiset
• hash_multimap
[1] There is an extensive literature dealing with hash tables. See, for example, section 6.4 of Knuth. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching . Addison-Wesley, 1975.)
[2] If the hash function is poor (that is, if many different keys hash to the same value) then this will hurt performance. The worst case is where every key hashes to the same value; in this case, run-time complexity of most Hashed Associative Container operations will be linear in the size of the container.
Читать дальшеИнтервал:
Закладка:
Похожие книги на «Standard Template Library Programmer's Guide»
Представляем Вашему вниманию похожие книги на «Standard Template Library Programmer's Guide» списком для выбора. Мы отобрали схожую по названию и смыслу литературу в надежде предоставить читателям больше вариантов отыскать новые, интересные, ещё непрочитанные произведения.
Обсуждение, отзывы о книге «Standard Template Library Programmer's Guide» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.