concurrent_vector.h

Go to the documentation of this file.

/***
* ==++==
*
* Copyright (c) Microsoft Corporation.  All rights reserved.
* Microsoft would like to acknowledge that this concurrency data structure implementation
* is based on the Intel implementation of its Threading Building Blocks ("Intel Material").
*
* ==--==
* =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
*
* concurrent_vector.h
*
* =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
****/

/*
    Intel Material Copyright 2005-2008 Intel Corporation.  All Rights Reserved.
*/

#pragma once

#include <crtdefs.h>
#include <memory>
#include <iterator>
#include <limits>
#include <algorithm>
#include <cstring>
#include <crtdbg.h>
#include <concrt.h>

#define _PPL_CONTAINER

#if !(defined (_M_X64) || defined (_M_IX86) || defined (_M_ARM) || defined (_M_ARM64))
    #error ERROR: Concurrency Runtime is supported only on X64, X86, ARM, and ARM64 architectures.
#endif  /* !(defined (_M_X64) || defined (_M_IX86) || defined (_M_ARM) || defined (_M_ARM64)) */

#if defined (_M_CEE)
    #error ERROR: Concurrency Runtime is not supported when compiling /clr.
#endif  /* defined (_M_CEE) */

#pragma pack(push,_CRT_PACKING)
#pragma warning (push)
#pragma warning (disable: 4510 4512 4610)  // disable warnings for compiler unable to generate constructor
#pragma push_macro("new")
#undef new


namespace Concurrency
{

template<typename _Ty, class _Ax = std::allocator<_Ty> >
class concurrent_vector;

namespace details
{

    // Bad allocation marker.
    #define _BAD_ALLOC_MARKER reinterpret_cast<void*>(63)

    // Base class of concurrent vector implementation.
    class _Concurrent_vector_base_v4
    {
    protected:

        // Basic types declarations.
        typedef size_t _Segment_index_t;
        typedef size_t _Size_type;

        // Size constants
        static const _Segment_index_t _Default_initial_segments = 1; // 2 initial items

        // Number of slots for segment's pointers inside the class
        static const _Segment_index_t _Pointers_per_short_table = 3; // to fit into 8 words of entire structure
        static const _Segment_index_t _Pointers_per_long_table = sizeof(_Segment_index_t) * 8; // one segment per bit

        // Segment pointer. Can be zero-initialized.
        struct _Segment_t
        {
            void* _My_array;
        };

        // Data fields

        // allocator function pointer
        void* (__cdecl *_My_vector_allocator_ptr)(_Concurrent_vector_base_v4 &, size_t);

        // embedded storage of segment pointers
        _Segment_t _My_storage[_Pointers_per_short_table];

        // Methods

        _Concurrent_vector_base_v4()
        {
            _My_early_size = 0;
            _My_first_block = 0; // here is not _Default_initial_segments
            for( _Segment_index_t _I = 0; _I < _Pointers_per_short_table; _I++)
                _My_storage[_I]._My_array = NULL;
            _My_segment = _My_storage;
        }
        _CONCRTIMP ~_Concurrent_vector_base_v4();

        _CONCRTIMP static _Segment_index_t __cdecl _Segment_index_of( _Size_type _Index );

        static _Segment_index_t _Segment_base( _Segment_index_t _K )
        {
            return (_Segment_index_t(1)<<_K & ~_Segment_index_t(1));
        }

        static _Segment_index_t _Segment_base_index_of( _Segment_index_t &_Index )
        {
            _Segment_index_t _K = _Segment_index_of( _Index );
            _Index -= _Segment_base(_K);
            return _K;
        }

        static _Size_type _Segment_size( _Segment_index_t _K )
        {
            return _Segment_index_t(1)<<_K; // fake value for _K==0
        }

        // An operation on an n-element array starting at begin.
        typedef void (__cdecl *_My_internal_array_op1)(void* _Begin, _Size_type _N );

        // An operation on n-element destination array and n-element source array.
        typedef void (__cdecl *_My_internal_array_op2)(void* _Dst, const void* _Src, _Size_type _N );

        // Internal structure for shrink_to_fit().
        struct _Internal_segments_table
        {
            _Segment_index_t _First_block;
            void* _Table[_Pointers_per_long_table];
        };

