如何遍历SparseArray？

Question

有没有一种方法可以遍历Java SparseArray (用于Android)？我使用 sparsearray 来轻松地按索引获取值。但是我找不到一种遍历的方法。

- Ruzanna

---

哇，说到一个完全不受喜爱的类，它不符合任何集合接口…… - user166390

选择的地图实现性能成为应用程序瓶颈的可能性非常非常小。 - Jeffrey Blattman

@JeffreyBlattman并不意味着当明显适合时我们应该避免使用正确的结构。 - frostymarvelous

@frostymarvelous 的评论“我只是想避免使用 TreeMap 或 HashMap，因为它们太重了”没有依据。这就是我的观点。 - Jeffrey Blattman

@frostymarvelous说它的速度是原来的两倍，这很可能意味着节省不到10毫秒。在整个应用程序的大局上，10毫秒重要吗？值得使用更难理解和维护的次优接口吗？我不知道这些问题的答案，但答案不是“无论如何都要使用稀疏数组”。 - Jeffrey Blattman

Answer 1

看起来我找到了解决方案。我没有正确注意到keyAt(index)函数。

所以我会采用这样的方法：

for(int i = 0; i < sparseArray.size(); i++) {
   int key = sparseArray.keyAt(i);
   // get the object by the key.
   Object obj = sparseArray.get(key);
}

- Ruzanna

---

文档说明了"keyAt(int index)给定范围在0...size()-1的索引，返回SparseArray中第index个键值对的键。"所以对于你描述的情况，它对我来说运作良好。 - Ruzanna

最好预先计算数组的大小并在循环中使用常量值。 - Dmitry Zaytsev

在这里直接使用valueAt函数会不会更容易？ - Milan Krstic

在循环内部这也可以起作用：Object obj = sparseArray.valueAt(i);。请注意，不要改变原文的意思并且不需要提供额外的解释。 - Florian

valueAt(i)比get(key)更快，因为valueAt(i)和keyAt(i)都是**O(1)，而get(key)是O(log2 n)**，所以我肯定会一直使用valueAt。 注：O(1)表示时间复杂度为常数级别，O(log2 n)表示时间复杂度与数据规模n的对数成正比。 - Mecki

Answer 2

如果你不关心键，那么在迭代稀疏数组时可以使用valueAt(int)直接访问值。

for(int i = 0, nsize = sparseArray.size(); i < nsize; i++) {
    Object obj = sparseArray.valueAt(i);
}

- Pogo Lin

---

如果你的迭代过程不关心键，即：循环计算特定值的出现次数，那么使用 valueAt() 是有用的（而且比被接受的解决方法更快）。 - Sogger

将sparseArray.size()存储在一个变量中，这样就不会每次调用size()。 - Pratik Butani

将size()方法赋值给一个变量是多余的。只需查看size()方法的代码即可轻松检查。我不明白为什么在建议这样的事情之前你没有这样做...我记得20年前我们有简单的链表，每次询问它们的大小时都必须计算它们的大小，但我不相信现在还存在这样的东西... - The incredible Jan

这是否保证按键顺序排列？ - HughHughTeotl

@HughHughTeotl 看起来是这样的。https://stackoverflow.com/a/38590278/2523899 - undefined

Answer 3

或者您可以创建自己的ListIterator：

