List / Vector / Array
Abstractions
C++
std::vector
: similar to C arrays, but dynamically-resizable;std::list
/std::forward_list
: a linked list of values; andstd::deque
: similar to avector
in that it allows random access, but also supports constant time insertion and removal from both ends of the array.
Vectors are the same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted
If the backing array of s is too small to fit all the given values a bigger array will be allocated. The returned slice will point to the newly allocated array.
Rust
std::vec::Vec
orstd::collections::VecDeque
std::collections::LinkedList
Go
Slice vs array:
- an array has a fixed size. A slice is a dynamically-sized, flexible view into the elements of an array.
[n]T
is an array ofn
values of typeT
;[]T
is a slice with elements of typeT
.- A slice does not store any data, it just describes a section of an underlying array. Changing the elements of a slice modifies the corresponding elements of its underlying array. Other slices that share the same underlying array will see those changes.
s[low : high]
, low
is included, high
is excluded. Index start from 0
. low
and high
can be ommitted (e.g. a[:10]
, a[0:]
, a[:]
).
// primes is an array
primes := [6]int{2, 3, 5, 7, 11, 13}
// s is a slice: [3 5 7]
var s []int = primes[1:4]
// slice literals
[]bool{true, true, false}
// get length
len(s)
// get capacity (num of elements in the underlying array,
// counting from the first element in the slice)
cap(s)
// if len < cap, the slice can be extended
s = s[:4]
// Creating a slice with make
b := make([]int, 0, 5) // len(b)=0, cap(b)=5
If the backing array of s
is too small to fit all the given values a bigger array will be allocated. (So it is more like a Java's ArrayList
.)
Java
ArrayList is like C++'s Vector
Create
C++
#include <vector>
std::vector<int> v {1, 2, 3, 4};
// or
std::vector<int> v = {1, 2, 3, 4};
Go
An array's length is part of its type, so arrays cannot be resized.
// array length must be a constant
var a [10]int
fmt.Printf("%T\n", a) // =>[10]int
primes := [6]int{2, 3, 5, 7, 11, 13}
Slices can be created using variables:
n := 5
a := make([]int, n)
fmt.Printf("%T\n", a) // => []int
2D array/slice:
// array
c := [5][5]uint8{}
// slice
a := make([][]uint8, dy)
for i := range a {
a[i] = make([]uint8, dx)
}
Java
Create empty:
List<Integer> v = new ArrayList<>();
// Array
String[] arr = new String[]{"A", "B", "C"};
// List
List<Integer> v =
new ArrayList<>(Arrays.asList(5, 4, 3, 2, 1));
Init Stream
Stream<Integer> intStream = Stream.of(1,2,3,4);
Copy from existing:
List<Integer> copy = new ArrayList<>(origin)
Rust
let mut l = LinkedList::new();
let v = vec![5, 4, 3, 2, 1];
Python
>>> [[0] * 4] * 4
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Repeated Values In List/Tuple
List
>>> [0] * 10
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Tuple.
>>> (0,) * 10
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
Notice the comma in (0,)
, otherwise it is scalar calculation
>>> (1) * 10
10
Init 2D array
>>> a = [[0] * 3 for _ in range(4)]
>>> a
[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
2D 8-Directions
>>> [(x, y) for x in d for y in d if x != 0 or y != 0]
[(1, 1), (1, 0), (1, -1), (0, 1), (0, -1), (-1, 1), (-1, 0), (-1, -1)]
JavaScript
const clone = originArray.slice(0);
// first 10 items.
originArray.slice(0, 10);
Add Elements
C++
Use push_back
or emplace_back
:
std::vector<int> v = {1, 2};
v.emplace_back(3);
v.push_back(4);
emplace_back
will forward the args to the constructor, while push_back
takes the value as the input:
std::vector<std::pair<std::string, int>> v = {std::make_pair("a", 1),
std::make_pair("b", 2)};
v.emplace_back("c", 3);
v.push_back(std::make_pair("d", 4));
Go
In Go, we append elements to a slice. If the backing array of s
is too small to fit all the given values a bigger array will be allocated. The returned slice will point to the newly allocated array.
s = append(s, 1)
// append multiple
x := []int{1,2,3}
y := []int{4,5,6}
x = append(x, y...)
Java
list.add()
Python
list.append()
JavaScript
// insert, front
list.unshift();
// insert, back
list.push();
Remove Element
Go
Remove last element of the slice:
if len(slice) > 0 {
slice = slice[:len(slice)-1]
}
JavaScript
// delete from back
list.pop();
// delete from front
list.shift();
Delete without changing indices of other elements (leaving a hole)
delete array[i];
Delete and shift other elements forward (modifying array in place)
var index = array.indexOf(5);
if (index > -1) {
array.splice(index, 1);
}
Delete by filtering
keys.filter((key) => key != 'foo');
Last Item
C++
vector::back
: returns a referencevector::end
: returns an iterator just past the element
Contains
C++
Use std::find
std::vector<int> v { 10, 20, 30, 40 };
int val = 20;
if (std::find(v.begin(), v.end(), val) != v.end()) {
...
}
Python
Use in
:
>>> a = [1, 2, 3]
>>> 1 in a
True
>>> 4 in a
False
JavaScript
Use includes
:
arr.includes(element);
Map
JavaScript
[1, 2, 3].map((x) => x * 2);
Python
map(lambda x: x * 2, [1, 2, 3])
Array Length
JavaScript
[1, 2, 3].length;
Python
len([1,2,3])
Join As String
Python
join
is a method of string instead of a list, since any iterable can be joined.
>>> "|".join(["a", "b", "c"])
'a|b|c'
Java 8+
String joined = String.join(",", Arrays.asList("a", "b", "c"));
or
String joined = Arrays.asList("a", "b", "c").stream().collect(Collectors.joining(","));
Manipulate before joining, e.g. to Uppercase
String joined = Arrays.asList("a", "b", "c")
.stream()
.map(String::toUpperCase)
.collect(Collectors.joining(","));
Another example:
List<BigDecimal> buffer = ...
String s = buffer.stream()
.map(x -> x.toString())
.collect(Collectors.joining(","));
Join Two Arrays
Javascript
[1].concat([2])[(1, 2)];
IndexOf
Javascript
var array = [2, 5, 9];
var index = array.indexOf(5);
Subarray / Slice
Python
arr_slice = arr[start:end]
arr[2:]
JavaScript
const arrSlice = arr.slice(start, end);
Convert To Other Type
Java
Array to Stream
Arrays.stream(array);
String to IntStream
IntStream is = "abc".chars();
Array to Immutable List
private static final Thing[] PRIVATE_VALUES = { ... };
public static final List<Thing> VALUES =
Collections.unmodifiableList(Arrays.asList(PRIVATE_VALUES));
Arrays.asList
does not return ArrayList
, so does not support addAll()
or add()
, will throw UnsupportedOperationException
Convert to string array
String[] y = x.toArray(new String[0]);
Primitive Array To List
Use boxed()
int[] nums = new int[]{1,2,3};
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
Array To List
Integer[] nums = new Integer[]{1,2,3};
List<Integer> list = Arrays.stream(nums).collect(Collectors.toList());
Create ArrayList From Array
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
Deconstruct
JavaScript
const [a, b, c] = str.split('-');
Python
>>> a, *b, c = [1, 2, 3, 4, 5, 6]
>>> a
1
>>> b
[2, 3, 4, 5]
>>> c
6
Max / Min
Java
Java 8+
int[] a = new int[]{1,2,3};
int min = Arrays.stream(a).min().getAsInt();
Flatten
Python
There's no flatten builtin, but can use list comprehension:
flat_list = [item for sublist in nestedlist for item in sublist]
which means:
for sublist in nestedlist:
for item in sublist:
flat_list.append(item)
zip
Python
Zip
>>> x = (1, 2, 3)
>>> y = ('a', 'b', 'c')
>>> z = list(zip(x, y))
>>> z
[(1, 'a'), (2, 'b'), (3, 'c')]
Unzip. Use *
to unpack z
>>> x, y = list(zip(*z))
>>> x
(1, 2, 3)
>>> y
('a', 'b', 'c')
JavaScript
const a = [1, 2, 3];
const b = ['A', 'B', 'C'];
a.map((v, i) => [v, b[i]]);
// [[1, 'A'], [2, 'B'], [3, 'C']]
Comprehensions
Python
names = [c.name for c in customers if c.admin]
MaxDiff
Given an array, find the max diff between one integer and the integers to its right. e.g. [1, 5, 3, 65, 7, 43]
, the max
is 65 - 7 = 58
.
int maxdiff(int *a, int len)
{
int m = a[0];
int mdiff = 0x80000000;
int i;
for (i = 1; i < len; i++) {
if (m - a[i] > mdiff) {
mdiff = m - a[i];
}
if (a[i] > m) {
m = a[i];
}
}
return mdiff;
}