        _CONCRTIMP void _Internal_reserve( _Size_type _N, _Size_type _Element_size, _Size_type _Max_size );
        _CONCRTIMP _Size_type _Internal_capacity() const;
        void _Internal_grow( _Size_type _Start, _Size_type _Finish, _Size_type _Element_size, _My_internal_array_op2 _Init, const void *_Src );
        _Size_type _Internal_grow_segment( const _Size_type _Start, _Size_type _Finish, _Size_type _Element_size, _Segment_t** _PPSegment, _Size_type* _PSegStart, _Size_type* _PSegFinish );
        _CONCRTIMP _Size_type _Internal_grow_by( _Size_type _Delta, _Size_type _Element_size, _My_internal_array_op2 _Init, const void *_Src );
        _CONCRTIMP void* _Internal_push_back( _Size_type _Element_size, _Size_type& _Index );
        _CONCRTIMP _Segment_index_t _Internal_clear( _My_internal_array_op1 _Destroy );
        void _Internal_truncate( _Size_type _Old_size, _Size_type _New_size, _Size_type _Element_size, _My_internal_array_op1 _Destroy);
        _CONCRTIMP void* _Internal_compact( _Size_type _Element_size, void *_Table, _My_internal_array_op1 _Destroy, _My_internal_array_op2 _Copy );
        _CONCRTIMP void _Internal_copy( const _Concurrent_vector_base_v4& _Src, _Size_type _Element_size, _My_internal_array_op2 _Copy );
        _CONCRTIMP void _Internal_assign( const _Concurrent_vector_base_v4& _Src, _Size_type _Element_size,
                              _My_internal_array_op1 _Destroy, _My_internal_array_op2 _Assign, _My_internal_array_op2 _Copy );
        _CONCRTIMP void _Internal_throw_exception(_Size_type) const;
        _CONCRTIMP void _Internal_swap(_Concurrent_vector_base_v4&);

        _CONCRTIMP void _Internal_resize( _Size_type _New_size, _Size_type _Element_size, _Size_type _Max_size, _My_internal_array_op1 _Destroy, _My_internal_array_op2 _Init, const void* _Src);
        _CONCRTIMP _Size_type _Internal_grow_to_at_least_with_result( _Size_type _New_size, _Size_type _Element_size, _My_internal_array_op2 _Init, const void *_Src );

        // Count of segments in the first block.
        _Subatomic<_Size_type> _My_first_block;

        // Requested size of vector.
        _Subatomic<_Size_type> _My_early_size;

        // Pointer to the segments table.
        _Subatomic<_Segment_t*> _My_segment;


    private:
        // Private functionality.
        class _Helper;
        friend class _Helper;
    };

    typedef _Concurrent_vector_base_v4 _Concurrent_vector_base;

    // Meets requirements of a forward iterator for STL.*/
    template<typename _Container, typename _Value>
    class _Vector_iterator
    {
        // concurrent_vector over which we are iterating.
        _Container* _My_vector;

        // Index into the vector.
        size_t _My_index;

        // Caches _My_vector-&gt;_Internal_subscript(_My_index)
        mutable _Value* _My_item;

        template<typename _C, typename _Ty>
        friend _Vector_iterator<_C,_Ty> operator+( ptrdiff_t _Offset, const _Vector_iterator<_C,_Ty>& _Vec );

        template<typename _C, typename _Ty, typename _U>
        friend bool operator==( const _Vector_iterator<_C,_Ty>&, const _Vector_iterator<_C,_U>& );

        template<typename _C, typename _Ty, typename _U>
        friend bool operator<( const _Vector_iterator<_C,_Ty>&, const _Vector_iterator<_C,_U>& );

        template<typename _C, typename _Ty, typename _U>
        friend ptrdiff_t operator-( const _Vector_iterator<_C,_Ty>&, const _Vector_iterator<_C,_U>& );

        template<typename _C, typename _U>
        friend class ::Concurrency::details::_Vector_iterator;

        template<typename _Ty, class _Ax>
        friend class ::Concurrency::concurrent_vector;

        _Vector_iterator( const _Container& _Vec, size_t _Index, void* _Ptr = NULL )
            : _My_vector(const_cast<_Container*>(&_Vec)),
              _My_index(_Index),
              _My_item(static_cast<_Value*>(_Ptr))
        {
        }

    public:
        // Default constructor
        _Vector_iterator()
            : _My_vector(NULL), _My_index(~size_t(0)), _My_item(NULL)
        {
        }

        _Vector_iterator( const _Vector_iterator<_Container,typename _Container::value_type>& _Other )
            : _My_vector(_Other._My_vector),
              _My_index(_Other._My_index),
              _My_item(_Other._My_item)
        {
        }