public final class SparseArrayIterator<E> implements ListIterator<E> {

private final SparseArray<E> array;
private int cursor;
private boolean cursorNowhere;

/**
 * @param array
 *            to iterate over.
 * @return A ListIterator on the elements of the SparseArray. The elements
 *         are iterated in the same order as they occur in the SparseArray.
 *         {@link #nextIndex()} and {@link #previousIndex()} return a
 *         SparseArray key, not an index! To get the index, call
 *         {@link android.util.SparseArray#indexOfKey(int)}.
 */
public static <E> ListIterator<E> iterate(SparseArray<E> array) {
    return iterateAt(array, -1);
}

/**
 * @param array
 *            to iterate over.
 * @param key
 *            to start the iteration at. {@link android.util.SparseArray#indexOfKey(int)}
 *            < 0 results in the same call as {@link #iterate(android.util.SparseArray)}.
 * @return A ListIterator on the elements of the SparseArray. The elements
 *         are iterated in the same order as they occur in the SparseArray.
 *         {@link #nextIndex()} and {@link #previousIndex()} return a
 *         SparseArray key, not an index! To get the index, call
 *         {@link android.util.SparseArray#indexOfKey(int)}.
 */
public static <E> ListIterator<E> iterateAtKey(SparseArray<E> array, int key) {
    return iterateAt(array, array.indexOfKey(key));
}

/**
 * @param array
 *            to iterate over.
 * @param location
 *            to start the iteration at. Value < 0 results in the same call
 *            as {@link #iterate(android.util.SparseArray)}. Value >
 *            {@link android.util.SparseArray#size()} set to that size.
 * @return A ListIterator on the elements of the SparseArray. The elements
 *         are iterated in the same order as they occur in the SparseArray.
 *         {@link #nextIndex()} and {@link #previousIndex()} return a
 *         SparseArray key, not an index! To get the index, call
 *         {@link android.util.SparseArray#indexOfKey(int)}.
 */
public static <E> ListIterator<E> iterateAt(SparseArray<E> array, int location) {
    return new SparseArrayIterator<E>(array, location);
}

private SparseArrayIterator(SparseArray<E> array, int location) {
    this.array = array;
    if (location < 0) {
        cursor = -1;
        cursorNowhere = true;
    } else if (location < array.size()) {
        cursor = location;
        cursorNowhere = false;
    } else {
        cursor = array.size() - 1;
        cursorNowhere = true;
    }
}

@Override
public boolean hasNext() {
    return cursor < array.size() - 1;
}

@Override
public boolean hasPrevious() {
    return cursorNowhere && cursor >= 0 || cursor > 0;
}

@Override
public int nextIndex() {
    if (hasNext()) {
        return array.keyAt(cursor + 1);
    } else {
        throw new NoSuchElementException();
    }
}

@Override
public int previousIndex() {
    if (hasPrevious()) {
        if (cursorNowhere) {
            return array.keyAt(cursor);
        } else {
            return array.keyAt(cursor - 1);
        }
    } else {
        throw new NoSuchElementException();
    }
}

@Override
public E next() {
    if (hasNext()) {
        if (cursorNowhere) {
            cursorNowhere = false;
        }
        cursor++;
        return array.valueAt(cursor);
    } else {
        throw new NoSuchElementException();
    }
}

@Override
public E previous() {
    if (hasPrevious()) {
        if (cursorNowhere) {
            cursorNowhere = false;
        } else {
            cursor--;
        }
        return array.valueAt(cursor);
    } else {
        throw new NoSuchElementException();
    }
}

@Override
public void add(E object) {
    throw new UnsupportedOperationException();
}

@Override
public void remove() {
    if (!cursorNowhere) {
        array.remove(array.keyAt(cursor));
        cursorNowhere = true;
        cursor--;
    } else {
        throw new IllegalStateException();
    }
}

@Override
public void set(E object) {
    if (!cursorNowhere) {
        array.setValueAt(cursor, object);
    } else {
        throw new IllegalStateException();
    }
}
}

- 0101100101

---

个人认为这有点过度工程化。不过还是很棒的。 - hector6872

Answer 4

对于使用Kotlin的人来说，遍历SparseArray最简单的方法是：使用Anko或Android KTX的Kotlin扩展！（感谢Yazazzello指出了Android KTX）

只需调用forEach { i, item -> }

- 0101100101

---

是的，你说得对。我的错，我看了标签后认为 Kotlin 不应该在这里。但现在我重新考虑后，认为这个答案对 Kotlin 本身是一个很好的参考。虽然我建议使用 https://android.github.io/android-ktx/core-ktx/ 而不是使用 Anko（如果你能编辑你的答案并添加 android-ktx，我会点赞它）。 - Yazazzello

@Yazazzello 嘿，我甚至不知道 Android KTX，好主意！ - 0101100101

Answer 5

非常简单。只需确保在执行循环之前获取数组大小。

for(int i = 0, arraySize= mySparseArray.size(); i < arraySize; i++) {
   Object obj = mySparseArray.get(/* int key = */ mySparseArray.keyAt(i));
}

希望这有所帮助。

- Pascal

---

在循环之前“获取”大小没有任何意义，如果你只想要值，先获取键也没有意义。 - undefined

