本文介绍了MFC词典集合,具有密钥一致性和按位置排序的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

查看

我不能看到我需要的MFC集合。

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

关于还表示

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

正如我所预期的,我认为它使用散列算法。

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为例) - 目的:交换顺序元素getti遵循所述的顺序

  • 看起来我甚至不需要是一个真正的钥匙 - 我真的不需要那些疯狂的哈希算法快速访问。而且,通过密钥访问元素的问题,似乎现在我不需要它,但是开始使用它时,我只能安全地回答这个问题。

  • 不需要快速插入,删除,更新等。

  • 不需要快速搜索指定的元素

  • 键unicity

  • Ordered (by an int, for example) - Purpose: Swapping elements of order and also getting them following the sequence that was stated
  • Seems to me this even doesn´t even need to be a "real key" - I really don't need those crazy hashing algorhitms for fast access. And , the question of accessing elements by key, it seems I don't need it for now, but I can only answer securely to this when beginning to use it.
  • Don't need fast insert, delete, update, etc.
  • Don't need fast search of a specified element
  • key unicity

我想知道我可以在实际应用中应用这种模式多少次。
你可以建议我最好的解决方案是什么?

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是按键排序的,所以不合适。

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++.

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

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.

提前感谢,

Sérgio

推荐答案

我决定从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 << "\n\t[";
            DumpElements<KEY>(dc, key, 1);
            dc << "] = ";
            DumpElements<VALUE>(dc, val, 1);
        }
    }

    dc << "\n";
}

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.

这篇关于MFC词典集合,具有密钥一致性和按位置排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

11-02 20:23