具有关键唯一性和按位置排序的 MFC 字典集合

2022-01-12 00:00:00 dictionary mfc

看桌子http://msdn.microsoft.com/en-us/library/y1z022s1%28v=vs.80%29.aspx#_core_collection_shape_features

我看不到满足我需要的 MFC 集合.

I can not see a MFC collection for the purpose I need.

http://上的 CMap 文档msdn.microsoft.com/en-us/library/s897094z%28v=vs.80%29.aspx 还声明

你可能认为这个迭代是键值顺序的,但不是.检索到的元素的顺序是不确定的."

正如我所期望的那样,我认为它使用散列算法.

as I would expect from a thing I presume it uses hashing algorhitms.

我需要的是一本具有以下功能的字典:

What I need, is a dictionary that has the following features:

  • 有序(例如,通过 int) - 目的:交换 order 元素并按照规定的顺序获取它们
  • 在我看来,这甚至不需要成为真正的密钥"――我真的不需要那些疯狂的散列算法来快速访问.还有,按键访问元素的问题,我好像暂时不需要,但是开始用的时候才能安全回答.
  • 不需要快速插入、删除、更新等.
  • 不需要快速搜索指定元素
  • 关键的唯一性

我想知道我可以在实际应用中应用这种模式多少次.您可以为此建议我的最佳解决方案是什么?

I wonder how many times I can apply this pattern in real apps. What is the best solution you can suggest me for this?

注意:不久前,我在 C# 中也遇到了同样的问题.也欢迎它的解决方案.如果我没记错 SortedDictionary 是按 key 排序的,那么它是不合适的.

Note: I had the same problem in C# also, some time ago. Solutions for it are also welcome. If I recall correctly SortedDictionary is sorted on the key, so it is not suitable.

即使使用 MFC 中的东西更可取――只是为了不与现有的代码库发生冲突――也不是义务.因此,如果它是标准 C++,您可以提出任何您想要的建议.

Even if it would be preferable - only for the sake of not being dissonant with the already existing code base - to use a thing from MFC, it is not an obligation. So you can suggest whatever you want, if it is standard C++.

为了提高清晰度:容器的每个元素的描述将是

For improving the clarity: the description of each element of the container would be

{
     int Unique NonNullable OrderIndex,
     enum KeyEnum Unique NonNullable key, 
     enum ValueEnum NotUnique NonNullable value
}

如果它被实现为动态数组,我什至不关心存储 OrderIndex.对于这个,我真的只需要一个唯一的值来指示相对位置并且可以交换位置元素.

If it is implemented as something like a dynamic array, I really don't even care about storing the OrderIndex. For this one, I really only need a unique value that indicates the relative position and have the possibilty to swap elements of position.

提前致谢,

塞尔吉奥

推荐答案

我决定从 CMap 和 CArray 派生一个模板类,并编写 ArrayMapTempl.h 文件如下:

I decided to derive a templated class from both CMap and CArray and write the ArrayMapTempl.h file as follows:

//Author: Sérgio Loureiro. This is open source.

#include <afxtempl.h>

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
class CArrayMap: protected CArray<KEY,ARG_KEY>, protected CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>
{
private:
    bool m_isChangingSize;
public:
    CArrayMap():
      m_isChangingSize(false)
    {
    };

    CArrayMap(const CArrayMap& src){};
    CArrayMap operator=(const CArrayMap& src){return *this;};

    // Attributes
    INT_PTR GetSize() const;
    INT_PTR GetCount() const;
    BOOL IsEmpty() const;
    INT_PTR GetUpperBound() const;

    // Lookup
    int Lookup(ARG_KEY key) const;
    int Lookup(ARG_KEY key, VALUE& rValue) const;

// Operations
    // Clean up
    void RemoveAll();

    // Accessing elements
    const CPair& GetAt(INT_PTR nIndex) const;
    CPair& GetAt(INT_PTR nIndex);
    void SetAt(INT_PTR nIndex, ARG_KEY newKey, ARG_VALUE newValue);
    const CPair& ElementAt(INT_PTR nIndex) const;
    CPair& ElementAt(INT_PTR nIndex);

    // Direct Access to the element data
    const CPair& GetData() const;
    CPair& GetData();

    // Potentially growing the array
    INT_PTR Add(ARG_KEY newKey, ARG_VALUE newValue);
    void Copy(const CArrayMap& src);

    // overloaded operator helpers
    const CPair& operator[](INT_PTR nIndex) const;
    CPair& operator[](INT_PTR nIndex);

    // Operations that move elements around

    BOOL Swap(INT_PTR nIndex, INT_PTR nIndex2);
    BOOL MoveUp(INT_PTR nIndex);
    BOOL MoveDown(INT_PTR nIndex);

