一、问题简介

       在C++的开发工作中，经常会将STL的标准容器进行一层封装，以满足更高级的需求，如支持外部内存等。在封装容器时，容易出现问题的地方包括容器的元素运算符以及容器的内存分配器，本人在做相关的工作时，将上述两方面所遇到问题的分析解决方法进行了如下总结。

二、问题一：重载运算符时的问题

        对于被封装的STL容器，由于其可能作为自定义数据类型而成为其他容器（如基于RB Tree的容器map和基于Hash Table的容器unordered_set）的元素，所以需要在封装时重载容器的运算符。具体需要重载的运算符包括用于RB Tree中排序的比较运算符"<"，以及用于无序容器中判等使用的"=="运算符，如在封装容器类“CVector”中可以进行以下重载：

friend bool operator < (const CVector<T, Allocator> &vec1, const CVector<T, Allocator> &vec2)
{
    return vec1.m_vector < vec2.m_vector; // 重载运算符"<"
}
friend bool operator == (const CVector<T, Allocator> &vec1, const CVector<T, Allocator> &vec2)
{
    return vec1.m_vector == vec2.m_vector; // 重载运算符"=="
}

        对于C++的类，重载运算符的函数可以声明为成员函数，也可以声明为友元函数，如对于一个“person”类：

class person {
public:
    bool operator<(const Person &arg); // 重载运算符的函数作为成员函数
private:
    int a;
};
bool person::operator<(const Person &arg)
{
    if((this->a) < arg.a) {}
}
// or---------------------------------------------------------------
class person {
public:
    friend bool operator<(const Person& arg1, const Person& arg2); // 重载运算符的函数作为友元函数(友元函数不属于成员函数)
private:
    int a;
};
bool operator<(const Person& arg1, const Person& arg2) // 实现时不需要类名限定，不属于任何类
{
    if(arg1.a < arg2.a) {}
}

但是，在封装容器的内部，“<“和”= =“运算符只能声明为友元函数，因为封装容器时使用了类模板，所以封装的容器是可以被继承的，当继承下来的子类容器的对象被装载进别的容器时，子类对象和父类对象一样可以执行”<“或”= =“操作，这个过程其实是发生了隐式类型转换。友元函数没有this指针，所需操作数都必须在参数表显式声明，很容易实现类型的隐式转换，所以使用友元函数就满足了第一个参数需要隐式转换的需求，使用成员函数重载运算符则不满足要求。

       然而，容器内部的另一些运算符重载时则只能声明为成员函数，如赋值运算符”=”、函数调用运算符“()“、下标运算符”[]”和通过指针访问的类成员运算符”->”，如下所示。在重载上述运算符时，它们左侧的操作数均为重载了运算符类的对象，如果把这些运算符重载为友元函数，这样的话一些非左值（如常量）会被编译器隐式转换为一个临时对象，这样非左值就会出现在运算符的左边，破坏了运算符的语义，如2=C；另外，编译器也会提供一个默认的赋值运算符，如果自己定义为友元函数，函数的参数列表不一样，不会发生重载。

CVector &operator=(const CVector<T, Allocator> &vec)  // 重载运算符"="
{
    m_vector = vec.m_vector;
    return *this;
}
T &operator[](const int &n)  // 重载运算符"[]"
{
    return m_vector[n];
}

 因此，在封装容器的内部，重载运算符可以总结为两种情况：
        a.运算符左侧操作数能够发生隐式类型转换，借助友元函数重载；
        b.运算符左侧操作数不能发生隐式类型转换，使用成员函数重载。

三、问题二：分配器构造函数的问题

        封装容器的内存分配器问题容易出现在封装基于Hash Table的容器时，通常会遇到如下错误：

error: no matching function for call to ‘myAlloc::CAllocator<std::__detail::_Hash_node_base*, (_MEM_TYPE_E)0u, 0u>::CAllocator(std::_Hashtable<int, int, myAlloc::CAllocator<int, (_MEM_TYPE_E)0u, 0u>, std::__detail::_Identity, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, true, true> >::_Node_allocator_type&)’_Bucket_allocator_type __alloc(_M_node_allocator());
上述错误指没有匹配的函数调用自定义分配器，可能的原因包括以下两方面。

       a.封装容器底层的_Hashtable使用自定义内存分配器导致的错误，因此先验证该猜测：

验证步骤一：_Hashtable使用STL自带的内存分配器。