        _Vector_iterator operator+( ptrdiff_t _Offset ) const
        {
            return _Vector_iterator( *_My_vector, _My_index+_Offset );
        }
        _Vector_iterator& operator+=( ptrdiff_t _Offset )
        {
            _My_index+=_Offset;
            _My_item = NULL;
            return *this;
        }
        _Vector_iterator operator-( ptrdiff_t _Offset ) const
        {
            return _Vector_iterator( *_My_vector, _My_index-_Offset );
        }
        _Vector_iterator& operator-=( ptrdiff_t _Offset )
        {
            _My_index-=_Offset;
            _My_item = NULL;
            return *this;
        }
        _Value& operator*() const
        {
            _Value* _Item = _My_item;
            if( !_Item )
                _Item = _My_item = &_My_vector->_Internal_subscript(_My_index);
            _CONCRT_ASSERT( _Item==&_My_vector->_Internal_subscript(_My_index));  // corrupt cache
            return *_Item;
        }
        _Value& operator[]( ptrdiff_t _K ) const
        {
            return _My_vector->_Internal_subscript(_My_index+_K);
        }
        _Value* operator->() const
        {
            return &operator*();
        }

        // Pre increment
        _Vector_iterator& operator++()
        {
            size_t _K = ++_My_index;
            if( _My_item )
            {
                // Following test uses 2's-complement wizardry.
                if( (_K& (_K-2))==0 )
                {
                    // _K is a power of two that is at least _K-2.
                    _My_item= NULL;
                }
                else
                {
                    ++_My_item;
                }
            }
            return *this;
        }

        // Pre decrement
        _Vector_iterator& operator--()
        {
            _CONCRT_ASSERT( _My_index>0 ); // operator--() applied to iterator already at beginning of concurrent_vector.
            size_t _K = _My_index--;
            if( _My_item )
            {
                // Following test uses 2's-complement wizardry.
                if( (_K& (_K-2))==0 )
                {
                    // k is a power of two that is at least k-2.
                    _My_item= NULL;
                }
                else
                {
                    --_My_item;
                }
            }
            return *this;
        }

        // Post increment
        _Vector_iterator operator++(int)
        {
            _Vector_iterator _Result = *this;
            operator++();
            return _Result;
        }

        // Post decrement
        _Vector_iterator operator--(int)
        {
            _Vector_iterator _Result = *this;
            operator--();
            return _Result;
        }

        // STL support

        typedef ptrdiff_t difference_type;
        typedef _Value value_type;
        typedef _Value* pointer;
        typedef _Value& reference;
        typedef std::random_access_iterator_tag iterator_category;
    };

    template<typename _Container, typename _Value>
    struct std::_Is_checked_helper<_Vector_iterator<_Container, _Value> >
        : public true_type
    {   // mark _Vector_iterator as checked. This suppresses warning C4996
    };

    template<typename _Container, typename _Ty>
    _Vector_iterator<_Container,_Ty> operator+( ptrdiff_t _Offset, const _Vector_iterator<_Container,_Ty>& _Vec )
    {
        return _Vector_iterator<_Container,_Ty>( *_Vec._My_vector, _Vec._My_index+_Offset );
    }

    template<typename _Container, typename _Ty, typename _U>
    bool operator==( const _Vector_iterator<_Container,_Ty>& _I, const _Vector_iterator<_Container,_U>& _J )
    {
        return _I._My_index==_J._My_index && _I._My_vector == _J._My_vector;
    }

    template<typename _Container, typename _Ty, typename _U>
    bool operator!=( const _Vector_iterator<_Container,_Ty>& _I, const _Vector_iterator<_Container,_U>& _J )
    {
        return !(_I==_J);
    }

    template<typename _Container, typename _Ty, typename _U>
    bool operator<( const _Vector_iterator<_Container,_Ty>& _I, const _Vector_iterator<_Container,_U>& _J )
    {
        return _I._My_index<_J._My_index && _I._My_vector == _J._My_vector;
    }

    template<typename _Container, typename _Ty, typename _U>
    bool operator>( const _Vector_iterator<_Container,_Ty>& _I, const _Vector_iterator<_Container,_U>& _J )
    {
        return _J<_I;
    }

    template<typename _Container, typename _Ty, typename _U>
    bool operator>=( const _Vector_iterator<_Container,_Ty>& _I, const _Vector_iterator<_Container,_U>& _J )
    {
        return !(_I<_J);
    }

    template<typename _Container, typename _Ty, typename _U>
    bool operator<=( const _Vector_iterator<_Container,_Ty>& _I, const _Vector_iterator<_Container,_U>& _J )
    {
        return !(_J<_I);
    }

    template<typename _Container, typename _Ty, typename _U>
    ptrdiff_t operator-( const _Vector_iterator<_Container,_Ty>& _I, const _Vector_iterator<_Container,_U>& _J )
    {
        return ptrdiff_t(_I._My_index)-ptrdiff_t(_J._My_index);
    }

    template<typename _Ty, class _Ax>
    class _Allocator_base
    {
    public:
        typedef typename _Ax::template
            rebind<_Ty>::other _Allocator_type;
        _Allocator_type _My_allocator;

