Get the number of duplicated elements in a set-CodePudding

So a set doesn't allow duplicates, but is there a way, or another data structure, that can allow me to get the number of repeated elements even though they have been removed?. Let me explain myself better anyways.

Lets say I'm giveng this input:

[1, 2, 2, 3, 2, 5, 3]

If I put it in a set, it will end up like this:

[1, 2, 3, 5]

Which is what I want, but how can I know that there were three 2s before they were removed? Isn't this related to those data structure with "buckets" or something?

Basically I'd like the output to be something like this:

[1, 2, 3, 5]
 |  |  |  |
[1, 3, 2, 1]

With the bottom array being the number of duplicates of each element on the top array.

CodePudding user response：

You can use a std::map to count the frequency of the items.

For example:

int arr[] = {1, 2, 2, 3, 2, 5, 3};

std::map<int, int> count;

for (int i = 0; i < 7; i  ) {
    count[arr[i]]  ;
}

for (auto& [element, frequency] : count) {
    std::cout << element << " : " << frequency << endl;
}

The output would be something like this:

CodePudding user response：

You gave the answer yourself: if suffices to keep counts in correspondence to the unique elements. Hence a compact data structure is the list of the unique elements paired with the list of counts in the same order.

Now how this is obtained depends on how you plan to remove the duplicates and the kind of access desired. One way is to sort the initial list, purge the duplicates at the same time that you count them and fill the list of counts. Another way is to use a map with the list elements as keys and associate them with a count. Whether you keep the map or fill new lists is your choice.