Algorithm101 是我在 Github 上新开的 Repo,目的是边学习边总结一些基本的数据结构和算法。

万丈高楼平地起,让我们开始吧。

Array

数组(Array) 是一种线性表数据结构,通过一段连续的存储区域(内存空间)来存储元素。这句话的关键在于连续,因为连续的特性,计算机能够通过数组首地址以及数组下标计算得到偏移量,从而直接访问对应位置的数组元素,这个过程,也就是所谓的随机访问

Array in C++

以 C 的风格声明数组:

int foo[3] = {1, 2, 3};

通过 C++ 容器 Array (cppreference)使用数组:

std::array<int, 3> foo = {1, 2,3 };

std::array 是对 c 风格数组的一种封装,允许 C++ 用户像其他容器一样使用 array,主要代码如下:

template <class _Tp, size_t _Size>
struct array {
	typedef _Tp                                   value_type;
	typedef value_type&                           reference;
	// iterator 就是 native pointer
	typedef value_type*                           iterator;
	
	// 唯一的数据成员
	_Tp __elems_[_Size];
};

我们拿出一些成员函数来观察 array 的设计:

value_type* data() _NOEXCEPT {return __elems_;}

iterator begin() _NOEXCEPT {return iterator(data());}

iterator end() _NOEXCEPT {return iterator(data() + _Size);}

Array in Go

// foo := [...]int{1, 2, 3}
var foo [3]int = [...]int{1, 2, 3}

与 C++ 不同,Go 在函数调用时,传递数组并不会隐式的将数组作为指针,而是,传递这个数组的一份 Copy,也就是说 array 在 Go 中是值类型(value)。

Vector in C++

由于array限定了大小,且无法动态更改,我们在 C++ 中实际上很少使用arrayvector(cppreference) 是 STL 提供的封装动态数组的顺序容器。

std::vector<int> foo = {1, 2};
foo.push_back(3);

我们来看下 Clang 对vector的实现:

template <class _Tp, class _Allocator>
class __vector_base {
    typedef _Allocator                               allocator_type;
    typedef allocator_traits<allocator_type>         __alloc_traits;
    typedef typename __alloc_traits::pointer         pointer;
    typedef pointer                                  iterator;
    // ...
    pointer                                         __begin_;
    pointer                                         __end_;
    __compressed_pair<pointer, allocator_type> __end_cap_;
};

template <class _Tp, class _Allocator /* = allocator<_Tp> */>
class _LIBCPP_TEMPLATE_VIS vector 
	: private __vector_base<_Tp, _Allocator>
{
	// 这个 point 绕了好大一圈,实际上就是 _Tp*
	// __wrap_iter 是一个迭代器的包裹,为什么要这个 wrapper,现在还不知道
	typedef __wrap_iter<pointer>                     iterator;
};

vector 区别于 array 最重要的就是动态扩容,我们摘出push_back的代码来一窥究竟:

size_type size() const _NOEXCEPT
	{return static_cast<size_type>(this->__end_ - this->__begin_);}
	
template <class _Tp, class _Allocator>
void
vector<_Tp, _Allocator>::push_back(const_reference __x) {
	// 不懂为啥全加上了 this
    if (this->__end_ != this->__end_cap())  // 有可用空间
    {
        __alloc_traits::construct(this->__alloc(),
                                  _VSTD::__to_raw_pointer(this->__end_), __x);
        ++this->__end_; // 调整 __end_ 迭代器
    }
    else
        __push_back_slow_path(__x);
}

template <class _Tp, class _Allocator>
template <class _Up>
vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) {
    allocator_type& __a = this->__alloc();
    // 分配新的空间,重点看 __recommend(..) 就好了
    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
    __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x));
    __v.__end_++;
    // 重新给迭代器赋值
    __swap_out_circular_buffer(__v);
}

vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
{
    const size_type __ms = max_size();
    if (__new_size > __ms)
        this->__throw_length_error();
    const size_type __cap = capacity();
    if (__cap >= __ms / 2)
        return __ms;
    // 返回 2 * __cap
    return _VSTD::max<size_type>(2*__cap, __new_size);
}

vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
{
    // 释放原有空间
    __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
    // 调整迭代器
    _VSTD::swap(this->__begin_, __v.__begin_);
    _VSTD::swap(this->__end_, __v.__end_);
    _VSTD::swap(this->__end_cap(), __v.__end_cap());
    __v.__first_ = __v.__begin_;
    __invalidate_all_iterators();
}

emm,代码非常复杂,看上去也有很多的模板技巧,但是现在我们只关心vector的逻辑实现就够了。

Slice in Go

Slice 是基于数组的一种数据类型:

foo := make([]int, 3, 10)

Go Slices: usage and internals 详细描述了 Slice 的方方面面。

下面让我们深入源码观察 Slice

// 结构
type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}
// 创建 slice
func makeslice(et *_type, len, cap int) slice {
	// 根据切片的数据类型,获取切片的最大容量
	maxElements := maxSliceCap(et.size)
    // 比较切片的长度,长度值域应该在[0,maxElements]之间
	if len < 0 || uintptr(len) > maxElements {
		panic(errorString("makeslice: len out of range"))
	}
    // 比较切片的容量,容量值域应该在[len,maxElements]之间
	if cap < len || uintptr(cap) > maxElements {
		panic(errorString("makeslice: cap out of range"))
	}
    // 根据切片的容量申请内存
	p := mallocgc(et.size*uintptr(cap), et, true)
    // 返回申请好内存的切片的首地址
	return slice{p, len, cap}
}
// 动态扩容
// expand append(l1, l2...) to
//   init {
//     s := l1
//     if n := len(l1) + len(l2) - cap(s); n > 0 {
//       s = growslice_n(s, n)
//     }
//     s = s[:len(l1)+len(l2)]
//     memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
//   }
//   s
//
// l2 is allowed to be a string.
func growslice(et *_type, old slice, cap int) slice {
	// ...
	
	// 1. 扩容策略
	newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		// 如果需要的大小大于 doublecap,则新 cap 为指定的 cap
		newcap = cap
	} else {
		if old.len < 1024 {
			// 如果 old.len 小于 1024,则新 cap 为 doublecap
			newcap = doublecap
		} else {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newcap && newcap < cap {
				// 如果 old.len 大于 1024,则 old.cap 以 1.25 倍增大,直到大于指定的 cap
				newcap += newcap / 4
			}
			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

	// 2. 计算实际需要分配的空间大小
	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	// Specialize for common values of et.size.
	// For 1 we don't need any division/multiplication.
	// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
	// For powers of 2, use a variable shift.
	switch {
	case et.size == 1:
		// 旧 slice len 所需要的空间大小
		lenmem = uintptr(old.len)
		// 新 slice len 所需要的空间大小
		newlenmem = uintptr(cap)
		// 新 slice cap 所需要的空间大小
		capmem = roundupsize(uintptr(newcap))
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
	//...
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / et.size)
	}
	
	// ...

	// 3. 分配内存空间,完成 copy 和初始化工作
	var p unsafe.Pointer
	if et.kind&kindNoPointers != 0 {
		// 非指针类型,mallocgc 时不需要清零
		p = mallocgc(capmem, nil, false)
		// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
		// Only clear the part that will not be overwritten.
		// 将 [newlen:cap] 这一段赋零值
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
		// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
		p = mallocgc(capmem, et, true)
		// 指针类型,分配的空间已经清零
		if writeBarrier.enabled {
			// Only shade the pointers in old.array since we know the destination slice p
			// only contains nil pointers because it has been cleared during alloc.
			// 不太懂这个是干嘛的
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
		}
	}
	// 将之前的元素 copy 过来
	memmove(p, old.array, lenmem)

	return slice{p, old.len, newcap}
}

这里面需要注意的是,我看很多博客说如果 slice 底下的 array 还有空间,分配空间时会优先使用现有空间,但是我在代码中没看到相关逻辑,也没有在测试程序中复现这种现象。

a := [...]int{1, 2, 3, 4, 5, 6, 7, 8} // L1
b := a[:1:1]   // L2
b = append(b, 0)  // L3

// a: [1, 2, 3, 4, 5, 6, 7, 8]
// b: [1, 0]

即,在 L3 中,b 实际是被分配到一块新的内存中了,并不会影响原有数组。