我有点困惑...在循环之前“获取”大小是一种优化。获取键是获取值的唯一方式：这是一个两步操作。请参考SparseArray的Javadoc。 - undefined

Answer 6

使用上述循环方式从SparseArray中删除所有元素会导致异常。

为避免此问题，请按照以下代码使用普通循环从SparseArray中删除所有元素：

private void getValues(){      
    for(int i=0; i<sparseArray.size(); i++){
          int key = sparseArray.keyAt(i);
          Log.d("Element at "+key, " is "+sparseArray.get(key));
          sparseArray.remove(key);
          i=-1;
    }
}

- Sackurise

---

结尾的 i=-1; 没有作用。此外，应优先使用一个名为 .clear() 的方法。 - Paul Woitaschek

为什么你会使用for()循环而不是while()循环？你所做的对于循环来说毫无意义。 - Phil A

我认为Sackurise想要写i-=1;来解决现在缺失的元素。但更好的方法是将循环反转：for(int i=sparseArray.size()-1; i>=0; i++){...}；或者使用while (sparseArray.size()>0) { int key=sparseArray.keyAt(0);...}。 - ths

“上述循环”这样的参考并没有任何意义。 - The incredible Jan

我认为“迭代器”的重点是安全的对象删除。我没有看到使用类似于HashMap的稀疏数组的Iterator类的任何示例。这最接近解决安全对象删除的问题，希望它能在不发生并发修改异常的情况下正常工作。 - Androidcoder

@Androidcoder 迭代器的作用是遍历列表。对象的删除只是其中一种可能的用途。"this"与迭代器无关。 - undefined

Answer 7

这是一个简单的Iterator<T>和Iterable<T>实现，适用于SparseArray<T>。

public class SparseArrayIterator<T> implements Iterator<T> {
    private final SparseArray<T> array;
    private int index;

    public SparseArrayIterator(SparseArray<T> array) {
        this.array = array;
    }

    @Override
    public boolean hasNext() {
        return array.size() > index;
    }

    @Override
    public T next() {
        return array.valueAt(index++);
    }

    @Override
    public void remove() {
        array.removeAt(index);
    }

}

public class SparseArrayIterable<T> implements Iterable<T> {
    private final SparseArray<T> sparseArray;

    public SparseArrayIterable(SparseArray<T> sparseArray) {
        this.sparseArray = sparseArray;
    }

    @Override
    public Iterator<T> iterator() {
        return new SparseArrayIterator<>(sparseArray);
    }
}

如果您想迭代不仅是值，还包括键：

public class SparseKeyValue<T> {
    private final int key;
    private final T value;

    public SparseKeyValue(int key, T value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return key;
    }

    public T getValue() {
        return value;
    }
}

public class SparseArrayKeyValueIterator<T> implements Iterator<SparseKeyValue<T>> {
    private final SparseArray<T> array;
    private int index;

    public SparseArrayKeyValueIterator(SparseArray<T> array) {
        this.array = array;
    }

    @Override
    public boolean hasNext() {
        return array.size() > index;
    }

    @Override
    public SparseKeyValue<T> next() {
        SparseKeyValue<T> keyValue = new SparseKeyValue<>(array.keyAt(index), array.valueAt(index));
        index++;
        return keyValue;
    }

    @Override
    public void remove() {
        array.removeAt(index);
    }

}

public class SparseArrayKeyValueIterable<T> implements Iterable<SparseKeyValue<T>> {
    private final SparseArray<T> sparseArray;

    public SparseArrayKeyValueIterable(SparseArray<T> sparseArray) {
        this.sparseArray = sparseArray;
    }

    @Override
    public Iterator<SparseKeyValue<T>> iterator() {
        return new SparseArrayKeyValueIterator<T>(sparseArray);
    }
}

创建返回Iterable<T>和Iterable<SparseKeyValue<T>>的实用方法非常有用：

public abstract class SparseArrayUtils {
    public static <T> Iterable<SparseKeyValue<T>> keyValueIterable(SparseArray<T> sparseArray) {
        return new SparseArrayKeyValueIterable<>(sparseArray);
    }

    public static <T> Iterable<T> iterable(SparseArray<T> sparseArray) {
        return new SparseArrayIterable<>(sparseArray);
    }
}

