---
# System prepended metadata

title: Iterators and Algorithms to Know

---



# Iterators and Algorithms to Know

- Note that passing the name of a function into another function allows you to emulate the *higher order* feature of Functional Programming 
```cpp=
int main() { 
  auto out_int[](int i){ cout << i << endl; }
  for_each(..., ..., out_int);
  // this is a valid operation
}
```
- These are called **function objects**

# Iterators 
- Similar to array pointer arithmetic, iterators are a way to look at memory values in an array. Every container has an iterator defined with `C.begin()` (first element) and `C.end()` (pointing to just after the end of the container)

- Example: 
```cpp=
vector<int> V = {1, 2, 3, 4, 5}; 

for(vector<int>::iterator p = V.begin(); p != V.end(); ++p) { 
  cout << *p << endl; 
}
```

- Common Operations (Remember, all iterators are standardized)
  - `operator*` - Element at current position (return dereference)
  - `operator->` - Member Selection from current pos (return ptr)
  - `operator++/--` - move to next/prev element 
  - `operator==` - compare for positional equality
  - `operator=` - assign an iterator 
- (most of these are seen above)

- Can be categorized into input, output, forward, bidirectional (list, set, multiset, map, multimap), random access (vector, deque, string), or contiguous (adjacemtn in memory -- array, string, vector) (Contiguity is C++17 onwards)


### Common Iterators for Convenience 
- `istream_iterator<T>(obj)/ name(obj)` - no object provides default, this iterator lets you treat an input stream as an array of sorts 
- `ostream_iterator<T>^^(see above)` - this iterator lets you treat an output stream as an array of sorts
- `istringstream` - simulates string input for `operator>>`
- `stringstream` - simulates a string as an input stream for output 


# Algorithms 
- C++ STL Algorithms are common ways to solve problems that have been written time and time again. 
- Some of these include `copy`, `transform`, etc. 

### Common Algorithms and Parameters to Know: 
- `accumulate(begin, end, initial_value)` - Python `sum()`
- `sort(begin, end)` - Python `.sort()` -- List is the only stl container that has its own .sort() member
- `find(begin, end, element)` - Search Algo, returns iterator
  - `find_if(begin, end, condition)` - Returns iterator to first element that satisfies the condition 
- `transform(start_iter, end_iter, copy_iter, operation)` - transforms a set of values by mapping `operation` on top of them 
- `copy(start, end, output)` - copies from start->end into output
- `for_each(start, end, func)` - applies `func` to each element between start and end 
  - if the function takes by reference, mutable access is possible in this manner 
- `remove(start, end, ele)` and `remove_if(start, end, func)` - self-explanatory, though remove removes *all* occurences of the element provided 
- `unique(start, end)` - removes all duplicates in the range 
- `generate(start, end, function_that_returns_value)` - fill the container with the function 
- Note that all parameters that aren't explicity some variation of "element/ele" represent a function object, usually a lambda, that you apply

**IMPORTANT NOTE ABOUT `remove`, `remove_if`, AND `unique`**: When applied, they move all the elements to remove to the back of the container. These functions then return iterators to the first element to remove. For example, for vectors: 
```cpp=
std::vector<int> v {1, 2, 3, 4, 5, 5}; 
auto it = std::unique(v.start(), v.end()); 
v.erase(it, v.end()) // THIS IS WHAT ACTUALLY PERFORMS DELETION!!
```


## Ranges 
- Ranges are used automatically in for-loops, but also abstract away the `C.start()/end()` syntax that has become very prevalent. 
- `ranges::sort(v)` can replace `algorithms::sort(v.begin(), v.end())`
  - they are a more unified way to write these types of repetitive algorithms 


# Exceptions 
- C++ STL Exceptions are common exceptions that you would encounter in languages like Java or Python (base class `Exception`)
- Imported from `<stdexcept>` and `exception` is the base class