std_library.md

The standard library, Boost and proposals

Table of contents

• General information
  • Implementations
• Algorithms
  • std::iota
  • std::midpoint
• Containers
  • Associative containers
  • Sequence containers
    • std::array
    • std::deque
    • std::vector
    • std::vector<bool>
  • Unordered containers
• Input/output
• Iterators
• Memory
  • Allocators
• Numerics
  • std::bit_cast
  • Linear algebra support
  • Random numbers
• Regular expressions
• Smart pointers
  • std::unique_ptr
  • std::shared_ptr
    • std::enable_shared_from_this
  • std::weak_ptr
  • std::auto_ptr
  • std::observer_ptr
  • boost::intrusive_ptr
• Strings
  • Short string optimization
  • std::string_view
• Type support
  • Fixed-width integer types
  • Type traits
  • std::is_trivial*
• Utilities
  • Function objects
  • Pairs and tuples
  • Sum types
    • std::variant
    • (std::)expected
  • std::launder
• Tricks and subtleties
• The Standard Template Library (STL)

---

General information

📖

• J.Galowicz. C++17 STL cookbook: Discover the latest enhancements to functional programming and lambda expressions (2017)
• Ch. 18: Concurrency – N.M.Josuttis. The C++ standard library: A tutorial and reference (2012)

Implementations

🔗

• libstdc++
• libc++
• Microsoft

---

Algorithms

🎥

• C.Hoekstra. Algorithm intuition. Part I, Part II – CppCon (2019)
• J.Boccara. 105 STL algorithms in less than an hour – ACCU (2018)
• M.Clow. STL algorithms: How to use them and how to write your own – ACCU (2016)
• M.VanLoon. STL algorithms in action – CppCon (2015)

std::iota

🔗

• S.Parent. #iotashaming (2019)
• What does iota of std::iota stand for? – Stack Overflow

std::midpoint

🎥

• M.Clow. std::midpoint? How hard could it be? – CppCon (2019)

⚓

• S.D.Herring. Well-behaved interpolation for numbers and pointers – WG21/P0811R3 (2019)

---

Containers

🎥

• B.Steagall. If I had my ’druthers: A proposal for improving the containers in C++2x – C++Now (2018)

Associative containers

Associative containers are: std::set (collection of unique keys, sorted by keys), std::map (collection of key-value pairs, sorted by keys, keys are unique), std::multiset (collection of keys, sorted by keys), and std::multimap (collection of key-value pairs, sorted by keys).

🔗

• insert vs emplace vs operator[] in C++ std::map – Stack Overflow

Sequence containers

Sequence containers are: std::array (static contiguous array), std::vector (dynamic contiguous array), std::deque (double-ended queue), std::forward_list (singly-linked list), and std::list (doubly-linked list).

std::array

🔗

• Create N-element constexpr array in C++11 – Stack Overflow
• Why isn’t std::array::size static? – Stack Overflow

std::deque

🔗

• What really is a deque in STL? – Stack Overflow

std::vector

🔗

• How to enforce move semantics when a vector grows? – Stack Overflow

std::vector<bool>

🔗

• H.E.Hinnant. On vector<bool> (2012)
• Why is vector<bool> not an STL container? – Stack Overflow

Unordered containers

Unordered containers are: std::unordered_set (collection of unique keys, hashed by keys), std::unordered_map (collection of key-value pairs, hashed by keys, keys are unique), std::unordered_multiset (collection of keys, hashed by keys), and std::unordered_multimap (collection of key-value pairs, hashed by keys).

🔗

• Why is there no std::is_transparent equivalent for unordered containers? – Stack Overflow
• Why is unordered_map “find + insert” faster than “insert + check for success”? – Stack Overflow
• Performance of emplace is worse than check followed by emplace – Stack Overflow

🎥

• D.Kühl. #Hashing – ACCU (2019)
• M.Skarupke. You can do better than std::unordered_map: New improvements to hash table performance – C++Now (2018)

⚓

• M.Pusz. Heterogeneous lookup for unordered containers – WG21/P0919R3 (2018)

---

Input/output

🔗

• tellg() function give wrong size of file? – Stack Overflow

⚓

• Input/output library – C++ reference

