• Android12之容器类SortedVector、KeyedVector、Vector、VectorImpl总结(一百六十六)

    简介： CSDN博客专家，专注Android/Linux系统，分享多mic语音方案、音视频、编解码等技术，与大家一起成长！

    优质专栏：Audio工程师进阶系列【原创干货持续更新中……】🚀

    人生格言： 人生从来没有捷径，只有行动才是治疗恐惧和懒惰的唯一良药.

    更多原创,欢迎关注：Android系统攻城狮

    欢迎关注Android系统攻城狮

    1.前言

    本篇目的：理解Android12之容器类SortedVector、KeyedVector、Vector、VectorImpl之间联系。

    2.SortedVector、KeyedVector、Vector、VectorImpl介绍

    在Android中，SortedVector、KeyedVector、Vector和VectorImpl是用于数据存储和管理的容器类。

    1. SortedVector：

      • 原理：SortedVector是一个有序容器，它基于二进制搜索树（Binary Search Tree）实现。它会在插入元素时自动维持元素的有序性，并提供了一些方法来搜索、插入、删除和访问元素。
      • 作用：SortedVector可用于需要有序元素管理的场景，比如在大量数据中进行快速的查找、插入和删除等操作。

    2. KeyedVector：

      • 原理：KeyedVector是一种键值对容器，它基于哈希表（Hash Table）实现。每个键由一个哈希函数计算得到一个索引，然后将值存储在该索引位置上。在具有相同索引的情况下，它会处理冲突并保证键的唯一性。
      • 作用：KeyedVector可用于需要通过键来访问值的场景，比如实现高效的索引、查找和删除操作。

    3. Vector：

      • 原理：Vector是一个动态数组，它可以根据需要动态增加或减少容量。Vector在内部使用数组来存储元素，并提供了一些方法用于插入、删除、访问和修改元素。
      • 作用：Vector可用于需要动态管理大小的数组操作，比如在需要经常插入和删除元素的场景中。

    4. VectorImpl：

      • 原理：VectorImpl是Vector的底层实现，它提供了对底层数组的直接访问和操作。它主要用于实现Vector的相关方法。
      • 作用：VectorImpl在Vector类中作为内部实现的一部分，用于提供底层数组的管理和操作功能。

    总结：

    • SortedVector和KeyedVector适用于需要对数据进行排序或通过键值对进行访问的场景，
    • 而Vector适用于需要动态管理数组大小的场景。
    • VectorImpl则是Vector类的底层实现，提供对底层数组的直接操作。

    3.SortedVector、KeyedVector、Vector、VectorImpl关系类图

    继承
    关联友元类
    继承
    继承
    继承
    KeyedVector
    DefaultKeyedVector
    SortedVector
    friend class Vector
    SortedVectorImpl
    VectorImpl
    Vector
    typedef TYPE value_type

    4.SortedVector、KeyedVector、Vector、VectorImpl实现

    <1>.VectorImpl定义

    system/core/libutils/include/utils/VectorImpl.h

    class VectorImpl
{
/*! C-style array access */
    inline  const void*     arrayImpl() const       { return mStorage; }
            void*           editArrayImpl();
            
    /*! vector stats */
    inline  size_t          size() const        { return mCount; }
    inline  bool            isEmpty() const     { return mCount == 0; }
            size_t          capacity() const;
            ssize_t         setCapacity(size_t size);
            ssize_t         resize(size_t size);

            /*! append/insert another vector or array */
            ssize_t         insertVectorAt(const VectorImpl& vector, size_t index);
            ssize_t         appendVector(const VectorImpl& vector);
            ssize_t         insertArrayAt(const void* array, size_t index, size_t length);
            ssize_t         appendArray(const void* array, size_t length);
            
            /*! add/insert/replace items */
            ssize_t         insertAt(size_t where, size_t numItems = 1);
            ssize_t         insertAt(const void* item, size_t where, size_t numItems = 1);
            void            pop();
            void            push();
            void            push(const void* item);
            ssize_t         add();
            ssize_t         add(const void* item);
            ssize_t         replaceAt(size_t index);
            ssize_t         replaceAt(const void* item, size_t index);


class SortedVectorImpl : public VectorImpl
{
   public:
                            SortedVectorImpl(size_t itemSize, uint32_t flags);
    explicit                SortedVectorImpl(const VectorImpl& rhs);
    virtual                 ~SortedVectorImpl();
    
    SortedVectorImpl&     operator = (const SortedVectorImpl& rhs);    

    //! finds the index of an item
            ssize_t         indexOf(const void* item) const;

    //! finds where this item should be inserted
            size_t          orderOf(const void* item) const;

    //! add an item in the right place (or replaces it if there is one)
            ssize_t         add(const void* item);

    //! merges a vector into this one
            ssize_t         merge(const VectorImpl& vector);
};
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    <2>.VectorImpl实现

    system/core/libutils/VectorImpl.cpp