using _Key   = int;
using _Value = int;
using _Tp    = std::pair<const _Key, _Value>;
using _Hash  = std::hash<_Key>;
using _Pred  = std::equal_to<_Value>;
using _Alloc = std::allocator<_Tp>;  // 使用STL自带的内存分配器
using _Tr    = std::__umap_traits<std::__cache_default<_Key, _Hash>::value>;
std::_Hashtable<_Key, _Tp, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing,std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, _Tr> rr();

 步骤一结果：_Hashtable正常，未报错，排除_Hashtable本身的问题。

验证步骤二：_Hashtable使用自定义的分配器。

using _Key   = int;
using _Value = int;
using _Tp    = std::pair<const _Key, _Value>;
using _Hash  = std::hash<_Key>;
using _Pred  = std::equal_to<_Value>;
using _Alloc = myAlloc::CAllocator<_Tp, MEM_MALLOC_TYPE, nullptr>;  // 使用自定义的内存分配器
using _Tr    = std::__umap_traits<std::__cache_default<_Key, _Hash>::value>;
std::_Hashtable<_Key, _Tp, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing,std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, _Tr> rr();

 步骤二结果：_Hashtable正常，未报错，排除_Hashtable使用自定义分配器的问题。

       b.封装容器本身使用自定义分配器导致的错误，验证该猜测的方法如下： 

验证步骤一：封装容器“CUnordered_set”使用STL自带的内存分配器。

// CUnordered_set<int, myAlloc::CAllocator<int, MEM_MALLOC_TYPE, nullptr> > myUnordered_set;
CUnordered_set<int, std::allocator<int> > myUnordered_set;

 步骤一结果：封装容器正常，未报错，排除封装内容中除内存分配器以外的问题。

验证步骤二：封装容器“CUnordered_set”使用自定义的内存分配器。

CUnordered_set<int, myAlloc::CAllocator<int, MEM_MALLOC_TYPE, nullptr> > myUnordered_set;
// CUnordered_set<int, std::allocator<int> > myUnordered_set;

 步骤二结果：封装容器报错。

        因此，错误原因在于自定义内存分配器的问题。通过与STL自带的分配器的比较发现，自定义分配器缺少一个默认的构造函数、一个默认的拷贝构造函数和一个泛化的拷贝构造函数。

constexpr CAllocator() noexcept {}
constexpr CAllocator(const CAllocator&) noexcept = default;
template <typename _Other> constexpr CAllocator(const CAllocator<_Other>&) noexcept {}

 其中，泛型构造函数的存在主要为了解决STL库的设计问题。容器模板的第二个参数一般是分配器allocator，它是有类型参数T的，在容器的实现中，STL库最初假设被创建出来的对象也是T类型的，但是对于一些容器来说，这个假设是不成立的，所以STL库使用偏特化来提供不同的构造函数，帮助allocalor从一种类型伪装成另一种类型的allocator，从而可以作为容器的模版参数，然后在内部转换成原本的allocator，这就是泛型构造函数的作用。在模板类型转换时，STL中提供了rebind接口来实现，它的作用就是对于类型T的分配器allocator<T>，可以根据相同的策略得到另外一个类型U的分配器allocator<U>，并且类型T和类型U在逻辑上是相关的，比如在_Hashtable中，数据的类型和结点hash_node的类型就是有联系的，它们对的内存分配策略是一样的。

       上面的过程属于重绑定机制，模板构造函数和rebind结构，其实是分别解决了两个不同的问题，一个针对实例，一个针对类型：a.模板构造函数所解决的问题是，如果容器有了allocator<T1>的实例，如何构造出allocator<T2>的实例；b.rebind所解决的问题是，如果一个容器得到了allocator<T1>类型，在内部如何能得到allocator<T2>类型。

       分配器的构造函数内部实际上没有做任何事，不需要初始化任何成员变量，所以任意两个malloc_allocator都是可互换的。如果a1和a2的类型都是malloc_allocator<int>，则可以自由地通过a1来allocate()内存，然后通过a2来deallocate()它，于是在自定义的分配器内部还需要定义比较操作“==”和“！=”以表明所有的malloc_allocator对象是否是等价的，如下所示。

template <typename _Ty, typename _Other> 
inline bool operator==(const CAllocator<_Ty>&, const CAllocator<_Other>&) noexcept {
    if(typeid(_Ty) == typeid(_Other)) { 
        return true; 
    }
    else { 
        return false; 
    }
}

template <typename _Ty, typename _Other> 
inline bool operator!=(const CAllocator<_Ty>&, const CAllocator<_Other>&) noexcept  {
    if(typeid(_Ty) != typeid(_Other)) {
        return true;
    }
    else {
        return false;
    }
}