tbb::concurrent_vector

和stl::vector相比，tbb::concurrent_vector不支持insert和erase操作，且不保证内存是连续的。因为不支持insert操作，故而无法实现由一个线程进行插入排序，并同时由另一个线程去遍历的场景。TBB中也没有平衡树的支持，估计是因为，插入/删除时的节点移动操作很多，细粒度锁不容易带来更佳性能的原因。

template<typename T, class A>
class concurrent_vector: protected internal::allocator_base<T, A>,
                         private internal::concurrent_vector_base;
typedef concurrent_vector_base_v3 concurrent_vector_base;
// VC10 defines its own v4 template
struct concurrent_vector_base_v3::segment_t {
void* array;
};
atomic<segment_t*> my_segment;
segment_t my_storage[pointers_per_short_table];
// pointers_per_short_table = 3

concurrent_vector_base_v3::concurrent_vector_base_v3():

将指针数组my_storage的元素赋值为NULL, 然后将my_storage赋值给my_segment。

concurrent_vector_base_v3::segment_index_of(index):

即 log2(index|1)

concurrent_vector_base_v3::segment_base (k):

(1 << k & ~1)，和2**k（即1<<k）不同，当k为0时，结果为0而不是1

concurrent_vector_base_v3::segment_base_index_of(index):

将index调整为segment内的索引，并返回是第几个segment。

concurrent_vector_base_v3::segment_size(k):

返回第k个segment的大小。1 << k，k==0时应该返回2才对呀？

从逻辑上看，concurrent_vector内部的segments布局如下，总会是2,2,4,8,16,32...

但是实际分配的空间，则可能是16,16,32,64，取决于第一次的reservation, growth 或 assignment操作。如果第一次要求分配10个元素，那么heap上分配的空间是，比10大的最小的2的幂数，即16。

（插图来自http://blogs.msdn.com/b/nativeconcurrency，VC10中的concurrent_vector和TBB中的是同出一脉的。）

concurrent_vector::push_back (item)

调用internal_push_back(sizeof(T), k)去分配一段空间，然后调用internal_loop_guide（ntrails为1）将item拷贝到分配的空间上，最后返回iterator

concurrent_vector_base_v3::internal_push_back(element_size, &index)

使用__TBB_FetchAndIncrementWacquire将m_early_size加1，并将原来的size赋值给tmp和index。调用helper::extend_table_if_necessary(*this, k_old, tmp)，在必要时扩展segment table，调用helper::acquire_segment获取一个segment的基地址，计算偏移并返回对应的地址。

libittnotify是一些profiling的函数，在编译时可以打开或关闭。ITT=>Intel Threading Tools。