    BOOL SwapByKey(ARG_KEY key, ARG_KEY key2);
    BOOL MoveUpByKey(ARG_KEY key);
    BOOL MoveDownByKey(ARG_KEY key);

    BOOL InsertAt(INT_PTR nIndex, ARG_KEY newKey, ARG_VALUE newValue);
    BOOL RemoveAt(INT_PTR nIndex);
    BOOL RemoveByKey(ARG_KEY key);


public:
    void Serialize(CArchive&);
#ifdef _DEBUG
    void Dump(CDumpContext&) const;
    void AssertValid() const;
#endif

#if 0   
public:
// Construction
    CArray();

// Attributes
    INT_PTR GetSize() const;
    INT_PTR GetCount() const;
    BOOL IsEmpty() const;
    INT_PTR GetUpperBound() const;
    void SetSize(INT_PTR nNewSize, INT_PTR nGrowBy = -1);

// Operations
    // Clean up
    void FreeExtra();
    void RemoveAll();

    // Accessing elements
    const TYPE& GetAt(INT_PTR nIndex) const;
    TYPE& GetAt(INT_PTR nIndex);
    void SetAt(INT_PTR nIndex, ARG_TYPE newElement);
    const TYPE& ElementAt(INT_PTR nIndex) const;
    TYPE& ElementAt(INT_PTR nIndex);

    // Direct Access to the element data (may return NULL)
    const TYPE* GetData() const;
    TYPE* GetData();

    // Potentially growing the array
    void SetAtGrow(INT_PTR nIndex, ARG_TYPE newElement);
    INT_PTR Add(ARG_TYPE newElement);
    INT_PTR Append(const CArray& src);
    void Copy(const CArray& src);

    // overloaded operator helpers
    const TYPE& operator[](INT_PTR nIndex) const;
    TYPE& operator[](INT_PTR nIndex);

    // Operations that move elements around
    void RemoveAt(INT_PTR nIndex, INT_PTR nCount = 1);
    void InsertAt(INT_PTR nStartIndex, CArray* pNewArray);

// Implementation
protected:
    TYPE* m_pData;   // the actual array of data
    INT_PTR m_nSize;     // # of elements (upperBound - 1)
    INT_PTR m_nMaxSize;  // max allocated
    INT_PTR m_nGrowBy;   // grow amount

public:
    ~CArray();
    void Serialize(CArchive&);
#ifdef _DEBUG
    void Dump(CDumpContext&) const;
    void AssertValid() const;
#endif
#endif

//----------------------------------------------------------------------------------------
#if 0
public:
    // CPair
    struct CPair
    {
        const KEY key;
        VALUE value;
    protected:
        CPair( ARG_KEY keyval ) : key( keyval ) {}
    };

protected:
    // Association
    class CAssoc : public CPair
    {
        friend class CMap<KEY,ARG_KEY,VALUE,ARG_VALUE>;
        CAssoc* pNext;
        UINT nHashValue;  // needed for efficient iteration
    public:
        CAssoc( ARG_KEY key ) : CPair( key ) {}
    };

public:
// Construction
    /* explicit */ CMap(INT_PTR nBlockSize = 10);

// Attributes
    // number of elements
    INT_PTR GetCount() const;
    INT_PTR GetSize() const;
    BOOL IsEmpty() const;

    // Lookup
    BOOL Lookup(ARG_KEY key, VALUE& rValue) const;
    const CPair *PLookup(ARG_KEY key) const;
    CPair *PLookup(ARG_KEY key);

// Operations
    // Lookup and add if not there
    VALUE& operator[](ARG_KEY key);

    // add a new (key, value) pair
    void SetAt(ARG_KEY key, ARG_VALUE newValue);

    // removing existing (key, ?) pair
    BOOL RemoveKey(ARG_KEY key);
    void RemoveAll();

    // iterating all (key, value) pairs
    POSITION GetStartPosition() const;

    const CPair *PGetFirstAssoc() const;
    CPair *PGetFirstAssoc();

    void GetNextAssoc(POSITION& rNextPosition, KEY& rKey, VALUE& rValue) const;

    const CPair *PGetNextAssoc(const CPair *pAssocRet) const;
    CPair *PGetNextAssoc(const CPair *pAssocRet);

    // advanced features for derived classes
    UINT GetHashTableSize() const;
    void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);

// Implementation
protected:
    CAssoc** m_pHashTable;
    UINT m_nHashTableSize;
    INT_PTR m_nCount;
    CAssoc* m_pFreeList;
    struct CPlex* m_pBlocks;
    INT_PTR m_nBlockSize;

    CAssoc* NewAssoc(ARG_KEY key);
    void FreeAssoc(CAssoc*);
    CAssoc* GetAssocAt(ARG_KEY, UINT&, UINT&) const;