        _Allocator_base()
            : _My_allocator()
        {
        }

        _Allocator_base(const _Allocator_type &_Al)
            : _My_allocator(_Al)
        {
        }
    };

} // namespace details


template<typename _Ty, class _Ax>
class concurrent_vector: protected details::_Allocator_base<_Ty, _Ax>,
                         private details::_Concurrent_vector_base_v4
{
private:
    typedef concurrent_vector<_Ty, _Ax> _Myt;

    template<typename _C, typename _U>
    friend class details::_Vector_iterator;

public:

    
    typedef details::_Concurrent_vector_base_v4::_Size_type size_type;

    
    typedef typename details::_Allocator_base<_Ty, _Ax>::_Allocator_type allocator_type;

    
    typedef _Ty value_type;

    
    typedef ptrdiff_t difference_type;

    
    typedef _Ty& reference;

    
    typedef const _Ty& const_reference;

    
    typedef _Ty *pointer;

    
    typedef const _Ty *const_pointer;

    
    typedef details::_Vector_iterator<concurrent_vector,_Ty> iterator;

    
    typedef details::_Vector_iterator<concurrent_vector,const _Ty> const_iterator;

    
    typedef std::reverse_iterator<iterator> reverse_iterator;

    
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    
    explicit concurrent_vector(const allocator_type &_Al = allocator_type())
        : details::_Allocator_base<_Ty, _Ax>(_Al)
    {
        _My_vector_allocator_ptr = &_Internal_allocator;
    }

    
    concurrent_vector( const concurrent_vector& _Vector)
        : details::_Allocator_base<_Ty, _Ax>(_Vector.get_allocator())
    {
        _My_vector_allocator_ptr = &_Internal_allocator;
        _Internal_copy(_Vector, sizeof(_Ty), &_Copy_array);
    }

    
    template<class M>
    concurrent_vector( const concurrent_vector<_Ty, M>& _Vector, const allocator_type& _Al = allocator_type() )
        : details::_Allocator_base<_Ty, _Ax>(_Al)
    {
        _My_vector_allocator_ptr = &_Internal_allocator;
        _Internal_copy(_Vector._Internal_vector_base(), sizeof(_Ty), &_Copy_array);
    }


    
    concurrent_vector( concurrent_vector && _Vector)
        : details::_Allocator_base<_Ty, _Ax>(_Vector.get_allocator())
    {
        _My_vector_allocator_ptr = &_Internal_allocator;
        _Concurrent_vector_base_v4::_Internal_swap(_Vector._Internal_vector_base());
    }

    
    explicit concurrent_vector(size_type _N)
    {
        _My_vector_allocator_ptr = &_Internal_allocator;
        if ( !_N ) return;
        _Internal_reserve(_N, sizeof(_Ty), max_size()); _My_early_size = _N;
        _CONCRT_ASSERT( _My_first_block == _Segment_index_of(_N-1)+1 );
        _Initialize_array(static_cast<_Ty*>(_My_segment[0]._My_array), NULL, _N);
    }

    
    concurrent_vector(size_type _N, const_reference _Item, const allocator_type& _Al = allocator_type())
        : details::_Allocator_base<_Ty, _Ax>(_Al)
    {
        _My_vector_allocator_ptr = &_Internal_allocator;
        _Internal_assign( _N, _Item );
    }

    
    template<class _InputIterator>
    concurrent_vector(_InputIterator _Begin, _InputIterator _End, const allocator_type &_Al = allocator_type())
        : details::_Allocator_base<_Ty, _Ax>(_Al)
    {
        _My_vector_allocator_ptr = &_Internal_allocator;
        _Internal_assign(_Begin, _End, static_cast<_Is_integer_tag<std::numeric_limits<_InputIterator>::is_integer> *>(0) );
    }

    
    concurrent_vector& operator=( const concurrent_vector& _Vector )
    {
        if( this != &_Vector )
            _Concurrent_vector_base_v4::_Internal_assign(_Vector, sizeof(_Ty), &_Destroy_array, &_Assign_array, &_Copy_array);
        return *this;
    }

    
    template<class M>
    concurrent_vector& operator=( const concurrent_vector<_Ty, M>& _Vector )
    {
        if( static_cast<void*>( this ) != static_cast<const void*>( &_Vector ) )
        {
            _Concurrent_vector_base_v4::_Internal_assign(_Vector._Internal_vector_base(),
                                                         sizeof(_Ty), &_Destroy_array, &_Assign_array, &_Copy_array);
        }
        return *this;
    }

    
    concurrent_vector& operator=( concurrent_vector && _Vector )
    {
        if( static_cast<void*>( this ) != static_cast<const void*>( &_Vector ) )
        {
            _Concurrent_vector_base_v4::_Internal_swap(_Vector._Internal_vector_base());
            _Vector.clear();
        }
        return *this;
    }

    
    iterator grow_by( size_type _Delta )
    {
        return iterator(*this, _Delta ? _Internal_grow_by( _Delta, sizeof(_Ty), &_Initialize_array, NULL ) : _My_early_size);
    }

    
    iterator grow_by( size_type _Delta, const_reference _Item )
    {
        return iterator(*this, _Delta ? _Internal_grow_by( _Delta, sizeof(_Ty), &_Initialize_array_by, static_cast<const void*>(&_Item) ) : _My_early_size);
    }

    
    iterator grow_to_at_least( size_type _N )
    {
        size_type _M = 0;
        if( _N )
        {
            _M = _Internal_grow_to_at_least_with_result( _N, sizeof(_Ty), &_Initialize_array, NULL );
            if( _M > _N )
                _M = _N;
        }
        return iterator(*this, _M);
    };

    
    iterator push_back( const_reference _Item )
    {
        size_type _K;
        void *_Ptr = _Internal_push_back(sizeof(_Ty), _K);
        _Internal_loop_guide _Loop(1, _Ptr);
        _Loop._Init(&_Item);
        return iterator(*this, _K, _Ptr);
    }

    
    iterator push_back( _Ty &&_Item )
    {
        size_type _K;
        void *_Ptr = _Internal_push_back(sizeof(_Ty), _K);
        new (_Ptr) _Ty( std::move(_Item));
        return iterator(*this, _K, _Ptr);
    }

    
    reference operator[]( size_type _Index )
    {
        return _Internal_subscript(_Index);
    }

    
    const_reference operator[]( size_type _Index ) const
    {
        return _Internal_subscript(_Index);
    }

    
    reference at( size_type _Index )
    {
        return _Internal_subscript_with_exceptions(_Index);
    }

    
    const_reference at( size_type _Index ) const
    {
        return _Internal_subscript_with_exceptions(_Index);
    }

    
    size_type size() const
    {
        size_type _Sz = _My_early_size;
        size_type _Cp = _Internal_capacity();
        return _Cp < _Sz ? _Cp : _Sz;
    }

    
    bool empty() const
    {
        return !_My_early_size;
    }

    
    size_type capacity() const
    {
        return _Internal_capacity();
    }

    
    void reserve( size_type _N )
    {
        if( _N )
            _Internal_reserve(_N, sizeof(_Ty), max_size());
    }

    
    void shrink_to_fit();

    
    void resize(size_type _N)
    {
        _Internal_resize( _N, sizeof(_Ty), max_size(), _Destroy_array, _Initialize_array, NULL);
    }

    
    void resize(size_type _N, const _Ty& _Val)
    {
        _Internal_resize( _N, sizeof(_Ty), max_size(), _Destroy_array, _Initialize_array_by, static_cast<const void*>(&_Val) );
    }

    
    size_type max_size() const
    {
        return (~size_type(0))/sizeof(_Ty);
    }

    
    iterator begin()
    {
        return iterator(*this,0);
    }

    
    iterator end()
    {
        return iterator(*this,size());
    }

    
    const_iterator begin() const
    {
        return const_iterator(*this,0);
    }

    
    const_iterator end() const
    {
        return const_iterator(*this,size());
    }

    
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }

    
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }

    
    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }

    
    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }

    
    const_iterator cbegin() const
    {
        return (((const _Myt *)this)->begin());
    }

    
    const_iterator cend() const
    {
        return (((const _Myt *)this)->end());
    }

    
    const_reverse_iterator crbegin() const
    {
        return (((const _Myt *)this)->rbegin());
    }

    
    const_reverse_iterator crend() const
    {
        return (((const _Myt *)this)->rend());
    }

    
    reference front()
    {
        _CONCRT_ASSERT( size()>0 );
        return static_cast<_Ty*>(_My_segment[0]._My_array)[0];
    }

    
    const_reference front() const
    {
        _CONCRT_ASSERT( size()>0 );
        return static_cast<_Ty*>(_My_segment[0]._My_array)[0];
    }

    
    reference back()
    {
        _Size_type sz = size();
        _CONCRT_ASSERT( sz > 0 );
        return _Internal_subscript( sz-1 );
    }

    
    const_reference back() const
    {
        _Size_type sz = size();
        _CONCRT_ASSERT( sz > 0 );
        return _Internal_subscript( sz-1 );
    }

    
    allocator_type get_allocator() const
    {
        return this->_My_allocator;
    }

    
    void assign(size_type _N, const_reference _Item)
    {
        clear();
        _Internal_assign( _N, _Item );
    }

    
    template<class _InputIterator>
    void assign(_InputIterator _Begin, _InputIterator _End)
    {
        clear();
        _Internal_assign( _Begin, _End, static_cast<_Is_integer_tag<std::numeric_limits<_InputIterator>::is_integer> *>(0) );
    }

    
    void swap(concurrent_vector &_Vector)
    {
        if( this != &_Vector )
        {
            _Concurrent_vector_base_v4::_Internal_swap(static_cast<_Concurrent_vector_base_v4&>(_Vector));
            std::swap(this->_My_allocator, _Vector._My_allocator);
        }
    }

    
    void clear()
    {
        _Internal_clear(&_Destroy_array);
    }

    
    ~concurrent_vector()
    {
        _Segment_t *_Table = _My_segment;
        _Internal_free_segments( reinterpret_cast<void**>(_Table), _Internal_clear(&_Destroy_array), _My_first_block );
        // base class destructor call
    }

    const ::Concurrency::details::_Concurrent_vector_base_v4 &_Internal_vector_base() const { return *this; }
    ::Concurrency::details::_Concurrent_vector_base_v4 &_Internal_vector_base() { return *this; }
