Book Image

The C++ Standard Library - Second Edition

By : Rainer Grimm
Book Image

The C++ Standard Library - Second Edition

By: Rainer Grimm

Overview of this book

Standard template library enables programmers to speed up application development using the built-in data structures and algorithms in their codes. The C++ Standard Library is a comprehensive guide to the updated library of classes, algorithms, functions, iterators, and containers and serves as the best reference to the current C++ 17 standard. Starting with the introduction and history of the standard library, this book goes on to demonstrate how quickly you can manipulate various C++ template classes while writing your applications. You'll also learn in detail the four types of STL components. Then you'll discover the best methods to analyze or modify a string. You'll also learn how to make your application communicate with the outside world using input and output streams and how to use the non-owning string objects with regular strings. By the end of this book, you'll be able to take your programming skills to a higher level by leveraging the standard C++ libraries.
Table of Contents (19 chapters)
Free Chapter
1
Reader Testimonials
8
6. Adaptors for Containers
19
Index

Binary Search

The binary search algorithms use the fact that the ranges are already sorted. To search for an element, use std::binary_search. With std::lower_bound you get an iterator for the first element, being no smaller than the given value. With std::upper_bound you get an iterator back for the first element, which is bigger than the given value. std:::equal_range combines both algorithms.

If the container has n elements, you need on average log2(n) comparisons for the search. The binary search requires that you use the same comparison criterion that you used for sorting the container. Per default the comparison criterion is std::less, but you can adjust it. Your sorting criterion has to obey the strict weak ordering. If not, the program is undefined.

If you have an unordered associative container, the methods of the unordered associative container are in general faster.

Searches the element val in the range:

bool binary_search(FwdIt first, FwdIt last, const T& val)
bool...