book

Data Structures and Algorithms with the C++ STL

Name: Data Structures and Algorithms with the C++ STL
Author: John Farrier
ISBN: 9781835468555

by John Farrier

February 2024

Intermediate to advanced

458 pages

10h 33m

English

Packt Publishing

Read now

Unlock full access

Data Structures and Algorithms with the C++ STL
ContributorsAbout the authorAbout the reviewer
Preface
Who this book is forWhat this book coversTo get the most out of this bookDownload the example code filesConventions usedGet in touchShare Your ThoughtsDownload a free PDF copy of this book
Part 1: Mastering std::vector
Chapter 1: The Basics of std::vector
Technical requirementsThe significance of std::vectorA basic comparison of C-style arrays and std::vectorComparison of C-style arrays and std::vector for memory managementDeclaring and initializing std::vectorDeclaring a vectorInitializing a vectorAccessing elementsRandom accessAccessing the first and last elementsVector sizeAdding and removing elementsAdding elementsRemoving elementsCapacityPrefer using empty() when possibleClearing all elementsSummary
Chapter 2: Mastering Iterators with std::vector
Technical requirementsTypes of iterators in the STLInput iteratorsOutput iteratorsForward iteratorsReverse iteratorsBidirectional iteratorsRandom access iteratorsBasic iteration techniques with std::vectorIterating over std::vectorBasic iteration using iteratorsUsing constant iteratorsBenefits of iterationUsing std::begin and std::endUnderstanding iterator requirementsRange-based for loopsOverview of range-based for loopsWhen to use range-based for loopsModifying elements during iterationCreating a custom iteratorThe appeal of custom iteratorsCore requirementsIterator categories and their specialtiesA custom iterator exampleCustom iterator challenges and use casesIllustrative use cases of custom iteratorsSummary
Chapter 3: Mastering Memory and Allocators with std::vector
Technical requirementsUnderstanding capacity versus sizeRevisiting the basicsWhat exactly is capacity?Why this distinction mattersLooking under the hoodResizing and reserving memoryThe power of resize()Enter reserve()Optimizing with shrink_to_fit()Real-world relevanceCustom allocator basicsThe role and responsibility of an allocatorUnder the hood – the allocator interfaceTrade-offs and the need for custom allocatorsChoosing std::allocator over new, delete, and managed pointersCreating a custom allocatorCustom allocators – the heart of memory flexibilityUnderstanding the motivation behind custom allocatorsMemory pools – a popular custom allocator strategyUnlocking the potential of custom allocatorsAllocators and container performanceWhy allocators matter in performanceThe performance characteristics of std::allocatorWhen to consider alternative allocatorsProfiling – the key to making informed decisionsSummary
Chapter 4: Mastering Algorithms with std::vector
Technical requirementsSorting a vectorGetting started with std::sortThe engine under the hood – introsortEfficiency unparalleled – O(n log n)Sorting in descending orderSorting custom data typesPitfalls and precautionsSearching elementsLinear search with std::findBinary search techniquesUsing std::lower_bound and std::upper_boundBinary search versus linear search – efficiency and versatilityManipulating vectorsTransforming with std::copyReversing elements with std::reverseRotating vectors with std::rotateFilling a vector with std::fillPutting manipulation to useConsiderations in manipulationCustom comparators and predicatesUnderstanding comparatorsThe power of predicatesCrafting effective comparators and predicatesUser-defined structs and classesUnderstanding container invariants and iterator invalidationUnderstanding iterator invalidationStrategies to counteract invalidationDealing with invalidation in multi-threaded scenariosSummary
Chapter 5: Making a Case for std::vector
Performance considerationsComparison with other containersThe memory advantageThe takeawayPractical use casesA resizable dynamic array at heartData processing and analyticsGraphics and game developmentBeyond just containersVersatility and efficiencyA testament to versatilityEfficiency isn’t just about speedA safe default, but not the only optionSummary
Part 2: Understanding STL Data Structures
Chapter 6: Advanced Sequence Container Usage
Technical requirementsstd::arrayPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexityInterface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::vectorPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::dequePurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexityInterface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::listPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexityInterface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::forward_listPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::stringPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practices