    VectorImpl::VectorImpl(size_t itemSize, uint32_t flags)
    : mStorage(nullptr), mCount(0), mFlags(flags), mItemSize(itemSize)
{
}

VectorImpl::VectorImpl(const VectorImpl& rhs)
    :   mStorage(rhs.mStorage), mCount(rhs.mCount),
        mFlags(rhs.mFlags), mItemSize(rhs.mItemSize)
{
    if (mStorage) {
        SharedBuffer::bufferFromData(mStorage)->acquire();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    <3>.SortedVector定义与实现

    system/core/libutils/include/utils/SortedVector.h

    template <class TYPE>
class SortedVector : private SortedVectorImpl
{
    friend class Vector<TYPE>;
};

template<class TYPE> inline
SortedVector<TYPE>::SortedVector()
    : SortedVectorImpl(sizeof(TYPE),
                ((traits<TYPE>::has_trivial_ctor   ? HAS_TRIVIAL_CTOR   : 0)
                |(traits<TYPE>::has_trivial_dtor   ? HAS_TRIVIAL_DTOR   : 0)
                |(traits<TYPE>::has_trivial_copy   ? HAS_TRIVIAL_COPY   : 0))
                )
{
}

template<class TYPE> inline
SortedVector<TYPE>::SortedVector(const SortedVector<TYPE>& rhs)
    : SortedVectorImpl(rhs) {
}

template<class TYPE> inline
SortedVector<TYPE>::~SortedVector() {
    finish_vector();
}

template<class TYPE> inline
SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) {
    SortedVectorImpl::operator = (rhs);
    return *this;
}

template<class TYPE> inline
const SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) const {
    SortedVectorImpl::operator = (rhs);
    return *this;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    <4>.KeyedVector定义与实现

    system/core/libutils/include/utils/KeyedVector.h

    template <typename KEY, typename VALUE>
class KeyedVector
{
public:
    typedef KEY    key_type;
    typedef VALUE  value_type;

    inline                  KeyedVector();
};

template <typename KEY, typename VALUE>
class DefaultKeyedVector : public KeyedVector<KEY, VALUE>
{
public:
    inline                  DefaultKeyedVector(const VALUE& defValue = VALUE());
            const VALUE&    valueFor(const KEY& key) const;

private:
            VALUE                                           mDefault;
};

// ---------------------------------------------------------------------------

template<typename KEY, typename VALUE> inline
KeyedVector<KEY,VALUE>::KeyedVector()
{
}

template<typename KEY, typename VALUE> inline
bool KeyedVector<KEY,VALUE>::isIdenticalTo(const KeyedVector<KEY,VALUE>& rhs) const {
    return mVector.array() == rhs.mVector.array();
}

template<typename KEY, typename VALUE> inline
ssize_t KeyedVector<KEY,VALUE>::indexOfKey(const KEY& key) const {
    return mVector.indexOf( key_value_pair_t<KEY,VALUE>(key) );
}

template<typename KEY, typename VALUE> inline
const VALUE& KeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
    ssize_t i = this->indexOfKey(key);
    LOG_ALWAYS_FATAL_IF(i<0, "%s: key not found", __PRETTY_FUNCTION__);
    return mVector.itemAt(i).value;
}

template<typename KEY, typename VALUE> inline
const VALUE& KeyedVector<KEY,VALUE>::valueAt(size_t index) const {
    return mVector.itemAt(index).value;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    <5>.Vector定义与实现

    system/core/libutils/include/utils/Vector.h

    template <class TYPE>
class Vector : private VectorImpl
{
public:
            typedef TYPE    value_type;

    /*!
     * Constructors and destructors
     */

                            Vector();
                            Vector(const Vector<TYPE>& rhs);
    explicit                Vector(const SortedVector<TYPE>& rhs);
    virtual                 ~Vector();

    /*! copy operator */
            const Vector<TYPE>&     operator = (const Vector<TYPE>& rhs) const;
            Vector<TYPE>&           operator = (const Vector<TYPE>& rhs);

            const Vector<TYPE>&     operator = (const SortedVector<TYPE>& rhs) const;
            Vector<TYPE>&           operator = (const SortedVector<TYPE>& rhs);

            /*
     * empty the vector
     */
     };

template<class TYPE> inline
Vector<TYPE>::Vector()
    : VectorImpl(sizeof(TYPE),
                ((traits<TYPE>::has_trivial_ctor   ? HAS_TRIVIAL_CTOR   : 0)
                |(traits<TYPE>::has_trivial_dtor   ? HAS_TRIVIAL_DTOR   : 0)
                |(traits<TYPE>::has_trivial_copy   ? HAS_TRIVIAL_COPY   : 0))
                )
{
}

template<class TYPE> inline
Vector<TYPE>::Vector(const Vector<TYPE>& rhs)
    : VectorImpl(rhs) {
}

template<class TYPE> inline
Vector<TYPE>::Vector(const SortedVector<TYPE>& rhs)
    : VectorImpl(static_cast<const VectorImpl&>(rhs)) {
}

template<class TYPE> inline
Vector<TYPE>::~Vector() {
    finish_vector();
}

template<class TYPE> inline
Vector<TYPE>& Vector<TYPE>::operator = (const Vector<TYPE>& rhs) {
    VectorImpl::operator = (rhs);
    return *this;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
  • 相关阅读:
    机电设备制造企业，如何借助ERP系统做好客供料管理？
    抽象工厂模式：构建复杂的对象族
    UMLChina建模知识竞赛第4赛季第17轮
    huggingface_hub v0.17 现已发布
    风控图算法之社群发现算法（小数据集Python版）
    excel提示stdole32.tlb的解决方法
    ROS SMACH个人学习记录
    docker
    十年架构五年生活-09 五年之约如期而至
    谷歌翻译下载-大家都在用的批量谷歌翻译软件下载
  • 原文地址：https://blog.csdn.net/u010164190/article/details/133272452