public:
    ~CMap();
    void Serialize(CArchive&);
#ifdef _DEBUG
    void Dump(CDumpContext&) const;
    void AssertValid() const;
#endif
#endif

};

template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline INT_PTR CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetSize() const
{
    ASSERT(CArray::m_nSize == CMap::m_nCount);
    return CArray::GetSize();
};


template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline INT_PTR CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetCount() const
{
    ASSERT(CArray::m_nSize == CMap::m_nCount);
    return CArray::GetCount();
}


template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline BOOL CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::IsEmpty() const
{ 
    ASSERT(CArray::m_nSize == CMap::m_nCount);
    return CArray::IsEmpty();
}

template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline INT_PTR CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetUpperBound() const
{ 
    ASSERT(CArray::m_nSize == CMap::m_nCount);
    return CArray::GetUpperBound();
}


template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline INT_PTR CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Add(ARG_KEY newKey, ARG_VALUE newValue)
{ 
    VALUE rValue;
    if( CMap::Lookup(newKey,rValue))    //already exists
        return -1;

    INT_PTR nIndex = CArray::m_nSize;   //old size will be the new position

    m_isChangingSize= true;
    CMap::operator[] (newKey)= newValue;
    CArray::Add(newKey);
    m_isChangingSize= false;

    ASSERT(CArray::m_nSize == CMap::m_nCount);
    return nIndex;
};


template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline const typename CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CPair&
    CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAt(INT_PTR nIndex) const
{ 
    ASSERT(nIndex >= 0 && nIndex < m_nSize);
    if(nIndex >= 0 && nIndex < m_nSize)
    {
        return *CMap::PLookup(CArray::GetAt(nIndex));
    }
    AfxThrowInvalidArgException();
};


template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
inline typename CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CPair&
    CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAt(INT_PTR nIndex)
{ 
    ASSERT(nIndex >= 0 && nIndex < m_nSize);
    if(nIndex >= 0 && nIndex < m_nSize)
    {
        return *CMap::PLookup(CArray::GetAt(nIndex));
    }
    AfxThrowInvalidArgException();
};

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
int CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup(ARG_KEY key) const
{
    VALUE rValue;
    return this->Lookup(key, rValue);
};

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
int CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup(ARG_KEY key, VALUE& rValue) const
{
    for (int i=0; i<m_nSize ;i++)
    {
        if(CArray::operator [] ( i ) == key && CMap::Lookup(key, rValue))
        {
            return i;
        }
    }
    return -1;
};


template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveAll()
{
    m_isChangingSize=true;
    CMap::RemoveAll();
    CArray::RemoveAll();
    m_isChangingSize=false;

    ASSERT(CArray::m_nSize == CMap::m_nCount);
};



template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Swap(INT_PTR nIndex, INT_PTR nIndex2)
{
    if(nIndex<0 || nIndex2<0)
        return FALSE;

    if(nIndex>=m_nSize || nIndex2>=m_nSize)
        return FALSE;

    //Swap with itself. Everything is fine and nothing needs to be done
    if(nIndex == nIndex2)
        return TRUE;

    KEY k= CArray::GetAt(nIndex);
    CArray::SetAt(nIndex, CArray::GetAt(nIndex2));
    CArray::SetAt(nIndex, k);
};

template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::MoveUp(INT_PTR nIndex)
{
    if (nIndex == 0)
        return FALSE;
    return Swap(nIndex,nIndex-1);
};

template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::MoveDown(INT_PTR nIndex)
{
    if (nIndex == m_nSize-1)
        return FALSE;
    return Swap(nIndex,nIndex+1);
};

template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::SwapByKey(ARG_KEY key, ARG_KEY key2)
{
    int nIndex= Lookup(key);
    int nIndex2= Lookup(key2);
    if(nIndex == -1 || nIndex2 == -1)
        return FALSE;

    return Swap(nIndex,nIndex2);
}

template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::MoveUpByKey(ARG_KEY key)
{
    int nIndex= Lookup(key);
    if(nIndex == -1)
        return FALSE;

    return MoveUp(nIndex);
}

template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::MoveDownByKey(ARG_KEY key)
{
    int nIndex= Lookup(key);
    if(nIndex == -1)
        return FALSE;

    return MoveDown(nIndex);
}



