Introduction

Rust provides a very broad set of collections to use. We will look at most of them, see how they're used, discuss how they're implemented, and when to use and choose them. A big part of this chapter focuses on iterators. Much of Rust's flexibility comes from them, as all collections (and more!) can be used as iterators. Learning how to use them is crucial.

Throughout this chapter, we are going to use the big O notation to show how effective certain algorithms are. In case you don't know it yet, it is a way of telling how much longer an algorithm takes when working with more elements. Let's look at it briefly.

means that an algorithm is going to take the same time, no matter how much data is stored in a collection. It doesn't tell us how fast exactly it is, just that it's not going to slow down with size. This is the realistic ideal for a function. A practical example for this is accessing the first number in an infinite list of numbers: no matter how many numbers there are, you're always going to be able to instantly pick out the first one.

means that an algorithm is going to slow down by the same degree for every element. This is not good, but still okay. An example for this is printing all data in a for loop.

is really bad. It tells us that an algorithm is going to be slower and slower with every element. An example of it would be accessing data in a for loop nested in another for loop over the same data.