private:

    // Allocate _K items
    static void * __cdecl _Internal_allocator(::Concurrency::details::_Concurrent_vector_base_v4 &_Vb, size_t _K)
    {
        return static_cast<concurrent_vector<_Ty, _Ax>&>(_Vb)._My_allocator.allocate(_K);
    }
    // Free _K segments from table
    void _Internal_free_segments(void *_Table[], _Segment_index_t _K, _Segment_index_t _First_block);

    // Get reference to element at given _Index.
    _Ty& _Internal_subscript( size_type _Index ) const;

    // Get reference to element at given _Index with errors checks
    _Ty& _Internal_subscript_with_exceptions( size_type _Index ) const;

    // assign _N items by copying _Item
    void _Internal_assign(size_type _N, const_reference _Item);

    // helper class
    template<bool B> class _Is_integer_tag;

    // assign integer items by copying when arguments are treated as iterators. See C++ Standard 2003 23.1.1 p9
    template<class _I>
    void _Internal_assign(_I _First, _I _Last, _Is_integer_tag<true> *)
    {
        _Internal_assign(static_cast<size_type>(_First), static_cast<_Ty>(_Last));
    }
    // inline proxy assign by iterators
    template<class _I>
    void _Internal_assign(_I _First, _I _Last, _Is_integer_tag<false> *) {
        internal_assign_iterators(_First, _Last);
    }
    // assign by iterators
    template<class _I>
    void internal_assign_iterators(_I _First, _I _Last);

    // Construct _N instances of _Ty, starting at "begin".
    static void __cdecl _Initialize_array( void* _Begin, const void*, size_type _N );

    // Construct _N instances of _Ty, starting at "begin".
    static void __cdecl _Initialize_array_by( void* _Begin, const void* _Src, size_type _N );

    // Construct _N instances of _Ty, starting at "begin".
    static void __cdecl _Copy_array( void* _Dst, const void* _Src, size_type _N );

    // Assign _N instances of _Ty, starting at "begin".
    static void __cdecl _Assign_array( void* _Dst, const void* _Src, size_type _N );

    // Destroy _N instances of _Ty, starting at "begin".
    static void __cdecl _Destroy_array( void* _Begin, size_type _N );

    // Exception-aware helper class for filling a segment by exception-danger operators of user class
    class _Internal_loop_guide
    {
    public:
        const pointer _My_array;
        const size_type _N;
        size_type _I;
        _Internal_loop_guide(size_type _NTrials, void *_Ptr)
            : _My_array(static_cast<pointer>(_Ptr)), _N(_NTrials), _I(0)
        {
        }

        void _Init()
        {
            for(; _I < _N; ++_I)
                new( &_My_array[_I] ) _Ty();
        }
        void _Init(const void *_Src)
        {
            for(; _I < _N; ++_I)
                new( &_My_array[_I] ) _Ty(*static_cast<const _Ty*>(_Src));
        }
        void _Copy(const void *_Src)
        {
            for(; _I < _N; ++_I)
                new( &_My_array[_I] ) _Ty(static_cast<const _Ty*>(_Src)[_I]);
        }
        void _Assign(const void *_Src)
        {
            for(; _I < _N; ++_I)
                _My_array[_I] = static_cast<const _Ty*>(_Src)[_I];
        }
        template<class _It> void _Iterate(_It &_Src)
        {
            for(; _I < _N; ++_I, ++_Src)
                new( &_My_array[_I] ) _Ty( *_Src );
        }
        ~_Internal_loop_guide()
        {
            if(_I < _N) // if exception raised, do zeroing on the rest of items
                std::memset(_My_array+_I, 0, (_N-_I)*sizeof(value_type));
        }
    private:
        void operator=(const _Internal_loop_guide&); // prevent warning:  assign operator can't be generated
    };
};


