System.Collections.ArrayList is a dynamic array that is similar to the C STL's std :: Vector behavior, especially in the dynamic expansion mode of the array, both of which are basically the same. Different is that ArrayList uses an interface to implement an enumerator, while std :: Vector uses templates typedef techniques. The following will be mainly analyzed in these two points. Some places may mention STL corresponding practices to compare comparisons. This article analyzes the code from http://www.123aspx.com/rotor/rotorsrc.aspx?rot=39810, which is a Microsoft's public code, completely legal. Of course, this part of the code and Microsoft actually released .NET Framework may be small, if you don't worry, you can download the Reflector anti-compilation .NET FRANEWORK. According to my own observation, ArrayList is exactly the same in these two versions. 1. Member Variable: // Fields Private Object [] _Items; private int _size; private int _version; private const INT _DEFAULTCAPATIN = 16; _size represents the number of data items in the current array, pay attention, not the data item that the container can accommodate Number, the container actually has a buffer method, please refer to the analysis below. _Items is a collection of containers, where there is a buffer design. Each time you insert a data item, you will check the current _items's capacity Length. If you are discovered, if you are bigger than _Size, you will explain that there are some free space in the current _items, then insert the data item directly into the array. If the length of _items is found to be the same as _Size, it will not be idle space in _Items. To insert data items in an array, you must first expand the space of data _items. The algorithm of the expansion _items space is divided into 3 steps. First, allocate a larger space _items_new, usually the size of Length * 2. Then, copy all the data in _items to _items_new. Finally, use the _items_new to replace the _items.arrayList's memory expansion algorithm is EnSureCapacity, which actually calls the set method of the Length attribute of Capacity, and truly implement the extended function in the SET method. . Look at the next variable, _Version is a relatively special variable, used to represent the number of times the current array has been modified. Each time you call the INSERT, REMOVE, the value of the array, which will cause the value of the variable to increase. So why do you design this? In fact, it is entirely serving iterator IEnumerator. Consider the following scenarios, in the server of a chat software, the chat room use class class talkroom, and each user is represented by class User. The Class user {// server sends a message to the user. Public void sendmsg (String MSG) {...}}
Class Talkroom {// member private arraylist _people in the current chat room; / / broadcast messages to all user broadcasts to the chat room. Public void Broadcast (String MSG) {User = NULL; IEENUMERATOR IT = _PEOPLES.GETENUMERATOR (); while (it.movenext ()) {user = (user) ip; it.sendmsg (msg);}}} The short code describes the process of all user broadcast messages to the chat room, it seems reasonable, but is it true? Suppose it is in the TalkRoom :: Broadcast function, it.movenext (), the user = (user) before IT, the other thread is just because of some reasons, from _people, deleted the User object pointing to the IT (such as the user Line), what will happen? More serious case is that if the deleted user is exactly the last object of the array, then IT will turn into a NULL pointer, and the consequences of implementing the mandatory type conversion for NULL, do not need to explain more. In fact, STL's enumerator has the same problem, so in some reference manuals in STL, Push_Back, Pop_Front can cause the container's iterator to fail, this is the case. In this case, Microsoft's solution is to use a _Version variable, each change the container data, which is incremented. At the same time, the current container _Version passes the current container _Version to the iterator. Each time the iterator's MoveNext () function is executed, check whether the _version and iterator's _Versin is equal, once it is discovered, the container is found. Already changed, the iterator has been invalid and immediately throws an exception. Specific reference to the code: class ArrayListEnumerator {... public virtual bool MoveNext () {if (this.version = this.list._version!) {Throw new InvalidOperationException (Environment.GetResourceString ( "InvalidOperation_EnumFailedVersion"));} ... }
The last variable is _defaultcapacity, when used to specify the array size of the default, the default is 16.
2. Constructor: public arraylist () {_items = new object [_defaultcapacity]; // Reference_DefaultCapacity analysis, you can find it. }
Public ArrayList (int Capacity) {// If the initial allocation is set, use Capacity to replace _defaultcapacity. if (capacity <0) throw new ArgumentOutOfRangeException ( "capacity", Environment.GetResourceString ( "ArgumentOutOfRange_SmallCapacity")); _items = new Object [capacity];} and two constructors, but is not particularly worthy of analysis.
3. Add and delete functions:
// Add value to an array {if (_size == _items.length) Ensurecapacity (_size 1); // If necessary, expand capacity _items [_size] = value; _Version ; // version number change return_size ;}
/ / Delete an element, position it, then call Removeat. Public Virtual Void Remove (Object Obj) {int index = indexof (obj); bcldebug.corractness (index> = 0 ||! (Obj is int32), "You passed an int32 to remove what wasn't in the arraylist./ R / NDID you mean removeat? int: " Obj " count: " count); if (index> = 0) Removeat (index);
// Really delete the function of the element. public virtual void RemoveAt (int index) {if (index <0 || index> = _size) throw new ArgumentOutOfRangeException ( "index", Environment.GetResourceString ( "ArgumentOutOfRange_Index")); _size--; if (index <_size) { Array.copy (_items, index 1, _items, index, _size - index);} _items [_size] = null; _Version ; // version number change}
4. Attribute of Capacity: The Capacity property determines that the memory allocation of this entire container is very simple, mainly analyzing the SET function. Public Virtual Int Capacity {Get // Get, returns an array size. {Return this._items.length;} // set method The main process has 3 steps // 1. Compare the array size and the current array size, if equally, then exit directly. // 2. The number of data required and the number of data in the current array is required. If it is to truncate the array, the exception is thrown. // 3. Extension array, first assign a larger array, then copy the origin group to the new array, replace the original array with the new array, and is exactly the same as the above analysis. Set {if (value! = This._items.length) {if (value * / Else {this._Items = new object [0x10];}}}} The analysis of ArrayList is here, in fact, the actual interest is three points, first, dynamic memory allocation algorithm, this is actually referred to Mr. Jie's book << STL Source Analysis >> About Std :: Vector Growth Array Analysis Chapter, Graphic Combination, I don't think it is easy. Second, use the _Version variable to ensure that the iterator is valid. Finally, I found code that never executed. In addition, Microsoft's .NET Framework is a source treasure, all kinds of implementation code throughout the aspects, I have been studying, I will continue to write some experience and experience in some analysis, my level is limited, if there is any mistake, welcome to correct, Also welcomes contempt.
