Home >Backend Development >C++ >What are the standard complexity guarantees for operations on different C container types?
What are the standard complexity guarantees for operations on different C container types?
- Patricia ArquetteOriginal
- 2024-12-26 00:00:18203browse
Standard Container Complexity Guarantees
Standard containers in C provide a range of complexity guarantees that govern the behavior of their operations. The following table summarizes these guarantees for different container types:
| Container Type | Copy Constructor | Fill Constructor | begin() | end() | rbegin() | rend() | front() | push_front() | pop_front() | push_back() | pop_back() | insert() | insert: fill | insert: range | size() | swap() | erase key | erase element | erase range | count() | find() | equal range | Lower Bound/Upper Bound | Equality | InEquality | Element Access | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Forward Container | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(ln(n)) | O(1) | O(ln(n) S) | O(log(n) k) | O(ln(n)) | O(ln(n)) | O(ln(n)) | O(n) | O(n) | O(1) | ||||||
| Reverse Container | O(1) | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | ||||||||||||||
| Random Access Container | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | |||||||||||||||||
| Sequence | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(ln(n)) | O(ln(n) S) | O(ln(n)) | O(ln(n)) | |||||||||||||||
| Front/Back Insert Sequence | O(1) | O(1) | O(1) | O(1) | O(1) | O(n) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | |||||||||||||||
| Back/Front Insert Sequence | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) | |||||||||||||||||
| Associative Container | O(1) | O(1) | O(kln(n) n) | O(1) | O(1) | O(1) | O(ln(n)) | O(ln(n)) | O(ln(n)) | O(n) | O(n) | ||||||||||||||||
| Simple/Sorted/Unique Associative Container | O(1) | O(1) ) | O(ln(n)) | O (n) | O(1) | O(1) | O(1) | O(ln(n)) | O(n) | O(n) | |||||||||||||||||
| Pair/Sorted/Unique Associative Container | O(1) | O(1) | O(1) | O(1) | O(1) | O(ln(n)) | O(n) | O(n) | |||||||||||||||||||
| Multiple/Sorted/Unique Associative Container | O(1) | O(1) | O(1) | O(1) | O(1) | O(ln(n)) | O(n) | O(n) |
The above is the detailed content of What are the standard complexity guarantees for operations on different C container types?. For more information, please follow other related articles on the PHP Chinese website!
Statement：
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Previous article：How Can I Forcefully Terminate a Single Thread in C 11 Without Cooperation?Next article：How Can I Forcefully Terminate a Single Thread in C 11 Without Cooperation?
Related articles
See more- C++ compilation error: A header file is referenced multiple times, how to solve it?
- C++ compilation error: wrong function parameters, how to fix it?
- C++ error: The constructor must be declared in the public area, how to deal with it?
- Process management and thread synchronization in C++
- How to deal with data splitting problems in C++ development