`
qiezi
  • 浏览: 497294 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

仿STL的vector,写了一组array操作方法。

    博客分类:
  • D
阅读更多
文档从MSDN抄过来的,稍稍改了一下。
module array;

struct random_access_iterator(T)
{
private:
	alias random_access_iterator!(T) self_type;
	T[] array;
	size_t pos;

public:
	static self_type opCall(T[] array, size_t pos)
	{
		self_type ret;
		ret.array = array;
		ret.pos   = pos;
		return ret;
	}

	T[] get_array()
	{
		return array;
	}

	size_t get_pos()
	{
		return pos;
	}

	T opCall()
	{
		return array[pos];
	}

	void opAssign(T value)
	{
		array[pos] = value;
	}

	void check_array(T[] array)
	{
		if (array !is this.array)
			throw new Exception("not same array object");
		if (this.pos > array.length)
			throw new Exception("invalid iterator");
	}

	self_type
	opAdd(int delta)
	{
		return self_type(this.array, this.pos + delta);
	}

	self_type
	opAdd_r(int delta)
	{
		return opAdd(delta);
	}

	self_type
	opPostInc()
	{
		return opAddAssign(1);
	}

	self_type
	opAddAssign(int delta)
	{
		this.pos += delta;
		if (this.pos > this.array.length)
			this.pos = this.array.length;
		return *this;
	}

	self_type
	opSub(int delta)
	{
		return self_type(this.array, this.pos - delta);
	}

	self_type
	opSub_r(int delta)
	{
		return opSub(delta);
	}

	self_type
	opPostSub()
	{
		return opSubAssign(1);
	}

	self_type
	opSubAssign(int delta)
	{
		this.pos -= delta;
		if (this.pos > this.array.length)
			this.pos = this.array.length;
		return *this;
	}

	self_type
	opNeg()
	{
		int pos = (-this.pos) % this.array.length;
		return self_type(this.array, pos);
	}

	T opCast()
	{
		return this.array[this.pos];
	}

	int opCmp(self_type rhs)
	{
		if (this.array != rhs.array)
			throw new Exception("can't compare iterators of different array");
		return cast(int)this.pos - cast(int)rhs.pos;
	}

	int opEquals(self_type rhs)
	{
		if (this.array == rhs.array && 
			this.pos == rhs.pos)
			return 1;
		return 0;
	}
}

template iterator(T : T[])
{
	alias random_access_iterator!(T) iterator;
}

/******************************************************************************
 * Returns an element at a specified location in the array.
 *
 * Returns: 
 *     A value to the element subscripted in the argument. 
 *     If pos is greater than the size of the array, at throws an exception. 
 *
 * Params:
 *     array = Array object.
 *     pos   = The subscript or position number of the element to reference 
 *             in the array.
 * 
 * Example:
 * --------------------------------------
 * // array_at.d
 * voud main( )
 * {
 *    int[] v1;
 *    
 *    v1.push_back( 10 );
 *    v1.push_back( 20 );
 * 
 *    int i = v1.at( 0 );
 *    int j = v1.at( 1 );
 *    dout << "The first element is " << i << endl;
 *    dout << "The second element is " << j << endl;
 * }
 * --------------------------------------
 *
 * Output:
 *         The first element is 10<br />
 *         The second element is 20
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *****************************************************************************/
T at(T)(inout T[] array, int pos)
{
	return array[pos];
}

unittest
{
	printf("test array.at\n\0");

	int[] array = [1,2,3];
	assert(array.at(0) == 1);
	assert(array.at(1) == 2);
	assert(array.at(2) == 3);
	assert(array == [1,2,3]);
}

/******************************************************************************
 * Returns last element of the array.
 *
 * Returns:
 *          The last element of the array. If the array is empty, the return 
 *          value is undefined.
 *
 * Params:
 *     array = Array object.
 *
 * Remarks: 
 *          When compiling with _SECURE_SCL 1, a runtime error will occur if 
 *          you attempt to access an element in an empty array. See Checked 
 *          Iterators for more information.
 *
 * Example:
 * -------------------------------------
 * // array_back.d
 * void main() {
 *    int[] v1;
 *    
 *    v1.push_back( 10 );
 *    v1.push_back( 11 );
 * 
 *    int i = v1.back( );
 * 
 *    dout << "The last integer of v1 is " << i << endl;
 * }
 * ------------------------------------
 *
 * Output:
 *          The last integer of v1 is 11
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *
 * See_Also:
 *          front and back
 *****************************************************************************/
T back(T)(inout T[] array)
{
	version(_SECURE_SCL)
	{
		return array[$-1];
	}
	else
	{
		T result;
		if (!array.empty())
			result = array[$-1];
		return result;
	}
}

unittest
{
	printf("test array.back\n\0");

	int[] array = [1,2,3];
	int b = array.back();
	assert(b == 3);
	assert(array == [1,2,3]);
}


/******************************************************************************
 * Returns the number of elements that the array could contain without 
 * allocating more storage.
 *
 * Returns: The current length of storage allocated for the array.
 *
 * Params:
 *     array = Array object.
 *
 * Remarks: The member function resize will be more efficient if sufficient 
 *          memory is allocated to accommodate it. Use the member function 
 *          reserve to specify the amount of memory allocated. <br />
 *          This function is <b>deprecated</b>.
 *
 * Example:
 * ------------------------------------
 * // array_capacity.d
 * 
 * void main( )
 * {
 *    int[] v1;
 *    
 *    for (int i=0; i<16; ++i)
 *       v1.push_back( 1 );
 *    dout << "The length of storage allocated is "
 *         << v1.capacity( ) << "." << endl;
 * 
 *    v1.push_back( 2 );
 *    dout << "The length of storage allocated is now "
 *         << v1.capacity( ) << "." << endl;
 * }
 * ------------------------------------
 *
 * Output:
 *         The length of storage allocated is 16.<br />
 *         The length of storage allocated is now 32.
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *
 * See_Also:
 *         array.size and array.capacity
 ******************************************************************************/
// deprecated
size_t capacity(T)(inout T[] array)
{
	if (array.length <= 16)
		return 16;
	for (size_t i=32; true; i *= 2)
	{
		if (i > array.length)
			return i;
		if (i > (1 << 30))
			return size_t.max;
	}
	return size_t.max;
}

unittest
{
	printf("test array.capacity\n\0");

	int[] array = [];
	assert(array.capacity() == 16);

	int[] array1 = [1];
	assert(array1.capacity() == 16);

	int[] array2 = [1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,16];
	assert(array2.capacity() == 16);

	int[] array3 = [1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,16,17];
	assert(array3.capacity() == 32);
}


/******************************************************************************
 * Erases the elements of the array.
 *
 * Params:
 *     array = Array object.
 * 
 * Example:
 * ------------------------------------
 * // array_clear.d
 * 
 * void main( )
 * {
 *    int[] v1;
 *    
 *    v1.push_back( 10 );
 *    v1.push_back( 20 );
 *    v1.push_back( 30 );
 * 
 *    dout << "The size of v1 is " << v1.size( ) << endl;
 *    v1.clear( );
 *    dout << "The size of v1 after clearing is " << v1.size( ) << endl;
 * }
 * ------------------------------------
 * 
 * Output:
 *         The size of v1 is 3<br />
 *         The size of v1 after clearing is 0
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 ******************************************************************************/
void clear(T)(inout T[] array)
{
	array.length = 0;
}

unittest
{
	printf("test array.clear\n\0");

	int[] array = [1,2,3];
	array.clear();
	assert(array.length == 0);
}


/******************************************************************************
 * Tests if the array is empty.
 *
 * Returns:
 *          true if the array is empty; false if the array is not empty.
 *
 * Params:
 *     array = Array object.
 *
 * Example:
 * ------------------------------------
 * // array_empty.d
 * 
 * void main( )
 * {
 *    int[] v1;
 * 
 *    v1.push_back( 10 );
 * 
 *    if ( v1.empty( ) )
 *       dout << "The array is empty." << endl;
 *    else
 *       dout << "The array is not empty." << endl;
 * }
 * ------------------------------------

 * Output:
 *         The array is not empty.
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *****************************************************************************/
bool empty(T)(inout T[] array)
{
	return 0 == array.length;
}

unittest
{
	printf("test array.empty\n\0");

	int[] array = [1,2,3];
	assert(array.empty() == false);
	int[] array1 = [];
	assert(array1.empty() == true);
}


/******************************************************************************
 * Returns a random-access iterator to the first element in the container.
 *
 * Returns: A random-access iterator addressing the first element in the array
 *          or to the location succeeding an empty array.
 *
 * Params:
 *     array = Array object.
 *
 * Example:
 * ------------------------------------
 * // array_begin.d
 * 
 * void main( )
 * {
 *    int[] c1;
 *    iterator!(int[]) c1_Iter;
 *    
 *    c1.push_back( 1 );
 *    c1.push_back( 2 );
 * 
 *    c1_Iter = c1.begin( );
 *    dout << "The first element of c1 is "<< *c1_Iter << endl;
 * 
 *    c1_Iter = 20;
 *    c1_Iter = c1.begin( );
 *    dout << "The first element of c1 is now "<< c1_Iter << endl;
 * }
 * ------------------------------------
 *
 * Output:  
 *         The first element of c1 is 1<br >
 *         The first element of c1 is now 20
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *
 * See_Also:
 *         array.empty, array.erase, and array.push_back
 *****************************************************************************/
iterator!(T[]) begin(T)(inout T[] array)
{
	return iterator!(T[])(array, 0);
}

unittest
{
	printf("test array.begin\n\0");

	int[] array = [1,2,3];
	auto begin = array.begin();
	assert(begin == iterator!(int[])(array, 0));
}


/******************************************************************************
 * Returns a random-access iterator that points just beyond the end of the 
 * array.
 *
 * Returns:
 *          random-access iterator to the end of the array object. If the array
 *          is empty, array.end == array.begin.
 *
 * Params:
 *     array = Array object.
 *
 * Example:
 * ------------------------------------
 * // array_end.d
 *
 * void main( )
 * {
 *    int[] v1;
 *    iterator!(int[]) v1_Iter;
 *    
 *    v1.push_back( 1 );
 *    v1.push_back( 2 );
 * 
 *    for ( v1_Iter = v1.begin( ) ; v1_Iter != v1.end( ) ; v1_Iter++ )
 *       cout << v1_Iter.get << endl;
 * }
 * ------------------------------------
 *
 * Output:
 *         1<br />
 *         2
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *****************************************************************************/
iterator!(T[]) end(T)(inout T[] array)
{
	return iterator!(T[])(array, array.length);
}

unittest
{
	printf("test array.end\n\0");

	int[] array = [1,2,3];
	auto end = array.end();
	assert(end == iterator!(int[])(array, 3));
}

/******************************************************************************
 * Removes an element in a array from specified position.
 *
 * Returns:
 *          An iterator that designates the first element remaining beyond any
 *          elements removed, or a pointer to the end of the array if no such
 *          element exists.
 *
 * Params:
 *          array = Array object.
 *          where = Position of the element to be removed from the array.
 *
 * Example:
 * ------------------------------------
 * // array_erase.d
 *
 * void main( )
 * {
 *    int[] v1;
 *    iterator!(int[]) Iter;
 *    
 *    v1.push_back( 10 );
 *    v1.push_back( 20 );
 *    v1.push_back( 30 );
 *    v1.push_back( 40 );
 *    v1.push_back( 50 );
 * 
 *    dout << "v1 =" ;
 *    for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
 *       dout << " " << *Iter;
 *    dout << endl;
 * 
 *    v1.erase( v1.begin( ) );
 *    dout << "v1 =";
 *    for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
 *       dout << " " << *Iter;
 *    dout << endl;
 * }
 * ------------------------------------
 *
 * Output:
 *         v1 = 10 20 30 40 50<br />
 *         v1 = 20 30 40 50
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *
 * See_Also:
 *         empty, erase, and push_back
 *****************************************************************************/
iterator!(T[]) erase(T)(inout T[] array, iterator!(T[]) where)
{
	where.check_array(array);
	for (int i=where.get_pos(); i<array.length-1; ++i)
		array[i] = array[i+1];
	array.length = array.length - 1;
	return iterator!(T[])(array, where.get_pos());
}

unittest
{
	printf("test array.erase\n\0");

	int[] array = [1,2,3];
	iterator!(int[]) begin = array.begin();
	// DMD does not support this:
	// array.erase(array, begin);
	erase!(int)(array, begin);

	assert(array == [2,3]);
}


// 以下部分必须注释掉,DMD不允许这种重载,应该是个BUG

/******************************************************************************
 * Removes a range of elements in a array from specified positions.
 *
 * Returns:
 *          An iterator that designates the first element remaining beyond any
 *          elements removed, or a pointer to the end of the array if no such
 *          element exists.
 *
 * Params:
 *          array = Array object.
 *          first = Position of the first element removed from the array.
 *          last  = Position just beyond the last element removed from the
 *                  array.
 *
 * Example:
 * ------------------------------------
 * // array_erase.d
 *
 * void main( )
 * {
 *    int[] v1;
 *    iterator!(int[]) Iter;
 *    
 *    v1.push_back( 10 );
 *    v1.push_back( 20 );
 *    v1.push_back( 30 );
 *    v1.push_back( 40 );
 *    v1.push_back( 50 );
 * 
 *    dout << "v1 =" ;
 *    for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
 *       dout << " " << *Iter;
 *    dout << endl;
 * 
 *    v1.erase( v1.begin( ) );
 *    dout << "v1 =";
 *    for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
 *       dout << " " << *Iter;
 *    dout << endl;
 *
 *    v1.erase( v1.begin( ) + 1, v1.begin( ) + 3 );
 *    cout << "v1 =";
 *    for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
 *       cout << " " << *Iter;
 *    cout << endl;
 * }
 * ------------------------------------
 *
 * Output:
 *         v1 = 10 20 30 40 50<br />
 *         v1 = 20 30 40 50<br />
 *         v1 = 20 50
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *
 * See_Also:
 *         empty, erase, and push_back
 *****************************************************************************/
/*
iterator!(T[]) erase(T)(inout T[] array, iterator!(T[]) first, iterator!(T[]) last)
{
	return null;
}
*/


/******************************************************************************
 * Returns a reference to the first element in an array.
 *
 * Returns:
 *         The first element in the array object. If the array is empty, the
 *         return is undefined.
 *
 * Params:
 *     array = Array object.
 *
 * Remarks:
 *         When compiling with _SECURE_SCL 1, a runtime error will occur if you
 *         attempt to access an element in an empty array. See Checked
 *         Iterators for more information.
 *
 * Example:
 * ------------------------------------
 * // array_front.d
 * 
 * void main( )
 * {
 *    int[] v1;
 *    
 *    v1.push_back( 10 );
 *    v1.push_back( 11 );
 * 
 *    int i = v1.front( );
 * 
 *    cout << "The first integer of v1 is "<< i << endl;
 * }
 * ------------------------------------
 * 
 * Output:
 *         The first integer of v1 is 10
 *  
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *
 * See_Also:
 *          front and back
 *****************************************************************************/
T front(T)(inout T[] array)
{
	version(_SECURE_SCL)
	{
		return array[0];
	}
	else
	{
		if (!array.empty())
			return array[0];
		T result;
		return result;
	}
}

unittest
{
	printf("test array.front\n\0");

	int[] array = [1,2,3];
	int f = array.front();
	assert(f == 1);
	assert(array == [1,2,3]);
}


/******************************************************************************
 * Inserts an element or a number of elements or a range of elements into the
 * array at a specified position.
 *
 * Returns:
 *         The first insert function returns an iterator that points to the 
 *         position where the new element was inserted into the array.
 *
 * Params:
 *         array = Array object.
 *         where = The position in the array where the first element is
 *                 inserted.
 *         value = The value of the element being inserted into the array.
 *
 * Remarks:
 *         Any insertion operation can be expensive, see vector Class for a
 *         discussion of array performance.
 *
 * Example:
 * ------------------------------------
 * // array_insert.cpp
 * 
 * int main( )
 * {
 *    int[] v1;
 *    iterator!(int[]) Iter;
 *    
 *    v1.push_back( 10 );
 *    v1.push_back( 20 );
 *    v1.push_back( 30 );
 * 
 *    dout << "v1 =" ;
 *    for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
 *       dout << " " << Iter.get();
 *    dout << endl;
 * 
 *    v1.insert( v1.begin( ) + 1, 40 );
 *    dout << "v1 =";
 *    for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
 *       dout << " " << Iter.get();
 *    dout << endl;
 *    v1.insert( v1.begin( ) + 2, 4, 50 );
 * 
 *    dout << "v1 =";
 *    for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
 *       dout << " " << Iter.get();
 *    dout << endl;
 * 
 *    v1.insert( v1.begin( )+1, v1.begin( )+2, v1.begin( )+4 );
 *    dout << "v1 =";
 *    for (Iter = v1.begin( ); Iter != v1.end( ); Iter++ )
 *       dout << " " << Iter.get();
 *    dout << endl;
 * }
 * ------------------------------------
 *
 * Output:
 *         v1 = 10 20 30<br />
 *         v1 = 10 40 20 30<br />
 *         v1 = 10 40 50 50 50 50 20 30<br />
 *         v1 = 10 50 50 40 50 50 50 50 20 30
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *****************************************************************************/
iterator!(T[]) insert(T)(inout T[] array, iterator!(T[]) where, T value)
{
	where.check_array(array);
	array.length = array.length + 1;
	for(int i=array.length-1; i>where.get_pos(); i--)
		array[i] = array[i-1];
	array[where.get_pos()] = value;
	return iterator!(T[])(array, where.get_pos());
}

unittest
{
	printf("test array.insert\n\0");

	int[] array = [1,2,3];
	auto begin = array.begin();
	insert!(int)(array, begin, 4);
	assert(array == [4,1,2,3]);
}



/******************************************************************************
 * Deletes the element at the end of the array.
 *
 * Params:
 *         array = Array object.
 *
 * Example:
 * ------------------------------------
 * // array_pop_back.cpp
 * 
 * int main( )
 * {
 *    int[] v1;
 *    
 *    v1.push_back( 1 );
 *    dout << v1.back( ) << endl;
 *    v1.push_back( 2 );
 *    dout << v1.back( ) << endl;
 *    v1.pop_back( );
 *    dout << v1.back( ) << endl;
 * }
 *  
 * Output:
 *         1<br/>
 *         2<br/>
 *         1
 *  
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 * See_Also:
 *         push_back and pop_back
 *****************************************************************************/
void pop_back(T)(inout T[] array)
{
	if (array.length)
		array.length = array.length - 1;
}

unittest
{
	printf("test array.pop_back\n\0");

	int[] array = [1,2,3];

	array.pop_back();
	assert(array.length == 2);
	assert(array == [1,2]);

	array.pop_back();
	assert(array.length == 1);
	assert(array == [1]);

	array.pop_back();
	assert(array.length == 0);

	array.pop_back();
	assert(array.length == 0);
}


/******************************************************************************
 * Adds an element to the end of the array.
 *
 * Params:
 *         array = Array object.
 *         value = The element added to the end of the array.
 * 
 * Example:
 * ------------------------------------
 * // array_push_back.cpp
 * 
 * void main( )
 * {
 *    int[] v1;
 *    
 *    v1.push_back( 1 );
 *    if ( v1.size( ) != 0 )
 *       dout << "Last element: " << v1.back( ) << endl;
 * 
 *    v1.push_back( 2 );
 *    if ( v1.size( ) != 0 )
 *       dout << "New last element: " << v1.back( ) << endl;
 * }
 * ------------------------------------
 *
 * Output: 
 *         Last element: 1<br/>
 *         New last element: 2
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *
 * See_Also:
 *         push_back and pop_back<br />
 *         accumulate, copy, and push_back<br />
 *         adjacent_difference and push_back<br />
 *         empty, erase, and push_back
 *****************************************************************************/
void push_back(T)(inout T[] array, T value)
{
	array ~= value;
}

unittest
{
	printf("test array.push_back\n\0");

	int[] array = [1,2,3];
	array.push_back(4);
	assert(array == [1,2,3,4]);

	array.push_back(5);
	assert(array == [1,2,3,4,5]);
}

/******************************************************************************
 * Specifies a new size for a array.
 *
 * Params:
 *         array = Array object.
 *         newsize = The new size of the array.
 *         value = The value of new elements added to the array if the new size
 *                 is larger that the original size. If the value is omitted,
 *                 the new objects are assigned the default value.
 *
 * Remarks:
 *         If the container's size is less than the requested size, _newsize,
 *         elements are added to the array until it reaches the requested size.
 *         If the container's size is larger than the requested size, the
 *         elements closest to the end of the container are deleted until the
 *         container reaches the size _newsize. If the present size of the
 *         container is the same as the requested size, no action is taken.
 *
 *         size reflects the current size of the array.
 *
 * Example:
 * ------------------------------------
 * // array_resize.d
 *
 * void main( )
 * { 
 *    int[] v1;
 *    
 *    v1.push_back( 10 );
 *    v1.push_back( 20 );
 *    v1.push_back( 30 );
 * 
 *    v1.resize( 4,40 );
 *    cout << "The size of v1 is " << v1.size( ) << endl;
 *    cout << "The value of the last object is " << v1.back( ) << endl;
 * 
 *    v1.resize( 5 );
 *    cout << "The size of v1 is now " << v1.size( ) << endl;
 *    cout << "The value of the last object is now " << v1.back( ) << endl;
 * }
 * ------------------------------------
 *
 * Output:
 *         The size of v1 is 4<br />
 *         The value of the last object is 40<br />
 *         The size of v1 is now 5<br />
 *         The value of the last object is now 0
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *****************************************************************************/
void resize(T)(inout T[] array, size_t newsize, T value = T.init)
{
	array.length = newsize;
}

unittest
{
	printf("test array.resize\n\0");

	int[] array = [1,2,3];

	array.resize(cast(uint)5);
	assert(array == [1,2,3,0,0]);

	array.resize(cast(uint)2);
	assert(array == [1,2]);
}




/******************************************************************************
 * Reserves a minimum length of storage for a array object, allocating space if
 * necessary.
 *
 * Params:
 *         array = Array object.
 *         count = The minimum length of storage to be allocated for the array.
 *
 * Example:
 * ------------------------------------
 * // array_reserve.cpp
 * 
 * void main( )
 * {
 *    int[] v1;
 * 
 *    v1.reserve( 20 );
 * }
 * ------------------------------------
 *
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *****************************************************************************/
void reverse(T)(inout T[] array, size_t count)
{
	size_t oldlen = array.length;
	array.length = count;
	array.length = oldlen;
}

unittest
{
	printf("test array.reverse can't test\n\0");
}


/******************************************************************************
 * Returns the number of elements in the array.
 *
 * Returns:
 *         The current length of the array.
 *
 * Params:
 *         array = Array object.
 *
 * Example:
 * ------------------------------------
 * // array_size.d
 * 
 * voud main( )
 * {
 *    int[] v1;
 *    size_t i;
 *    
 *    v1.push_back( 1 );
 *    i = v1.size( );
 *    dout << "Vector length is " << i << "." << endl;
 * 
 *    v1.push_back( 2 );
 *    i = v1.size( );
 *    dout << "Vector length is now " << i << "." << endl;
 * }
 * ------------------------------------
 * 
 * Output:
 *         Vector length is 1.<br />
 *         Vector length is now 2.
 *  
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *
 * See_Also:
 *         size and capacity
 *****************************************************************************/
size_t size(T)(inout T[] array)
{
	return array.length;
}

unittest
{
	printf("test array.size\n\0");

	int[] array = [1,2,3];
	assert(array.size() == 3);

	int[] array1 = [1,2];
	assert(array1.size() == 2);
}


/******************************************************************************
 * Exchanges the elements of two arrays.
 *
 * Params:
 *         array = Array object.
 *         right = A array providing the elements to be swapped, or a array
 *                 whose elements are to be exchanged with those of the array
 *                 _left.
 *         left  = A array whose elements are to be exchanged with those of the
 *                 array _right.
 *
 * Example:
 * ------------------------------------
 * // array_swap.d
 * void main( )
 * {
 *    int[] v1, v2;
 * 
 *    v1.push_back( 1 );
 *    v1.push_back( 2 );
 *    v1.push_back( 3 );
 * 
 *    v2.push_back( 10 );
 *    v2.push_back( 20 );
 * 
 *    dout << "The number of elements in v1 = " << v1.size( ) << endl;
 *    dout << "The number of elements in v2 = " << v2.size( ) << endl;
 *    dout << endl;
 * 
 *    v1.swap( v2 );
 * 
 *    dout << "The number of elements in v1 = " << v1.size( ) << endl;
 *    dout << "The number of elements in v2 = " << v2.size( ) << endl;
 * }
 * ------------------------------------
 *
 * Output:
 *         The number of elements in v1 = 3<br />
 *         The number of elements in v2 = 2<br />
 *
 *         The number of elements in v1 = 2<br />
 *         The number of elements in v2 = 3<br />
 *  
 * Requirements:
 * ------------------------------------
 * import array;
 * ------------------------------------
 *****************************************************************************/
void swap(T)(inout T[] left, inout T[] right)
{
	T[] temp = left;
	left = right;
	right = temp;
}

unittest
{
	printf("test array.swap\n\0");

	int[] array1 = [1,2,3,4];
	int[] array2 = [4,3,2,1];
	array1.swap(array2);

	assert(array1 == [4,3,2,1]);
	assert(array2 == [1,2,3,4]);
}

import std.stdio;
void main()
{
	int[] a = [1,2,3];
	assert(a.at(0) == 1);
	auto i = a.begin();
	auto b = a.end();


	while(i != a.end())
	{
		printf("%d\n\0", i());
		i ++;
	}

	auto iter = a.begin();
	writefln(iter());
	iter = 5;
	writefln(a);
}

分享到:
评论
70 楼 oldrev 2007-04-09  
昨天突然发现,由于D采用GC,链表的写法和C++不一样,两个链表完全可以共享节点,看来前面的努力白费了......
69 楼 h_rain 2007-04-08  
呵呵,做程序的啊~
68 楼 qiezi 2007-04-08  
我前2周也很忙,回来最早也是10点,有2次是2点才回来,还有一次回来以后通宵。。好在还是单身啊
67 楼 h_rain 2007-04-08  
nsISupports的IID和COM里面的IUnknown的IID竟然是一样的


我晕~

这敌意也太明显了~
66 楼 h_rain 2007-04-08  
说句实话,每天就晚上9:30之后才能有时间学点东西,白天工作上也忙的要命,总得完善产品,开发新项目,晚上7:00~9:30还要陪我2岁的女儿玩,哄她睡觉,天天都累的不得了.
唉~

时间不够用啊...



65 楼 qiezi 2007-04-08  
XPCOM基本原理和COM是一样的,少了多继承,接口感觉要舒服一些,其它方面相差不大。

nsISupports的IID和COM里面的IUnknown的IID竟然是一样的,前面一堆0,后面是0x46。。。不知道是不是曾经打算和COM合在一起
64 楼 qiezi 2007-04-08  
模板版本和普通版本在一起是有些问题,2个模板版本参数个数不同似乎也不行。。。
63 楼 h_rain 2007-04-08  
oldrev     1 分钟 
没注意,楼上的楼上的楼上是强人啊,高中就玩烂了链表,要不您给写一个?

呵呵,又没说你的链表不好,叫什么号啊:)
小孩子脾气,没劲的~
你写到好,很好,行了吧!

我在92年初二就开始编程了,高中开始玩asm/c,大学开始玩c++,链表是数据结构的基础,当然玩烂了,有什么奇怪的?
现在我工作中也一直没有使用STL,用的就是我自己写的模板库,缺什么加什么,毕竟所有的代码都在掌握中,用着舒服.

刚才还想说呢,到现在我连D的文档都没时间看全呢,就是在这看看大家的文章,倒真是该开始读一下文档了呢.
62 楼 h_rain 2007-04-08  
呵呵,支持qiezi!
"Value"也不错.
确实,如果想弄一个像样的迭代器,需要考虑规划的东西很多,肯定不是几天就可以完成的,单说线程安全,就有很多需要顾虑的了.

开始移植XPCOM了,你的动作还真快,佩服!
那东西前两天看了一下,头痛:)
61 楼 oldrev 2007-04-08  
没注意,楼上的楼上的楼上是强人啊,高中就玩烂了链表,要不您给写一个?
60 楼 oldrev 2007-04-08  
那就定成 value 吧,STL我还是搞不定,里面的 set/map/sort 实现实在是太复杂了
好像D中同一名字的函数的模板版本和普通版本在一起有问题?

void foo(T)(T t)
{
}

void foo()
{
}
59 楼 qiezi 2007-04-07  
C++里面迭代器的思想源于指针,通常是:
char arr[10];
char* begin = arr;
char* end = begin + (sizeof(arr) / sizeof(arr[0]));
char* iter = begin;
while(iter != end)
{
    *iter = 'c';
    iter ++;
}

所以迭代器就模拟了这一语法,刚好C++也支持了。D既然不支持,就另想办法,这个提领语法也没有漂亮到哪去,反面让D语言学习者看得莫名其妙。

这里的约定无非就是*iter,我提议使用value来作约定,清晰明了又不隐晦。不管放入的是什么东西,对于容器来说,它都是“值”。

template vector(T)
{
    alias T[] vector;
}
vector!(int) array = [1,2,3];
auto iter = array.begin();
while(iter != array.end())
{
    writefln(iter.value);
    iter.value = iter.value * 3;
}

暂是没加上去,继续讨论。。不过这里的迭代器比较简陋,STL的实现也差不多忘光啦,BOOST的还没开始看,所以这个实际上是写着玩的,并没有打算把它形成一个库。

我目前正在做XPCOM移植到D的工作,一些必需的文件已经转换完成,其它的IDL文件我打算修改idl编译器来做,不然工作量太大了。上次修改了一个,不小心删了,不过工作量并不大。编写的测试目前运行有些问题,和上次BerkeleyDB有点像,打算过几天在Linux上试试,Windows上我用D遇到很多问题,解决起来经常摸不着方向,还是先把它在linux上跑起来再说。
58 楼 h_rain 2007-04-07  
oldrev     21 小时前 
双向链表的迭代迭代器是双向迭代器,不支持大小比较,而且也不支持 += 2。 
链表中的节点在堆中的位置完全是随机的,后加入的节点的地址不一定比老节点大。 
STL 是数据结构和算法实现的典范,值得好好学习。


呵呵,关于迭代器,在C++ STL中,无非是想提供一个对不同数据结构的进行操作的统一访问模型,以便对不同的数据结构的算法操作可以有一个统一的接口。在D中也一样,就是对数据结构进行操作而预定的统一模型。
C++ STL中没有支持的操作,不代表是没有用的操作,别把那东西看的太神了。
对于数组来说,访问这个数据结构中的元素所代表的“数据”,仅仅需要一个索引(对C数组,这个索引简单到只能是整数类型),或指向元素的指针。
对于链表来说,访问这个数据结构中的元素所代表的“数据”,则需要这个元素的一个对应的“存根(节点指针)”,要不这个存根事先保留,要不就从头或尾遍历得到。
其他的数据结构也需要对元素进行定位,也需要这么一个对应的存根来访问元素所代表的数据。
迭代器的作用就应该是对那个“存根”进行了统一的抽象,从而在上层的算法操作上,可以使用一个相对统一的接口。
因为迭代器代表了对元素数据的访问,所以通过迭代器得到数据就是必须的了。但C++中使用*提领操作符得到数据那是C++中的定义(想让迭代器的表现像指针),D中完全没有必要一定这么实现,因为迭代器并不是意味着指针或类似于指针,这么想是错误的。

将链表,树,图等等的数据结构进行排序后,对迭代器进行+=,-=之类的操作是很有意义的。


C/C++操作的双向链表我在高中的时候就玩烂了,哈。

STL 是数据结构和算法实现的典范,值得好好学习。

不要死扣代码的实现,学学实现背后的思想吧。


因为D中是不鼓励指针的使用的,所以我也不赞成弄成*Iter的形式。
根据我上面的看法,迭代器的作用之一就是对元素数据的间接引用,那么得到数据完全可以使用成员函数或属性,比如Set/Get,SetData/GetData,或Data,用什么名字完全是一种约定。
57 楼 qiezi 2007-04-07  
所有使用opAssign的都会这样“暖昧”,毕竟它把可以隐式转形的一类类型区别对待了。
56 楼 oldrev 2007-04-07  
这个赋值的感觉太暧昧了,算了,*ptr 本来就是为指针准备的,D 不提倡指针,我还是决定实现成属性吧,或者资讯一下 Walter?
55 楼 qiezi 2007-04-07  
上面这个没问题亚,x+1返回的是迭代器类型,我写了个代码测试也没有问题:
int[] arr = [1,2,3];
auto a, b;
a = arr.begin();
b = a + 1;
writefln(b());

输出:
2
54 楼 oldrev 2007-04-07  
等我仔细想想能不能用 mixin、.stringof 等等这些办法实现提领
53 楼 oldrev 2007-04-07  
赋值那个很有问题,比如你的迭代器是随机访问迭代器,重载了 opAdd(int rhs), opSub(int rsh),那么:
iterator!(int) x, y;
[b]y = x + 1; [/b]// ?????
52 楼 qiezi 2007-04-07  
是有些麻烦,取值调用opCall应该还是可以接受的,赋值也还勉强可以接受,毕竟迭代器并不是到处都在用,你也不会写一个类从它上面派生。要不也用opCall?感觉不好看啊:
int[] arr = [1,2,3];
auto iter = arr.begin();
int i = iter();
iter(3); // 赋值,等价于*iter = 3

D就算支持提领,如果没有引用类型也还是没办法实现C++这个语法的。

除非像ruby的&:symbol一样,ruby里面的语意是调用Symbol#to_proc并把proc对象用&作为块传给方法,同一个&有2种功能。

D也可以这样,让“*”发挥2个作用:
struct xxx_iterator(T)
{
    T* opPreStar(){...}
}

auto iter = ...
*iter = 3;

由于*调用opPreStar,返回T*类型,同时发挥第2个作用,合成的调用结果是:*(iter.opPreStar()) = 3;
51 楼 oldrev 2007-04-07  
因此我提议约定迭代器必须有一个读写值的属性,比如 current:

void current(T t); // set
T current(); // get

MyList.Iterator i;
it.current = 1;
int n = it.current;

相关推荐

    C++ STL vector 容器介绍

    C++ STL(Standard Template Library,标准模板库)是C++编程语言中不可或缺的一部分,它提供了一组高效且灵活的算法、容器和迭代器。在STL中,`vector`是一种非常重要的容器,它是一个动态数组,允许在任意位置进行...

    STL容器之array和vector.zip

    2. 成员函数:`std::array`提供了一系列的成员函数,如`size()`用于获取大小,`data()`返回原始数组的指针,以及重载的`[]`操作符用于访问元素。 3. 类型安全:由于`std::array`的大小是模板参数的一部分,所以在...

    走进stl (using stl)

    在这个例子中,`std::vector`作为STL的容器,替代了原始数组,`push_back`方法用于添加元素,而范围for循环则简化了求平均值的过程,无需手动管理索引。 总的来说,尽管STL的语法可能对初学者来说较为复杂,但它的...

    stl 小例子

    STL,全称为Standard Template Library(标准模板库),是C++编程语言中的一部分,它提供了一组高效、灵活且可重用的容器、迭代器、算法和函数对象(仿函数)。STL的主要目标是提高代码的简洁性、可读性和性能。在...

    [中英文]STL参考手册

    例如,`vector`的插入和删除操作在大多数情况下比原始数组更快,因为它会自动处理内存管理和元素移动。 STL的文档详细介绍了每个组件的使用方法、接口以及注意事项,是学习和使用STL的重要参考资料。对于开发者来说...

    源码 STL1.0库

    STL的算法库包含了一组通用的函数模板,用于执行各种常见操作,如排序(`std::sort`)、查找(`std::find`)、复制(`std::copy`)、合并(`std::merge`)等。这些算法可以作用于任何容器,通过迭代器来访问元素,...

    数组(一维、二维、三维)的动态申请及用vector的表示方法

    ### 数组(一维、二维、三维)的动态申请及用vector的表示方法 #### 一、变长一维数组 变长数组是指在编译时不能确定数组长度,而是在程序运行时需要动态分配内存空间的数组。下面详细介绍如何在C++中实现变长一维...

    STL-基础数据类型的基本用法

    STL,全称为Standard Template Library(标准模板库),是C++编程语言中的一部分,它提供了一组高效且灵活的数据结构和算法。STL的核心概念包括容器、迭代器、算法和函数对象,这些组件共同构成了一个强大的工具箱,...

    C++ STL库知识总结

    C++ STL库是C++标准库的一个重要组成部分,它提供了丰富的数据结构和算法,极大地提升了C++编程的效率和灵活性。以下是对C++ STL库知识的详细总结。 首先,STL(Standard Template Library,标准模板库)包含了六大...

    C++程序设计教学课件:Ch5 Array, String and Vector.pdf

    向量(Vector)是C++标准模板库(STL)中的一个动态数组容器。向量提供了比传统数组更高级的功能,如动态内存管理、大小的自动调整、成员访问和迭代器支持。声明向量时,需要包含头文件 `&lt;vector&gt;` 并指定存储的数据...

    数据结构C++描述(STL)

    常见的容器有数组(`std::array`)、向量(`std::vector`)、列表(`std::list`)、链表(`std::forward_list`、`std::list`)、集合(`std::set`、`std::unordered_set`)、映射(`std::map`、`std::unordered_map`...

    STL、贪心.zip_acm 算法

    1. 容器:STL提供了多种类型的容器,如数组(array)、向量(vector)、列表(list)、链表(forward_list)、双链表(list)、集合(set)、映射(map)、无序集合(unordered_set)和无序映射(unordered_map)。...

    cffect stl eg(原版)pdf

    - “swap技巧”是一种有效减少`std::vector`或`std::string`多余容量的方法。 - 这有助于提高程序的整体性能。 **描述:** - 通过交换两个容器的内部数据,可以有效地将一个容器的容量减小到其实际大小。 - 示例...

    VC.add.programming.array.list.rar_vc list

    它提供了一组方法来操作这些元素,包括添加、删除、访问和修改。例如,我们可以使用`push_back()`方法向数组列表末尾添加元素,使用`pop_back()`方法移除最后一个元素,使用`size()`获取元素数量,以及通过索引访问...

    C++程序设计教学课件:CHAPTER 11 THE STANDARD TEMPLATE LIBRARY.ppt

    3. **算法**:STL提供了一组广泛的算法,这些算法不依赖于特定的容器实现,可以对容器中的元素进行操作,如排序(sort)、查找(find)、拷贝(copy)、删除(remove)等。这些算法大大简化了复杂操作的编写,提高了...

    STL

    STL,全称为Standard Template Library(标准模板库),是C++编程语言中不可或缺的一部分,它为程序员提供了高效且可重用的数据结构和算法。STL的核心理念是泛型编程,这意味着它能处理不同类型的对象,提高了代码的...

    Algorithm-tstl.zip

    1. **容器**:容器是一组对象的集合,提供了对这些对象的管理方式。例如,`Array`(数组)、`Vector`(动态数组)、`List`(双链表)、`Set`(集合)和`Map`(映射)等。这些容器提供了丰富的操作接口,如插入、删除...

    test_stl

    它提供了一组高效、可重用的容器、迭代器、算法和函数对象,极大地提高了C++程序员的开发效率。JavaScript,另一方面,是Web前端开发的主导语言,通常与HTML和CSS一起用于构建交互式的网页应用。尽管JavaScript自身...

    c + + 试 题 及 答 案

    题目给出了一组字符串的定义和比较操作: ```cpp char str1[] = "abc"; char str2[] = "abc"; const char str3[] = "abc"; const char str4[] = "abc"; const char *str5 = "abc"; const char *str6 = "abc"; cout ...

    几本语言类的数据

    而“STL编程指南”则专注于C++编程,STL是C++的一个重要组成部分,提供了一组高效的数据结构(如vector、list、set)和算法(如排序、查找),极大地提高了代码的可读性和效率。 在编程领域,掌握算法和数据结构是...

Global site tag (gtag.js) - Google Analytics