CODEWITHSUNDEEP
c++
wolve80
wolve80

Reputation: 105

dynamic int * arrays as key for C++ map

I have some dynamic int * arrays that I would like to use as keys for an unordered_map. I'm a bit unclear on how I should declare the key type so it would actually be the value of the entire array.

Also, to deallocate the memory for the arrays, do I use map.clear()?

Example:

unordered_map<??, int> frequency;

while (some_condition) {

  int *my_array = new int[size];
  putSomeValuesToArray(my_array);
  frequency[my_array]++;
}

// to deallocate memory for the arrays in frequency?

Upvotes: 2

Views: 3196

Answers (3)

Luc Danton
Luc Danton

Reputation: 35449

You won't be able to stick int* as key inside a std::map and still be able to retrieve elements 'by value'. The reason for that is a single int* only provides the start of an array, you need the end too to compute anything (equivalently and more C-like, the length). In other words, int* does not an array (dynamic or otherwise) make; in this context it's an iterator to the start of a sequence.

You can use std::pair<int*, int*> but it should only be used for non-owning 'views' of data. That is, if you manually manage memory with a std::map<std::pair<int*, int*>, int> you'll end up with a headache. One possibility is using a smart-pointer: std::pair<std::unique_ptr<int[]>, int*>. But as others have recommended, just use std::vector as it is still compatible with C-like interfaces that deal with int*. Plus a const std::pair<std::unique_ptr<int>, int*> still allows you to scribble the memory, which can mess up the ordering of the map and ends you up in trouble.

A final blow to using int* or std::unique_ptr<int[]> is that you would need to provide the strict weak ordering that std::map requires, whereas std::vector<int> comes with an appropriate operator<. On the other hand, you need to provide a hash for both if you settle instead on std::unordered_map. For what it's worth, a simple functor that uses std::lexicographical_compare (same semantics as std::vector comparison):

struct compare {
    typedef std::pair<std::unique_ptr<int[]>, int*> value_type;
    bool
    operator()(value_type const& lhs, value_type const& rhs) const
    {
        return std::lexicographical_compare(lhs.first.get(), lhs.second
                                           , rhs.first.get(), rhs.second);
    }
};

Then you can use std::map<std::pair<std::unique_ptr<int[]>, int*>, int, compare>.

Upvotes: 0

iammilind
iammilind

Reputation: 69988

If you meant,

int *p = new int[size];

and you want to make p as a key, then for you better choice will be to use std::set().

Also, you cannot simply clear() it; you may want to delete[] each element before, to avoid memory leak. If you don't want to individually delete[] it then, you can use shared_ptr (or other smart pointers) which will do the job for you.

Upvotes: 1

Matthieu M.
Matthieu M.

Reputation: 299780

Important: If you use a dynamically allocated object in a STL Container, then to deallocate the memory you need to walk the container and call delete (or delete[]) explicitly.

I would strongly suggest moving from int* to std::vector<int>, you would not have the issue of memory ownership any longer then.

In order to declare a key, pass the type as the template parameter:

std::unordered_map<int*, Foo>
std::unordered_map<std::vector<int>, Foo>

Of course, for unordered_map you are likely going to need a specific Hash parameter, which derives a hash value from the Key you pass.

Upvotes: 4

Related Questions