具有关键唯一性和按位置排序的 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.
相关文章