template<typename _Ty, class _Ax>
void concurrent_vector<_Ty, _Ax>::shrink_to_fit()
{
    _Internal_segments_table _Old = { 0, nullptr };
    try
    {
        if( _Internal_compact( sizeof(_Ty), &_Old, &_Destroy_array, &_Copy_array ) )
            _Internal_free_segments( _Old._Table, _Pointers_per_long_table, _Old._First_block ); // Free joined and unnecessary segments
    }
    catch(...)
    {
        if( _Old._First_block ) // Free segment allocated for compacting. Only for support of exceptions in ctor of user _Ty[pe]
            _Internal_free_segments( _Old._Table, 1, _Old._First_block );
        throw;
    }
}

template<typename _Ty, class _Ax>
void concurrent_vector<_Ty, _Ax>::_Internal_free_segments(void *_Table[], _Segment_index_t _K, _Segment_index_t _First_block)
{
    // Free the arrays
    while( _K > _First_block )
    {
        --_K;
        _Ty* _Array = static_cast<_Ty*>(_Table[_K]);
        _Table[_K] = NULL;
        if( _Array > _BAD_ALLOC_MARKER ) // check for correct segment pointer
            this->_My_allocator.deallocate( _Array, _Segment_size(_K) );
    }
    _Ty* _Array = static_cast<_Ty*>(_Table[0]);
    if( _Array > _BAD_ALLOC_MARKER )
    {
        _CONCRT_ASSERT( _First_block > 0 );
        while(_K > 0)
            _Table[--_K] = NULL;
        this->_My_allocator.deallocate( _Array, _Segment_size(_First_block) );
    }
}

