# [retrieval algorithm] 01-STL

## Why do you suddenly think of the algorithm to retrieve?

The last time I seriously studied and reviewed the algorithm was three years ago. At that time, it was for school recruitment. After that, the algorithm seems to become less important. I just do a good job in front-end development, but when I become more and more skilled in business development, I find my vision will become narrower and narrower.

The breadth and depth of program development are equally important. Maybe it will not be used directly in our current work, but mastering the underlying knowledge such as algorithms and design patterns is the premise for us to go further. I think it's time to pick up the forgotten algorithms and reserve more basic knowledge for our next three years.

As a front-end development, the algorithm code implementation of this series will be implemented by TypeScript. At the same time, some problems will be posted to facilitate hands-on practice.

## Introduction to STL

Standard Template Library, or "Standard Template Library", is a set of standard components supported by C + + compiler by default.

This is the first thing I learned about algorithms and data structures. It is also the most commonly used library in algorithm competitions. However, this review is mainly to learn common data structures and will not seriously introduce the usage of STL. At the same time, it also explores a question often asked on the Internet: is there a library like STL in JavaScript?

## container

Definition: data structure independent of data type

## Type of container

### Sequential container

• Vector: vector
• List: double ended list
• Stack: stack
• Queue: queue

map: mapping

Set: ordered set

## Sequential container

vector, list and queue are easy to be confused. The main differences in C + + are the storage mode in memory and the supported operations.

1. The difference between vector and C + + array is that vector does not require programmers to allocate memory space themselves.
2. vector and queue are continuous storage, and list is discontinuous storage (double linked list).
3. Queue supports inserting elements at the head and end of the queue, while vector only supports inserting elements at the end of the queue.
4. list supports efficient insertion and deletion, but random access is inefficient.
5. The difference between heap priority queue and stack is first in first out (FIFO) and first in last out (FILO).

These sequential containers are the built-in object Array in JavaScript (js is an object-based language).

The supported methods are shown in this document

https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array

Here is a brief summary:

### JavaScript array object

#### forEach: traversal

```array.forEach(function(item, index, array) {
console.log(item, index)
})
```

#### push: adds an element to the end of the array

```let newLength = array.push('Orange')
```

#### pop: deletes the element at the end of the array

```let last = array.pop()
```

#### shift: delete array header elements

```let first = array.shift()
```

```let newLength = array.unshift('Strawberry')
```

#### indexOf/lastIndexOf: find the index of an element in the array

```let pos = fruits.indexOf('Banana')
//lastIndexOf: index of the last
let pos = fruits.lastIndexOf('Banana')
```

#### splice: deletes an element through the index

```let removedItem = array.splice(pos, 1)
//Delete multiple elements from an index location
let removedItem = array.splice(pos, n)
//Copy an array
let shallowCopy = fruits.slice() //The default values for begin and end are 0 and end
```

#### concat: merge arrays

```const array3 = array1.concat(array2);
```

#### find/findIndex: find qualified elements

```const found = array1.find(element => element > 10);
//findIndex returns the index
const isLargeNumberIndex = array1.findIndex(element => element > 13);
```

#### Flat: flat array

```const arr1 = [0, 1, 2, [3, 4]];

console.log(arr1.flat());
// expected output: [0, 1, 2, 3, 4]

const arr2 = [0, 1, 2, [[[3, 4]]]];

console.log(arr2.flat(2));
// expected output: [0, 1, 2, [3, 4]]
```

#### Map: map / flatMap: map and flatten the array

```let arr1 = ["it's Sunny in", "", "California"];

arr1.map(x => x.split(" "));
// [["it's","Sunny","in"],[""],["California"]]

arr1.flatMap(x => x.split(" "));
// ["it's","Sunny","in", "", "California"]
//It is equivalent to using map and flat(1) together, but it is more efficient
arr1.map(x => x.split(" ")).flat(1);
// ["it's","Sunny","in", "", "California"]
```

#### includes: whether to include a value

```array.includes('cat')
```

#### join: concatenate into a string

```const elements = ['Fire', 'Air', 'Water'];

console.log(elements.join('-'));
// expected output: "Fire-Air-Water"
```

#### reduce: recursively execute the function on the element and return the value / reducereight: execute from the right

```const array1 = [1, 2, 3, 4];
const reducer = (previousValue, currentValue) => previousValue + currentValue;

// 1 + 2 + 3 + 4
console.log(array1.reduce(reducer));
// expected output: 10

// 5 + 1 + 2 + 3 + 4
console.log(array1.reduce(reducer, 5));
// expected output: 15
```

#### reverse: returns the inverted array, and the original array will also be changed

```const reversed = array1.reverse();
```

#### some: judge whether there are qualified elements

```array.some(element => element % 2 === 0)
```

## Associated container

js, Map and Set are new data types in ES6 standard. Please refer to teacher Liao Xuefeng's tutorial

https://www.liaoxuefeng.com/wiki/1022910821149312/1023024181109440

### Map in JavaScript

```var m = new Map([['Michael', 95], ['Bob', 75], ['Tracy', 85]]);
m.get('Michael'); // 95
```
```var m = new Map(); // Empty Map
m.set('Bob', 59);
```

### Set in JavaScript

```var s1 = new Set(); // Empty Set
var s2 = new Set([1, 2, 3]); // Including 1, 2 and 3
s; // Set {1, 2, 3, 4}
s.delete(3);
s; // Set {1, 2, 4}
s.has(1); //true
s.clear(); //Clear set
```

## Related topics

Title: "valid parentheses": use of stack

Question: https://leetcode-cn.com/problems/valid-parentheses/

Solution: https://leetcode-cn.com/problems/valid-parentheses/solution/typescript-you-xiao-de-gua-hao-zhan-de-y-lnv8/

Title: use of rainwater collection stack

Question: https://leetcode-cn.com/problems/trapping-rain-water/