FR: SparseSet support begin / end

Feature Requests
1

SparseSet support begin / end so I can iterate over it.

2

I opened a pull request for this: Add iterator for sparse set by FigBug · Pull Request #1497 · juce-framework/JUCE · GitHub

This has been requested in the past and Jules shot it down, but his reasons don’t make much sense. Iterators for SparseSet

Typically you’d use the class for very large sets where you have many repeated values

It’s a set, it can’t have repeated values

You’d also not necessarily have values stored at every possible index, so even the idea of iterating from zero is probably also not something that’d make sense for all cases.

It’s a set not an array, nothing is stored at indexes. You iterate contents, not indexes

But you don’t generally iterate selections.

I looked in the Projucer source, and selections are iterated with size and which is inefficient.

Sure, but also there’s the possibility of creating something like a SparseSet<float> , which would be impossible to iterate.

This already won’t work, size() and are meaningless for floats.

In a worst case scenario, where the SortedSet has lots of disjoint ranges, the performance of is terrible.

example:

    using clock = std::chrono::steady_clock;
    using seconds = std::chrono::duration<double>;

    juce::SparseSet<int> set;

    for (auto i = 0; i < 100000; i++)
        set.addRange({i * 2, i * 2 + 1});

    printf ("%d\n", set.getNumRanges());

    int64_t a = 0;
    int64_t b = 0;

    {
        const auto start_time = clock::now();

        for (const auto i : set)
            a += i;

        const auto end_time = clock::now();

        const auto elapsed_time = end_time - start_time;
        std::cout << std::chrono::duration_cast<seconds>(elapsed_time).count() << " seconds\n";
    }

    {
        const auto start_time = clock::now();

        for (auto i = 0; i < set.size(); i++)
            b += set[i];

        const auto end_time = clock::now();

        const auto elapsed_time = end_time - start_time;
        std::cout << std::chrono::duration_cast<seconds>(elapsed_time).count() << "seconds \n";
    }

    printf("%lld %lld\n", a, b);

release build on M1, iterator takes 0.000341167 seconds for 100,000 items
takes 3.0997 seconds

1 Like