现在，您可以迭代SparseArray<T>：

SparseArray<String> a = ...;

for (String s: SparseArrayUtils.iterable(a)) {
   // ...
}

for (SparseKeyValue<String> s: SparseArrayUtils.keyValueIterable(a)) {
  // ...
}

- mixel

Answer 8

如果您使用Kotlin，则可以像以下方式使用扩展函数，例如：

fun <T> LongSparseArray<T>.valuesIterator(): Iterator<T> {
    val nSize = this.size()
    return object : Iterator<T> {
        var i = 0
        override fun hasNext(): Boolean = i < nSize
        override fun next(): T = valueAt(i++)
    }
}

fun <T> LongSparseArray<T>.keysIterator(): Iterator<Long> {
    val nSize = this.size()
    return object : Iterator<Long> {
        var i = 0
        override fun hasNext(): Boolean = i < nSize
        override fun next(): Long = keyAt(i++)
    }
}

fun <T> LongSparseArray<T>.entriesIterator(): Iterator<Pair<Long, T>> {
    val nSize = this.size()
    return object : Iterator<Pair<Long, T>> {
        var i = 0
        override fun hasNext(): Boolean = i < nSize
        override fun next() = Pair(keyAt(i), valueAt(i++))
    }
}

你也可以转换为列表，如果你愿意。例如：

sparseArray.keysIterator().asSequence().toList()

我认为甚至可以在LongSparseArray本身上使用remove（而不是迭代器），因为它是按升序排列的，这样做可能是安全的。

---

编辑：似乎有一种更简单的方法，可以使用collection-ktx（示例在这里）。实际上，它的实现方式非常类似于我的写法。

Gradle需要这个：

implementation 'androidx.core:core-ktx:#'
implementation 'androidx.collection:collection-ktx:#'

这是 LongSparseArray 的用法：

    val sparse= LongSparseArray<String>()
    for (key in sparse.keyIterator()) {
    }
    for (value in sparse.valueIterator()) {
    }
    sparse.forEach { key, value -> 
    }

如果你使用Java，你可以使用LongSparseArrayKt.keyIterator、LongSparseArrayKt.valueIterator和LongSparseArrayKt.forEach来操作，其他情况也一样。

- android developer

Answer 9

答案是否定的，因为 SparseArray 没有提供它。正如 pst 所说，这个东西没有提供任何接口。

你可以从 0-size() 循环并跳过返回 null 的值，但只有这样而已。

正如我在我的评论中所述，如果需要迭代，请使用 Map 而不是 SparseArray。例如，使用按键排序迭代的 TreeMap。

TreeMap<Integer, MyType>

- John B

Answer 10

被接受的答案有一些漏洞。SparseArray的美妙之处在于它允许索引中存在间隙。因此，我们可以在SparseArray中使用两个类似下面的地图...

(0,true)
(250,true)

注意这里的大小将为2。如果我们迭代大小，我们只会得到与索引0和索引1映射的值。因此，具有键为250的映射不会被访问。

for(int i = 0; i < sparseArray.size(); i++) {
   int key = sparseArray.keyAt(i);
   // get the object by the key.
   Object obj = sparseArray.get(key);
}

最好的方法是通过迭代数据集的大小，然后使用数组的get()函数检查这些索引。以下是一个示例，其中我允许批量删除项目的适配器。

for (int index = 0; index < mAdapter.getItemCount(); index++) {
     if (toDelete.get(index) == true) {
        long idOfItemToDelete = (allItems.get(index).getId());
        mDbManager.markItemForDeletion(idOfItemToDelete);
        }
    }

我认为理想情况下SparseArray家族应该有一个getKeys()方法，但遗憾的是它没有。

- Tyler Pfaff

---

你错了 - keyAt 方法返回第n个键的值（在你的例子中，keyAt(1) 会返回 250），不要与 get 混淆，后者返回引用键的元素的值。 - Eborbob

我不确定你评论中的“this”是什么意思。你是在承认你的答案是错误的，还是在说我的评论是错误的？如果是后者，请查看http://developer.android.com/reference/android/util/SparseArray.html#keyAt%28int%29。 - Eborbob

我的回答是错误的，我不会删除它，以便其他人可以学习。 - Tyler Pfaff