I wrote a memory allocator to use with standard containers. However, every time I try to remove an element from a std::list, the program crashes at the line l.remove(elt).
I spent time investigating until I tried using malloc() and free() just to see what happens, and yes it crashed, too.
This is a simple code that crashes:
#include <limits>
#include <list>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <unordered_map>
template<typename T>
struct IngaAllocator
{
typedef T value_type;
IngaAllocator() {};
~IngaAllocator() {};
template<typename U>
constexpr IngaAllocator(IngaAllocator<U> const &) noexcept {}
IngaAllocator(IngaAllocator const &){}
T * address(T& x) const {return &x;};
const T * address(const T& x) const {return &x;};
[[nodiscard]] T * allocate(std::size_t n)
{
if(n > std::numeric_limits<std::size_t>::max() / sizeof(T))
{
throw std::bad_array_new_length();
}
return static_cast<T*>(malloc(sizeof(T) * n));
}
void deallocate(T * p, std::size_t n) noexcept
{
free((void *)p);
}
template<typename U, typename... Args>
void construct(U* p, Args&&... args) noexcept
{
new(static_cast<void *>(p))U(std::forward<Args>(args)...);
}
template<typename U>
void destroy(U* p)
{
p->~U();
}
inline bool operator == (IngaAllocator const &a) {return this == &a;}
inline bool operator != (IngaAllocator const &a) {return !operator == (a);}
};
template<class _Ty, class _Ax = IngaAllocator<_Ty>>
class List : public std::list<_Ty, _Ax>{};
template<class T, class U, class _Ax = IngaAllocator<T>>
class UnorderedMap : public std::unordered_map<T, U, std::hash<T>,
std::equal_to<T>, IngaAllocator<std::pair<const T, U>>>
{
};
int main(int argc, char **argv)
{
UnorderedMap<std::string, int> map;
map["one"] = 1;
for(auto & it: map)
{
fprintf(stderr, "%s : %d\n", it.first.c_str(), it.second);
}
auto it = map.find("one");
map.erase(it); //NO PROBLEM
for(auto & it: map)
{
fprintf(stderr, "%s : %d\n", it.first.c_str(), it.second);
} //WILL PRINT NOTHING
List<int> l;
l.push_back(1);
l.push_back(2);
for(auto au : l)
{
fprintf(stderr, "%d\n", au);
}
l.remove(2); //CRASHES HERE
for(auto au : l)
{
fprintf(stderr, "%d\n", au);
}
return 0;
}
So, even with malloc()/free(), it crashes.
What am I doing wrong? For IngaAllocator, I just find this in numerous places where the codes are basically identical. So I am totally lost about why it crashes, and how to fix it, if possible.
EDIT:
I tried with unordered_map and there is no crash when calling erase().
Elaborating on my comment: Your operator== is incorrect.
If you look at Allocator on cppreference, or allocator.requirements in the C++ standard, the rule for operator== is that two allocator objects shall compare equal only if memory allocated by one can safely be deallocated by the other. Moreover, one of the requirements of the copy constructor and the copy assignment operator is that when you copy one allocator object to another, then afterward they shall compare equal.
Your operator== simply compares the addresses of the two objects, so it does not satisfy this condition. If you were to do
IngaAllocator<int> a;
IngaAllocator<int> b(a); // copy constructor
then even though the copy constructor does nothing, a and b are still two different objects with different addresses, so a == b would return false.
This is why your program crashes. With GNU libstdc++, std::list::remove is implemented by creating a temporary list named __to_destroy and using splice() to splice into it all the elements to be removed from the original list l. The temporary list __to_destroy is constructed by copying the allocator of l.
In order to splice two lists, it's required that their allocators compare equal; this makes sense, because splice just moves nodes from one list to the other, and so nodes allocated with the allocator of the list l will be deallocated with the allocator of __to_destroy. As a check, the library actually verifies that they compare equal. When this fails, abort() is called.
Since your allocator simply calls malloc and free, any memory allocated by any instance of IngaAllocator<T> can be safely deallocated by any other instance. Therefore, your operator== should simply return true;, and likewise operator!= can simply return false;.
Of course, in a less trivial allocator, the comparison might need to involve actual tests; but you'd still need to ensure that copying preserves equality, as noted above.