---

Iterators

🔗

• Why use iterators instead of array indices? – Stack Overflow
• Iterator loop vs index loop – Stack Overflow

🎥

• C.Carter. Iterator haiku – CppCon (2016)

---

Memory

See also Memory and cache – Optimization and hardware.

Allocators

• What does (template) rebind<> do? – Stack Overflow
• Why is allocator::rebind necessary when we have template template parameters? – Stack Overflow

⚓

• std::allocator – C++ reference

---

Numerics

std::bit_cast

⚓

• std::bit_cast – C++ reference
• J.Bastien. Bit-casting object representations – WG21/P0476R2 (2017)

Linear algebra support

🔗

V.Reverdy. On vectors, tensors, matrices, and hypermatrices

🎥

• G.Davidson. Standardizing a linear algebra library – Meeting C++ (2018)

⚓

• M.Hoemmen et al. Historical lessons for C++ linear algebra library standardization – WG21/P1417R0 (2019)
• G.Davidson, ​B.Steagall. A proposal to add linear algebra support to the C++ standard library – WG21/P1385R3 (2019)
• G.Davidson, ​B.Steagall. What do we need from a linear algebra library? – WG21/P1166R0 (2019)

Random numbers

🔗

• M.E.O’Neill. Everything you never wanted to know about C++’s random_device – PCG (2015)
• Why is the new random library better than std::rand()? – Stack Overflow
• Why not just use random_device? – Stack Overflow

🎥

• A.Weis. Random numbers are hard – Meeting C++ (2019)

---

Regular expressions

🔗

• Regular expressions library – C++ reference

🎥

• T.Shen. Regular expressions in C++, present and future – CppCon (2016)

---

Smart pointers

A smart pointer is a class that simulates a raw C++ pointer, and provides automatic exception-safe object lifetime management.

🔗

• Smart pointer – Wikipedia
• Boost.SmartPtr: The smart pointer library
• H.Sutter. GotW #91: Smart pointer parameters – Guru of the Week (2013)
• Y.Sharon. Smart pointers: What, why, which? (1999)
• What is a smart pointer and when should I use one? – Stack Overflow
• Why is shared_ptr<void> legal, while unique_ptr<void> is ill-formed? – Stack Overflow

🎥

• A.O’Dwyer. Back to basics: Smart pointers – CppCon (2019)
• M.Fleming. The smart pointers I wish I had – CppCon (2019)

std::unique_ptr

The std::unique_ptr class is a smart pointer with unique ownership.

🔗

• What to use std::optional or std::unique_ptr? – Stack Overflow
• Should I assign or reset a unique_ptr? – Stack Overflow
• make_unique with brace initialization – Stack Overflow
• How do I pass a unique_ptr argument to a constructor or a function? – Stack Overflow

⚓

• std::unique_ptr – C++ reference
• S.T.Lavavej. make_unique – WG21/N3588 (2013)

std::shared_ptr

The std::unique_ptr class is a smart pointer with shared ownership.

🔗

• std::shared_ptr thread safety – Stack Overflow
• A.Williams. std::shared_ptr’s secret constructor

⚓

• std::shared_ptr – C++ reference

std::enable_shared_from_this

std::enable_shared_from_this allows a member function of an object that is currently managed by a std::shared_ptr to extend the lifetime of that object dynamically by generating additional std::shared_ptr instances.

🔗

• What is the usefulness of enable_shared_from_this? – Stack Overflow

⚓

• std::enable_shared_from_this – C++ reference

std::weak_ptr

🔗

• When is std::weak_ptr useful? – Stack Overflow

⚓

• std::weak_ptr – C++ reference

std::auto_ptr

std::auto_ptr is a smart pointer with unique ownership that had been designed before rvalue references and move semantics were introduced into the language. It was deprecated in C++11 and removed in C++17.

🔗

• H.Sutter. GotW #25: auto_ptr – Guru of the Week (2009)

⚓

• std::auto_ptr – C++ reference

std::observer_ptr

std::observer_ptr is a smart pointer that takes no ownership responsibility for its pointees (non-owning pointer).

⚓