template<typename _Ty, class _Ax>
_Ty& concurrent_vector<_Ty, _Ax>::_Internal_subscript( size_type _Index ) const
{
    _CONCRT_ASSERT( _Index<_My_early_size ); // index out of bounds
    size_type _J = _Index;
    _Segment_index_t _K = _Segment_base_index_of( _J );
    _CONCRT_ASSERT( _My_segment != (_Segment_t*)_My_storage || _K < _Pointers_per_short_table ); // index is under construction
    // no need in load_with_acquire because the thread works in its own space or gets
    _Ty* _Array = static_cast<_Ty*>(_My_segment[_K]._My_array);
    _CONCRT_ASSERT( _Array != _BAD_ALLOC_MARKER ); // instance may be broken by bad allocation; use at() instead
    _CONCRT_ASSERT( _Array != NULL ); // index is being allocated
    return _Array[_J];
}

template<typename _Ty, class _Ax>
_Ty& concurrent_vector<_Ty, _Ax>::_Internal_subscript_with_exceptions( size_type _Index ) const
{
    if( _Index >= _My_early_size )
        _Internal_throw_exception(0); // throw std::out_of_range
    size_type _J = _Index;
    _Segment_index_t _K = _Segment_base_index_of( _J );
    if( _My_segment == (_Segment_t*)_My_storage && _K >= _Pointers_per_short_table )
        _Internal_throw_exception(1); // throw std::out_of_range
    void *_Array = _My_segment[_K]._My_array; // no need in load_with_acquire
    if( _Array <= _BAD_ALLOC_MARKER ) // check for correct segment pointer
        _Internal_throw_exception(2); // throw std::range_error
    return static_cast<_Ty*>(_Array)[_J];
}

template<typename _Ty, class _Ax>
void concurrent_vector<_Ty, _Ax>::_Internal_assign(size_type _N, const_reference _Item)
{
    _CONCRT_ASSERT( _My_early_size == 0 );
    if( !_N )
        return;
    _Internal_reserve(_N, sizeof(_Ty), max_size());
    _My_early_size = _N;
    _Segment_index_t _K = 0;
    _Size_type _Sz = _Segment_size( _My_first_block );
    while (_Sz < _N)
    {
        _Initialize_array_by(static_cast<_Ty*>(_My_segment[_K]._My_array), static_cast<const void*>(&_Item), _Sz);
        _N -= _Sz;
        if (!_K)
        {
            _K = _My_first_block;
        }
        else {
            ++_K;
            _Sz <<= 1;
        }
    }
    _Initialize_array_by(static_cast<_Ty*>(_My_segment[_K]._My_array), static_cast<const void*>(&_Item), _N);
}