Chapter 7: Advanced Ordered Associative Container Usage
Technical requirementsstd::setPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::mapPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::multisetPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::multimapPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practices
Chapter 8: Advanced Unordered Associative Container Usage
Technical requirementsstd::unordered_setPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::unordered_mapPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::unordered_multisetPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::unordered_multimapPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practices
Chapter 9: Advanced Container Adaptor Usage
Technical requirementsstd::stackPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::queuePurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::priority_queuePurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::flat_setPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationBest practicesstd::flat_mapPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexityInterface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationBest practicesstd::flat_multisetPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationBest practicesstd::flat_multimapPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexityInterface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationBest practices
Chapter 10: Advanced Container View Usage
Technical requirementsstd::spanPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexityInterface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationExampleBest practicesstd::mdspanPurpose and suitabilityIdeal use casesPerformanceMemory managementThread safetyExtensions and variantsSorting and searching complexitySpecial interface and member functionsComparisonsInteractions with algorithmsExceptionsCustomizationBest practices
Part 3: Mastering STL Algorithms
Chapter 11: Fundamental Algorithms and Searching
Technical requirementsSortingChecking conditionsCounting and findingSearching and comparisonBest practicesSummary
Chapter 12: Manipulation and Transformation
Technical requirementsCopying and moving in STL containersCopying semantics in the STLMoving semantics in the STLCopying versus moving – a deliberate choiceExploring return value optimizationFilling and generating in STL containersPopulating with static assignmentDynamic generation with the STLEnsuring relevance and efficiencyRemoving and replacing in STL containersThe essence of removalReplacementA balancing actSwapping and reversing in STL containersSwapping – the art of interchangingReversing – a glimpse from the endDeduplication – singling out the uniqueSampling – a slice of the wholeBest practicesSummary
Chapter 13: Numeric and Range -Based Operations
Technical requirementsBasic numeric operationsGenerating sequences with std::iotaSumming elements with std::accumulateAdjacent elements and their interactions with std::adjacent_differenceInner products with std::inner_productAdvanced numeric operationsOperations on sorted rangesBest practicesSummary
Chapter 14: Permutations, Partitions, and Heaps
Technical requirementsPartitioningstd::partition and its powerChecking partitions with std::is_partitionedThe utility of std::partition_pointPartitioning beyond basic sequencesPermutationsGenerating permutations with std::next_permutationPredecessor permutations with std::prev_permutationShuffling elements randomly with std::shuffleRotating sequences with std::rotateHeap operationsConstructing heaps with std::make_heapAdding and removing elements – std::push_heap and std::pop_heapHeap-based sorting – the power of std::sort_heapChecking heap validity with std::is_heapThe significance of heaps in today’s computingBest practicesSummary
Chapter 15: STL with Ranges
Technical requirementsIntroduction to rangesUnderstanding the essence of rangesWhy the shift to ranges?A glimpse into range operationsLooking ahead – the power of modern STLRanges for sorting algorithmsTraditional STL sorting – a recapRange-based sorting – the basicsEmbracing composability in sortingAdvantages beyond syntax – why ranges shine in sortingThe revolution of ranges in sortingRanges for searching algorithmsFinding elegance – range-based searchingChaining and filtering – the beauty of composabilityUnderstanding views in searchesThe extended toolkit – more than just findBest practicesEmbracing the power of chainingGuarding against range pitfalls – lifetime awarenessPerformance considerations – laziness and evaluationReadability over brevity – striking the balanceAdhering to range idioms – keep it standardSummary
Part 4: Creating STL-Compatible Types and Algorithms
Chapter 16: Creating STL-Types Containers
Technical requirementsThe advantages of STL-compatible typesOne language, one approachReusability – the gift that keeps givingEfficiency in the familiarPaving the way forwardInteracting with STL algorithmsThe centrality of iteratorsAdapting to algorithmic expectationsError handling and feedback mechanismsAlgorithmic efficiency and your typeLaying a solid foundationEssential requirements for compatibilityThe cornerstones of compatibilityThe vitality of iteratorsEmbracing value semanticsOperational guaranteesSize and capacity queriesElement access and manipulationConsistency in exception safetyLooking forward to enhanced integrationCrafting iterators for custom typesChoosing the right iterator typeCrafting the basic componentsAddressing iterator categories with type traitsEnd iterators – signifying the finish lineConsiderations for const iteratorsPerformance optimizations and advanced techniquesEmbracing the iterative spiritEffective operator overloadingOperator overloading in C++Considerations in overloadingImplementing arithmetic operators for custom typesOverloading relational operators for clear comparisonsSimplifying tasks with assignment and compound assignmentStream operators for efficient I/OOperator precedence and associativity in overloadingThe role of operator overloading in C++Creating custom hash functionsInteroperability with STL containersCustom type semanticsThe characteristics of a good hash functionExample for the creation of a custom hash functionSummary
Chapter 17: Creating STL -Compatible Algorithms
Technical requirementsTemplate functionsA primer on function templatesVariadic templates – multiplicity in templatesSFINAE – fine-tuning template substitutionHarnessing SFINAE with std::enable_ifOverloadingCrafting multiple algorithm versions for STL containersFunction resolution – navigating the intricaciesOverloading with care – clarity and consistencyCreating generic algorithmsToward a type-independent approachEmbracing iterators – the bridge to genericsPredicates – customizing algorithm behaviorThe magic of functors – enhancing flexibilityCustomizing existing algorithmsLooking at the decorator pattern in actionHarnessing the power of lambda functionsMixing patterns with lambdas for ultimate customizationSummary
Chapter 18: Type Traits and Policies
Technical requirementsUnderstanding and using type traitsEnhancing code adaptability with type traitsEmpowering metaprogramming with type traitsToward more informed and adaptable codeUtilizing type traits with the STLWorking with data typesWorking with algorithmsUnderstanding and using policies in C++Benefits with respect to the STLBuilding modular components using policiesPotential challengesThe role of policies in modern C++Using policies with the STLMemory allocation policiesSorting policies for versatile algorithmsFine-tuning data structures with policiesSummary
Part 5: STL Data Structures and Algorithms: Under the Hood
Chapter 19: Exception Safety
Technical requirementsBasic exception safetyThe pivotal role of program invariants in the STLResource integrity – the guardian of robust softwareHarnessing the STL for basic exception safetyStrong exception safetyNavigating STL containers with strong guaranteesCrafting custom STL containers with strong guaranteesInfusing exception safety into custom STL algorithmsException safety is the path to robust applicationsThe effect of noexcept on STL operationsAn introduction to noexceptApplication to STL data typesApplication to STL algorithmsSummary
Chapter 20: Thread Safety and Concurrency with the STL
Technical requirementsConcurrency versus thread safetyThread safety – a pillar for stable concurrencyThe interplay of concurrency and thread safetyChallenges and rewardsConcurrency without thread safety – a recipe for chaosUnderstanding thread safetyThread safety in STL containers – laying the groundworkGrasping the thread-safe nature of STL algorithmsRace conditions – the ghosts in the machineSafeguarding concurrency – the way forwardRace conditionsSteering clear of a silent peril – race conditions in the STLThe anatomy of a race condition in the STLMore than meets the eyeAnticipating race conditionsSafeguarding your code – a proactive stanceMutexes and locksFrom manual to automatic – lock guards and unique locksAvoiding the stalemate – deadlock preventionIncorporating mutexes with STL containersSTL containers and thread safetyWhen safety needs reinforcements – concurrent modificationsContainer iterators – the fragile bridgeContainers with a built-in shield – concurrent containersSpecific container concernsBehaviors of std::vector in multi-threadingCharacteristics of std::list in concurrencyConsiderations with associative containersConcurrency aspects of unordered containersInsights into container adaptorsConcurrency support within the STLIntroduction to threadsThe advent of asynchronous tasksAtomic operationsPotential concurrent challengesUsing the STL’s concurrency featuresUsing std::thread, std::async, std::future, and thread -local storageInitiating threads using std::threadManaging asynchronous operations with std::async and std::futurePreserving data consistency using thread-local storageIntegrating tools for proficient concurrencyConcurrent data structures in the STLThe STL’s concurrency-optimized containersStriving for maximum efficiency in concurrent environmentsBest practices in actionSummary
Chapter 21: STL Interaction with Concepts and Coroutines
Technical requirementsConceptsA brief introduction to conceptsRefined constraints in STL algorithmsEffectively constraining templatesEnhanced data structures with explicit requirementsCustom concepts and STL interactionsPotential challenges and caveatsCoroutinesUnderstanding coroutines – a refresherSTL algorithms and coroutine integrationCoroutines and STL data structuresPotential synergies with ranges and viewsLooking ahead – a paradigm shiftSummary
Chapter 22: Parallel Algorithms with the STL
Technical requirementsIntroduction to execution policiesThe <execution> header– enabling parallelism in STL algorithmsImplementing parallel executionReflecting on the transition to parallel STLIncorporating execution policiesIntegrating policies with standard algorithmsUnderstanding parallel execution policiesSelecting the appropriate execution policyThe impact of constexpr on algorithms and containersEvolution of constexprAlgorithms and the role of constexprContainers and constexpr integrationPerformance considerationsParallelism overheadDetermining optimal data sizeData access and synchronization challengesFalse sharing – a subtle performance issueLoad balancingThe importance of profilingSummary
Index
Why subscribe?
Other Books You May EnjoyPackt is searching for authors like youShare Your ThoughtsDownload a free PDF copy of this book

Content preview from Data Structures and Algorithms with the C++ STL

14 Permutations, Partitions, and Heaps

This chapter explores some of the most essential yet often overlooked aspects of the algorithmic library of the C++ Standard Template Library (STL). The chapter sheds light on sequence organization through partitioning, sequence variation via permutations, and the fascinating world of heap-based operations. These operations are the backbone of many advanced algorithms and data structures. By understanding and mastering them, developers can enhance the efficiency of their applications, optimize data handling, and ensure the integrity of their datasets.

In this chapter, we will cover the following topics related to STL:

Partitioning
Permutations
Heap operations
Best practices

Technical requirements

The ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

C++ Data Structures and Algorithm Design Principles

Publisher Resources

ISBN: 9781835468555

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Data Structures and Algorithms with the C++ STL

by John Farrier

14

Permutations, Partitions, and Heaps

Technical requirements

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.