• std::experimental::observer_ptr – C++ reference
• B.Stroustrup. Abandon observer_ptr – WG21/P1408R0 (2018)
• W.E.Brown. A proposal for the world’s dumbest smart pointer – WG21/N4282 (2014)

boost::intrusive_ptr

The boost::intrusive_ptr class is a smart pointer that stores a pointer to an object with an embedded reference count, which is managed somewhere outside the smart pointer.

🔗

• B.Wicht. Boost intrusive_ptr: Faster shared pointer (2011)
• Boost intrusive pointer – Stack Overflow

⚓

• intrusive_ptr – Boost.SmartPtr
• I.Muerte. An intrusive smart pointer – WG21/P0468R1 (2018)

---

Strings

📝

• std::basic_string<T, ...> is the only container in the standard library that requires T to be a trivial standard-layout type.

🔗

• H.Sutter. GotW #29: Strings – Guru of the Week (2009)
• Why std::string does not have const char* cast – Stack Overflow
• Why doesn’t std::string provide implicit conversion to char*? – Stack Overflow

⚓

• std::basic_string – C++ reference

Short string optimization

🔗

• Meaning of acronym SSO in the context of std::string – Stack Overflow

std::string_view

🔗

• J.Miller. C++ std::string_view for better performance: An example use case (2019)

🎥

• M.Clow. string_view: When to use it and when not – CppCon (2015)
• N.MacIntosh. Evolving array_view and string_view for safe C++ code – CppCon (2015)

---

Type support

Fixed-width integer types

📝

• std::int8_t, std::int16_t, std::int32_t, and std::int64_t are guaranteed to use 2’s complement to represent negative values.

🔗

• When is uint8_t ≠ unsigned char? – Stack Overflow

Type traits

See also Type traits – Templates.

🎥

• M.Clow. Type traits: What are they and why should I use them? – CppCon (2015)

⚓

• Standard library header <type_traits> – C++ reference

std::is_trivial*

🎥

• J.Turner. Great C++ is_trivial – CppCon (2019)

---

Utilities

🔗

• Utility library – C++ reference

Function objects

🔗

• Function objects – C++ reference

🎥

• S.T.Lavavej. <functional>: What’s new, and proper usage – CppCon (2015)

Pairs and tuples

🔗

• Why can’t std::tuple<int> be trivially copyable? – Stack Overflow

🎥

• A.Meredith. How C++20 can simplify std::tuple – ACCU (2019)
• S.T.Lavavej. tuple<>: What’s new and how it works – CppCon (2016)

Sum types

std::variant

🎥

• N.Liber. The many variants of std::variant – C++Now (2019)

⚓

• std::variant – C++ reference

(std::)expected

A proposed utility class to represent expected monad.

🔗

• S.Brand. C++11/14/17 std::expected with functional-style extensions

⚓

• V.Botet, J.F.Bastien. std::expected – WG21/P0323R7 (2018)
• V.Botet, P.Talbot. A proposal to add a utility class to represent expected monad – WG21/N4109 (2014)

std::launder

🔗

• What is the purpose of std::launder? – Stack Overflow
• Where can I find what std::launder really does? – Stack Overflow

⚓

• std::launder – C++ reference

---

Tricks and subtleties

🔗

• A.O’Dwyer. Don’t inherit from standard types (2018)
• In std::exchange, why is the second template parameter defaulted? – Stack Overflow
• Why does the C++ standard algorithm count return a difference_type instead of size_t? – Stack Overflow
• Why standard container iterators don’t overload ->*? – Stack Overflow
• Why does numeric_limits work on types it does not know? – Stack Overflow

🎥

• J.Brown. This one weird trick: std::integral_constant – CppCon (2019)

---

The Standard Template Library (STL)

🔗

• Standard Template Library – Wikipedia
• History of the Standard Template Library – Wikipedia
• A.Stevens An interview with Alex Stepanov – Dr.Dobb's Journal (1995)
• What’s the difference between “STL” and “C++ standard library”? – Stack Overflow

📄

• D.R.Musser, A.A.Stepanov. A library of generic algorithms in Ada – Proceedings of ACM SIGAda, 216 (1987)

🎥

• A.Stepanov. STL and its design principles (2002)

⚓

• A.Stepanov et al. SGI STL: Source code and documentation