template<typename _Ty, class _Ax> template<class _I>
void concurrent_vector<_Ty, _Ax>::internal_assign_iterators(_I _First, _I _Last)
{
    _CONCRT_ASSERT(_My_early_size == 0);
    size_type _N = std::distance(_First, _Last);
    if( !_N ) return;
    _Internal_reserve(_N, sizeof(_Ty), max_size());
    _My_early_size = _N;
    _Segment_index_t _K = 0;
    _Size_type _Sz = _Segment_size( _My_first_block );
    while (_Sz < _N)
    {
        _Internal_loop_guide _Loop(_Sz, _My_segment[_K]._My_array);
        _Loop._Iterate(_First);
        _N -= _Sz;
        if (!_K)
        {
            _K = _My_first_block;
        }
        else {
            ++_K;
            _Sz <<= 1;
        }
    }

    _Internal_loop_guide _Loop(_N, _My_segment[_K]._My_array);
    _Loop._Iterate(_First);
}

template<typename _Ty, class _Ax>
void __cdecl concurrent_vector<_Ty, _Ax>::_Initialize_array( void* _Begin, const void *, size_type _N )
{
    _Internal_loop_guide _Loop(_N, _Begin); _Loop._Init();
}

template<typename _Ty, class _Ax>
void __cdecl concurrent_vector<_Ty, _Ax>::_Initialize_array_by( void* _Begin, const void *_Src, size_type _N )
{
    _Internal_loop_guide _Loop(_N, _Begin); _Loop._Init(_Src);
}

template<typename _Ty, class _Ax>
void __cdecl concurrent_vector<_Ty, _Ax>::_Copy_array( void* _Dst, const void* _Src, size_type _N ) {
    _Internal_loop_guide _Loop(_N, _Dst); _Loop._Copy(_Src);
}

template<typename _Ty, class _Ax>
void __cdecl concurrent_vector<_Ty, _Ax>::_Assign_array( void* _Dst, const void* _Src, size_type _N )
{
    _Internal_loop_guide _Loop(_N, _Dst); _Loop._Assign(_Src);
}

#pragma warning(push)
#pragma warning(disable: 4189) /* local variable _Array is initialized but not used - the compiler optimizes away calls to the destructor */

template<typename _Ty, class _Ax>
void __cdecl concurrent_vector<_Ty, _Ax>::_Destroy_array( void* _Begin, size_type _N )
{
    _Ty* _Array = static_cast<_Ty*>(_Begin);
    for( size_type _J=_N; _J>0; --_J )
        _Array[_J-1].~_Ty(); // destructors are supposed to not throw any exceptions
}

#pragma warning(pop)


template<typename _Ty, class A1, class A2>
inline bool operator==(const concurrent_vector<_Ty, A1> &_A, const concurrent_vector<_Ty, A2> &_B)
{
    // Simply:    return _A.size() == _B.size() && std::equal(_A.begin(), _A.end(), _B.begin());
    if(_A.size() != _B.size())
        return false;
    typename concurrent_vector<_Ty, A1>::const_iterator _I(_A.begin());
    typename concurrent_vector<_Ty, A2>::const_iterator _J(_B.begin());
    for(; _I != _A.end(); ++_I, ++_J)
    {
        if( !(*_I == *_J) )
            return false;
    }
    return true;
}


template<typename _Ty, class A1, class A2>
inline bool operator!=(const concurrent_vector<_Ty, A1> &_A, const concurrent_vector<_Ty, A2> &_B)
{
    return !(_A == _B);
}


template<typename _Ty, class A1, class A2>
inline bool operator<(const concurrent_vector<_Ty, A1> &_A, const concurrent_vector<_Ty, A2> &_B)
{
    return (std::lexicographical_compare(_A.begin(), _A.end(), _B.begin(), _B.end()));
}


template<typename _Ty, class A1, class A2>
inline bool operator>(const concurrent_vector<_Ty, A1> &_A, const concurrent_vector<_Ty, A2> &_B)
{
    return _B < _A;
}


template<typename _Ty, class A1, class A2>
inline bool operator<=(const concurrent_vector<_Ty, A1> &_A, const concurrent_vector<_Ty, A2> &_B)
{
    return !(_B < _A);
}


template<typename _Ty, class A1, class A2>
inline bool operator>=(const concurrent_vector<_Ty, A1> &_A, const concurrent_vector<_Ty, A2> &_B)
{
    return !(_A < _B);
}


template<typename _Ty, class _Ax>
inline void swap(concurrent_vector<_Ty, _Ax> &_A, concurrent_vector<_Ty, _Ax> &_B)
{
    _A.swap( _B );
}

} // namespace Concurrency

namespace concurrency = ::Concurrency;

#pragma pop_macro("new")
#pragma warning (pop)
#pragma pack(pop)