template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
int CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::InsertAt(INT_PTR nIndex,ARG_KEY newKey, ARG_VALUE newValue)
{

    AssertValid();          //ASSERT_VALID(this);

    if(nIndex < 0)
        return FALSE;   //AfxThrowInvalidArgException();

    if(nIndex > m_nSize)    //doesn't make sense to grow more than last+1 , given newKey has to be unique
        return FALSE;

    //I am not using this->Lookup(ARG_KEY key), because I 
    //presume CMap::Lookup(ARG_KEY key, VALUE& rValue) will be faster,
    //as it does not need to traverse the array.    

    VALUE rValue;
    if(CMap::Lookup(newKey,rValue)) //already exists
        return FALSE;

    m_isChangingSize=true;
    CMap::operator[] (newKey)= newValue;
    CArray::InsertAt(nIndex,newKey,1);
    m_isChangingSize=false;

    ASSERT(CArray::m_nSize == CMap::m_nCount);
    return TRUE;
}


template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveAt(INT_PTR nIndex)
{
    if(nIndex<0 || nIndex>= m_nSize)
        return FALSE;

    KEY k= CArray::GetAt(nIndex);

    //I am not using this->Lookup(ARG_KEY key), because I 
    //presume CMap::Lookup(ARG_KEY key, VALUE& rValue) will be faster,
    //as it does not need to traverse the array.    

    VALUE rValue;
    if(CMap::Lookup(k,rValue))  //already exists
    {
        m_isChangingSize= true;
        CMap::RemoveKey(k);
        CArray::RemoveAt(nIndex);
        m_isChangingSize= false;

        ASSERT(CArray::m_nSize == CMap::m_nCount);
        return TRUE;
    }
    else
        return FALSE;
};

template <class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
BOOL CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveByKey(ARG_KEY key)
{
    int nIndex= Lookup(key);
    if(nIndex == -1)
        return FALSE;

    KEY k= CArray::GetAt(nIndex);

    return RemoveAt(nIndex);
};


template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Serialize(CArchive& ar)
{
    ASSERT(CArray::m_nSize == CMap::m_nCount);
    //ASSERT_VALID((const CArray *)this);
    //ASSERT_VALID((const CMap *)this);

    CObject::Serialize(ar);

    if (ar.IsStoring())
    {
        ar.WriteCount(m_nSize);
        if (m_nSize == 0)
            return;  // nothing more to do

        for(INT_PTR i=0;i<m_nSize;i++)
        {
            KEY* pKey;
            VALUE* pValue;
            /* 
             * in some cases the & operator might be overloaded, and we cannot use it to 
             * obtain the address of a given object.  We then use the following trick to 
             * get the address
             */
            pKey = reinterpret_cast< KEY* >( &reinterpret_cast< int& >( const_cast< KEY& > ( static_cast< const KEY& >( CArray::operator[]( i ) ) ) ) );
            pValue = reinterpret_cast< VALUE* >( &reinterpret_cast< int& >( static_cast< VALUE& >( CMap::operator[]( *pKey ) ) ) );
            SerializeElements<KEY>(ar, pKey, 1);
            SerializeElements<VALUE>(ar, pValue, 1);
        }
    }
    else
    {
        DWORD_PTR nNewCount = ar.ReadCount();
        while (nNewCount--)
        {
            KEY newKey[1];
            VALUE newValue[1];
            SerializeElements<KEY>(ar, newKey, 1);
            SerializeElements<VALUE>(ar, newValue, 1);
            this->Add(newKey[0], newValue[0]);  //includes checking if it already exists
        }
    }
}

#ifdef _DEBUG
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Dump(CDumpContext& dc) const
{
    ASSERT(CArray::m_nSize == CMap::m_nCount);

    CObject::Dump(dc);

    dc << "with " << m_nSize << " elements";
    if (dc.GetDepth() > 0)
    {
        // Dump in format "[key] -> value"
        KEY key[1];
        VALUE val[1];

        POSITION pos = GetStartPosition();
        while (pos != NULL)

        for (int i=0; i<m_nSize; i++)
        {
            key[0]= CArray::operator[]( i );

            //val[0]= CMap::operator[]( key[0] );
            CMap::Lookup(key[0], val[0]);

            dc << "
	[";
            DumpElements<KEY>(dc, key, 1);
            dc << "] = ";
            DumpElements<VALUE>(dc, val, 1);
        }
    }

    dc << "
";
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CArrayMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::AssertValid() const
{
    CArray::AssertValid();
    CMap::AssertValid();

    if(!m_isChangingSize)   
        ASSERT(CArray::m_nSize == CMap::m_nCount);
}

#endif //_DEBUG

现在我拥有了我需要的一切.我没有测试所有东西,但我相信如果需要的话,只需要很少的修正.

Now I have everything I need. I didn't test everything, but I believe that only little corrections will be needed, if needed.

无论如何,谢谢大家的回答和评论.

Anyway, thank you all for the answers and comments.

相关文章