C# List<T>的使用
List是在日常开发中使用异常频繁的一个集合类。List是一个线性的容器，也就是存在List中的数据必须是连续的，一个挨着一个。那么就会有一些疑问，为什么List是线性的呢？创建的时候应该要一个多大的容器呢？太大了肯定是浪费空间，太小了装不下怎么办？集合中的单个元素又占有多大的内存空间呢？
①这个容器到底该设置为多大呢？
看一个例子。假设我们需要一个宠物容器。
-
class
Program {
-
-
private
static List<Pet> pets;
-
-
internal
class
Pet
-
{
-
-
}
-
-
static void Main(string[] args)
-
{
-
pets =
new List<Pet>();
-
Console.WriteLine(
"Count : " + pets.Count);
-
Console.WriteLine(
"Capacity : " + pets.Capacity);
-
while (
true) ;
-
}
-
-
}
-
-
}
因为还没有添加数据，所以此时的容量和树木都是0.现在我们向其中添加一个元素
-
static void Main(string[] args)
-
{
-
pets =
new List<Pet>(
0);
-
Console.WriteLine(
"Count : " + pets.Count);
-
Console.WriteLine(
"Capacity : " + pets.Capacity);
-
-
Console.WriteLine(
"添加一个元素后：");
-
Pet pet =
new Pet();
-
pets.Add(pet);
-
Console.WriteLine(
"Count : " + pets.Count);
-
Console.WriteLine(
"Capacity : " + pets.Capacity);
-
-
-
while (
true) ;
-
}
这里就说明List容器的容量只有在对其进行操作之后才会被设置，而且有个默认值的规则。实际上List提供了设置容器容量的构造方法，就是你可以设置这个容器的初始大小。之所以设置默认值为4，实在长期的实践过程中统计出设置这个默认值会得到最优解。
②再来看看第二个问题，每个单位元素所占的内存空间是多大？
-
internal
class
Pet
-
{
-
-
}
-
-
static void Main(string[] args)
-
{
-
pets =
new List<Pet>(
0);
-
Console.WriteLine(
"Count : " + pets.Count);
-
Console.WriteLine(
"Capacity : " + pets.Capacity);
-
-
for (
int i =
0; i <
4; i++)
-
{
-
Pet pet =
new Pet();
-
pets.Add(pet);
-
}
-
-
pets.ForEach(PrintAddress);
-
while (
true) ;
-
}
-
-
/// <summary>
-
/// 打印对象在内存中的位置
-
/// </summary>
-
/// <param name="obj"></param>
-
private static void PrintAddress(object obj)
-
{
-
GCHandle hander = GCHandle.Alloc(obj);
-
var pin = GCHandle.ToIntPtr(hander);
-
Console.WriteLine(pin);
-
}
添加了一个打印内存的方法，并且多添加了几个数据，以便通过元素地址的差值来看出每个元素在内存中所占的内存大小（这里注意Pet是一个空的类型，什么数据都没有）。打印结果如下：
可以看出，每个元素所占的内存大小为8个字节。因为是容器，我们容易臆想我们的数据在容器中是一个叠一个的，就想可比克那样，那么现在单位元素（一片薯片）是因为pet类是空的原因吗，
那我们在Pet上添加一些数据。修改代码如下
-
internal
class
Pet
-
{
-
public
string id;
-
public
string name;
-
public Type type;
-
public
int age;
-
}
然后我们再次执行修改后的代码，发现每个单位元素的所占的地址空间还是8个字节。所以List中的数据并不是和可比克那样叠加保存的。实际上是每个八位字节只保存了每个单位元素在堆内存中的地址，因为通过new出来的对象都是保存在堆内存中的，因为你无法保证每个单位元素实际需要多少内存空间。而在堆内存里的每个对象就像在池塘里的小鱼一样，但是有一根线连着这一条条小鱼，线的另一端就是List中对应的地址。
③现在的容量是4，如果装满了之后我们再向其中添加元素怎么办？
-
static void Main(string[] args)
-
{
-
pets =
new List<Pet>(
0);
-
Console.WriteLine(
"Count : " + pets.Count);
-
Console.WriteLine(
"Capacity : " + pets.Capacity);
-
Console.WriteLine(
"添加四个元素 ");
-
for (
int i =
0; i <
4; i++)
-
{
-
Pet pet =
new Pet();
-
pet.age = i;
-
pets.Add(pet);
-
}
-
Console.WriteLine(
"Count : " + pets.Count);
-
Console.WriteLine(
"Capacity : " + pets.Capacity);
-
pets.ForEach(PrintAddress);
-
Console.WriteLine(
"再添加四个元素 ");
-
for (
int i =
0; i <
4; i++)
-
{
-
Pet pet =
new Pet();
-
pet.age = i +
4;
-
pets.Add(pet);
-
}
-
Console.WriteLine(
"Count : " + pets.Count);
-
Console.WriteLine(
"Capacity : " + pets.Capacity);
-
pets.ForEach(PrintAddress);
-
-
while (
true) ;
-
}
我们发现再向其中添加元素的时候，容量被自动拓展了。这是因为在向List中Add元素的时候会先检测是否满了，如果满了就会根据拓展规则来拓展。
List自动拓展规则：当前容量X2（当然<Int最大值），但是我们能够看到在长度由4变为8的时候，整个List的地址其实是发生了变化的，将List之前的数据全部复制到一个容量更大的新的容器中，当然我们的pets的地址会更改为新的地址。
这里就有一个小的细节值得注意，频繁扩容一定是消耗性能的，毕竟要将数据完全复制到新的内存中，所以如果能够粗略估计数据的规模，在初始化的时候可以给出一个合理的初始容量，以避免频繁扩容。以下是List的扩容的源码，能够看到其规则。
-
// Adds the given object to the end of this list. The size of the list is
-
// increased by one. If required, the capacity of the list is doubled
-
// before adding the new element.
-
//
-
public void Add(T item) {
-
if (_size == _items.Length) EnsureCapacity(_size +
1);
-
_items[_size++] = item;
-
_version++;
-
}
-
-
-
-
// Ensures that the capacity of this list is at least the given minimum
-
// value. If the currect capacity of the list is less than min, the
-
// capacity is increased to twice the current capacity or to min,
-
// whichever is larger.
-
private void EnsureCapacity(int min) {
-
if (_items.Length < min) {
-
int newCapacity = _items.Length ==
0? _defaultCapacity : _items.Length *
2;
-
// Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
-
// Note that this check works even when _items.Length overflowed thanks to the (uint) cast
-
if ((
uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
-
if (newCapacity < min) newCapacity = min;
-
Capacity = newCapacity;
-
}
-
}
List源码里还有一些值得学习的小技巧：
比如我们想删除掉pets表中age为偶数的元素，我们可能会这样去写。
-
private static void RemovePets() {
-
for (
int i =
0; i <pets.Count; i++)
-
{
-
if (pets[i].age %
2 ==
0) {
-
pets.RemoveAt(i);
-
Console.WriteLine(
"------------------------ " + i);
-
pets.ForEach(PrintAddress);
-
}
-
}
-
}
从打印的结果可以看出，再没删除一次，pets中的所有数据的地址都发生了改变，也就是说每次删除一个元素都对所有的元素进行了一次集体搬家，这样不需要删除的元素愣生生搬家了四次。这显然是不合理的，合理的办法应该是先找出所有的需要删除的元素，
再对剩余的元素搬家一次。List提供了RemoveAll方法，就是干这事的。所以代码可以修改为
-
private static void RemovePets() {
-
pets.RemoveAll((pet)=> {
return pet.age %
2 ==
0; });
-
}
多次搬家显然是耗时的，我们这里测试一下两种方法耗时的时间上到底有多大的差别：
-
private
static List<Pet> pets;
-
public void Use() {
-
pets =
new List<Pet>(
0);
-
for (
int i =
0; i <
100000; i++)
-
{
-
Pet pet =
new Pet();
-
pet.age = i;
-
pets.Add(pet);
-
}
-
Console.WriteLine(
"pets.count : " + pets.Count);
-
DateTime beforeDT = System.DateTime.Now;
-
//耗时代码//
-
RemovePets1();
-
DateTime afterDT = System.DateTime.Now;
-
TimeSpan ts = afterDT.Subtract(beforeDT);
-
Console.WriteLine(
"need : " + ts.TotalMilliseconds);
-
Console.WriteLine(
"pets.count : " + pets.Count);
-
}
-
-
private void RemovePets2()
-
{
-
for (
int i = pets.Count -
1; i >
0; i--)
-
{
-
if (pets[i].age %
2 ==
0)
-
{
-
pets.RemoveAt(i);
-
}
-
}
-
}
-
-
private void RemovePets1() {
-
for (
int i =
0; i < pets.Count; i++)
-
{
-
if (pets[i].age %
2 ==
0) {
-
pets.RemoveAt(i);
-
}
-
}
-
}
-
-
private static void RemovePets()
-
{
-
pets.RemoveAll((pet) => {
return pet.age %
2 ==
0; });
-
}
为了看出差别，我们将数据量扩展为100000，使用RemovePets1删除偶数的耗时如下图：多次测试都在750ms左右，也可以用RemovePets2测试一下，大概在360ms左右
我们将上述代码中的RemovePets1改用RemovePets() ，结果如下：多次测试都在3ms左右。相差甚远。
当然更重要的是去学会人家怎么实现的，那就去看看源码，这个过程就慢慢嚼吧，是一个耐人寻味的过程，说难吧，也不难，但是真的是很细致。
-
// This method removes all items which matches the predicate.
-
// The complexity is O(n).
-
public int RemoveAll(Predicate<T> match) {
-
if( match ==
null) {
-
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
-
}
-
Contract.Ensures(Contract.Result<
int>() >=
0);
-
Contract.Ensures(Contract.Result<
int>() <= Contract.OldValue(Count));
-
Contract.EndContractBlock();
-
-
int freeIndex =
0;
// the first free slot in items array
-
-
// Find the first item which needs to be removed.
-
while( freeIndex < _size && !match(_items[freeIndex])) freeIndex++;
-
if( freeIndex >= _size)
return
0;
-
-
int current = freeIndex +
1;
-
while( current < _size) {
-
// Find the first item which needs to be kept.
-
while( current < _size && match(_items[current])) current++;
-
-
if( current < _size) {
-
// copy item to the free slot.
-
_items[freeIndex++] = _items[current++];
-
}
-
}
-
-
Array.Clear(_items, freeIndex, _size - freeIndex);
-
int result = _size - freeIndex;
-
_size = freeIndex;
-
_version++;
-
return result;
-
}
源码：https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,49c519bce0cdbd82
转载：https://blog.csdn.net/Struugle_Guy/article/details/116200936