5
\$\begingroup\$

For some of the algorithms that I am implementing it turned out to be useful storing ids in order to iterate on objects, while also avoiding having to think about reallocation and invalidation of pointers.

It turned out that being able to iterate on sets of ids is something which is quite useful in general (at least to me): iterating over subsets, filtering, etc. I have made a relatively simple iterable that took care of the details for me, and that I could also use with STL algorithms.

I'm trying to avoid having these classes become too bulky, so I haven't tried to add all iterator methods I could have; for example, the iterator implemented could be a random-access one, but it has nowhere near the amount of stuff it should have in order to be classified as one. At the same time I'm open to adding functionality if it obviously missing and doesn't have a high line count.

I'm looking for any kind of comments: naming, API, performance, etc. Thanks!

#include <utility>
#include <type_traits>

/**
 * @brief This class is an iterable construct on a list of ids on a given container.
 *
 * This class allows to iterate over a given subset of ids on the input
 * container as if they were laid out continuously in a single object.
 *
 * Both ids and items must be stored in containers accessible via
 * square-brakets and ids.
 *
 * By default the iterable will copy the input ids and own them. If this is not
 * desirable (maybe one wants to change the ids over time without being forced
 * to copy them multiple times), the class accepts a pointer to an ids
 * container, and it will automatically store a single reference to it, rather
 * than doing a copy.
 *
 * @tparam IdsContainer The type of the input ids in the constructor.
 * @tparam Container The type of the container to be iterated on.
 */
template <typename IdsContainer, typename Container>
class SubsetIterable {
    public:
        template <typename T>
        class SubsetIterator;

        using value_type     = typename Container::value_type;
        using iterator       = SubsetIterator<typename copy_const<value_type, Container>::type>;
        using const_iterator = SubsetIterator<const value_type>;

        /**
         * @brief The type used to contain the ids in the iterable.
         *
         * This is a constant copy of the input ids if we own them, and
         * otherwise a const reference if we don't (and thus they can change).
         */
        static constexpr bool OwnsIds = !std::is_pointer_v<IdsContainer>;
        using IdsStorage  = typename std::conditional<OwnsIds, 
                                         const IdsContainer, 
                                         const std::remove_pointer_t<IdsContainer> &
                                     >::type;

        /**
         * @brief Basic constructor for owning iterable.
         *
         * This constructor stores a copy of all the ids and a reference to the
         * container over which to iterate.
         *
         * This class and its iterators do *NOT* perform any bound checking on
         * the size of the container and the input ids, neither at construction
         * nor during operation.
         *
         * This class and its iterators *WILL* be invalidated if the item
         * container is destroyed.
         *
         * @param ids The ids to iterate over.
         * @param items The items container.
         */
        template <bool Tmp = OwnsIds, typename std::enable_if_t<Tmp, int> = 0>
        SubsetIterable(IdsContainer ids, Container & items) : ids_(std::move(ids)), items_(items) {}

        /**
         * @brief Basic constructor for non-owning iterable.
         *
         * This constructor stores the pointer to the ids and items over which
         * to iterate.
         *
         * This class and its iterators do *NOT* perform any bound checking on
         * the size of the container and the input ids, neither at construction
         * nor during operation.
         *
         * This class and its iterators *WILL* be invalidated if the ids
         * container or the item container are destroyed.
         *
         * If the ids change, all previously generated iterators are invalidated.
         *
         * @param ids The ids to iterate over.
         * @param items The items container.
         */
        template <bool Tmp = OwnsIds, typename std::enable_if_t<!Tmp, int> = 0>
        SubsetIterable(IdsContainer ids, Container & items) : ids_(*ids), items_(items) {}

        /**
         * @brief This function returns an iterator to the beginning of this filtered range.
         */
        iterator begin() { return ids_.size() ? iterator(this) : iterator(); }

        /**
         * @brief This function returns a const_iterator to the beginning of this filtered range.
         */
        const_iterator begin() const { return cbegin(); }

        /**
         * @brief This function returns a const_iterator to the beginning of this filtered range.
         */
        const_iterator cbegin() const { return ids_.size() ? const_iterator(this) : const_iterator(); }

        /**
         * @brief This function returns an iterator to the end of this filtered range.
         */
        iterator end() { return iterator(); };

        /**
         * @brief This function returns a const_iterator to the end of this filtered range.
         */
        const_iterator end() const { return cend(); }

        /**
         * @brief This function returns a const_iterator to the end of this filtered range.
         */
        const_iterator cend() const { return const_iterator(); }

        /**
         * @brief This function returns the size of the range covered.
         */
        size_t size() const { return ids_.size(); }

    private:
        friend iterator;
        friend const_iterator;

        // Const reference if non-owning, const value otherwise.
        IdsStorage ids_;
        Container & items_;
};

/**
 * @brief This class is a simple iterator to iterate over filtered values held in a SubsetIterable.
 */
template <typename IdsContainer, typename Container>
template <typename T>
class SubsetIterable<IdsContainer, Container>::SubsetIterator {
    private:
        // The type of the SubsetIterable that defined this instance of the class
        using Owner = typename copy_const<SubsetIterable<IdsContainer, Container>, T>::type;
    public:
        using value_type = T;

        /**
         * @brief Basic constructor for end iterators.
         */
        SubsetIterator() : currentId_(0), parent_(nullptr) {}

        /**
         * @brief Basic constructor for begin iterators.
         *
         * @param parent The parent iterable object holding ids and values.
         */
        SubsetIterator(Owner * parent) : currentId_(0), parent_(parent) {}

        value_type& operator*()  { return parent_->items_[parent_->ids_[currentId_]]; }
        value_type* operator->() { return &(operator*()); }

        /**
         * @brief This function returns the equivalent item id of this iterator in its container.
         */
        size_t toContainerId() const { return parent_->ids_[currentId_]; }

        void operator++() {
            ++currentId_;
            if ( currentId_ >= parent_->ids_.size() ) {
                currentId_ = 0;
                parent_ = nullptr;
            }
        }

        bool operator==(const SubsetIterator & other) {
            if ( parent_ == other.parent_ ) return currentId_ == other.currentId_;
            return false;
        }
        bool operator!=(const SubsetIterator & other) { return !(*this == other); }

    private:
        size_t currentId_;
        Owner * parent_;
};

Example usage:

int main() {
    std::vector<std::string> test{"abc", "cde", "lol", "lal", "foo", "baz"};
    std::vector<size_t> ids{0,3,4,5};

    SubsetIterable itt(ids, test);
    for (const auto & s : itt)
        std::cout << s << '\n';
    std::cout << '\n';

    SubsetIterable itt2(&ids, test);
    for (const auto & s : itt2)
        std::cout << s << '\n';
    std::cout << '\n';

    ids[0] = 1;
    for (const auto & s : itt2)
        std::cout << s << '\n';
    std::cout << '\n';
    return 0;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Did you forget to include the header files? \$\endgroup\$ – yuri Aug 2 '18 at 19:33
  • \$\begingroup\$ Also seems to be missing using std::size_t; somewhere. \$\endgroup\$ – Toby Speight Aug 3 '18 at 8:08
  • \$\begingroup\$ I've added the needed headers, apologize for the mistake. I've never had to use the using directive with size_t though, it always compile like this. Is it a mistake? \$\endgroup\$ – Svalorzen Aug 3 '18 at 9:01
  • \$\begingroup\$ @Svalorzen What compiler do you use? There might be underwater magic going on. \$\endgroup\$ – Mast Aug 3 '18 at 9:08
  • 1
    \$\begingroup\$ I'm not saying your compiler does anything wrong, but it does explain why it's not required to include it as indicated in this comment. \$\endgroup\$ – Mast Aug 3 '18 at 9:31
4
\$\begingroup\$
  1. You should use default initialization for your members, see 1

        SubsetIterator() = default;
    ...
    private:
        size_t currentId_{0};
        Owner * parent_{nullptr};
    
  2. Your SubsetIterator could use constexpr all around, as you only hold literal types.

  3. You should changing the size_t of the SubsetIterator to a template argument size_type and pass that from the container. It might be that your class is used by a container that has a different size_type thatn size_t

  4. It is slightly unexpected that your operator++ invalidates at the end of the range. There is not even a warning, you silently accept every bogus input.

  5. I dont get the template arguments of your constructor

    template <bool Tmp = OwnsIds, typename std::enable_if_t<!Tmp, int> = 0>
    SubsetIterable(IdsContainer ids, Container & items) : ids_(*ids), items_(items) {}
    

    Why default to type int and = 0 ? There is no need for that or maybe am just not seeing it.

    template <bool Tmp = OwnsIds, typename std::enable_if_t<!Tmp>>
    SubsetIterable(IdsContainer ids, Container & items) : ids_(*ids), items_(items) {}
    

    Generally i would say that your owning constructor should take an rvalue rference rather than just stealing the range. That would both be much more obvious and let the compiler do its job.

\$\endgroup\$
  • \$\begingroup\$ What should I do about 4? For 5, unfortunately your suggestion does not compile. I bumped my head against it too while I was writing it. For the owning constructor, note that I am copying the input, and then moving it into my member variable. I don't steal ;) \$\endgroup\$ – Svalorzen Aug 3 '18 at 9:03
3
\$\begingroup\$

SubsetIterable isn't really clear in what it's trying to accomplish (props for the documentation though!). We're mapping indices to a range, so IndexMap or SubscriptMap may be better.

Consider making SubsetIterator its own class so that it can be used with existing algorithms and structures.

auto elements = std::vector(SubsetIterator{indices.begin(), container}, 
                            SubsetIterator{indices.end()});
std::copy(SubsetIterator{indices.begin(), container}, 
          SubsetIterator{indices.end()},
          ostream_joiner{std::cout, ", "});

That would also require fulfilling the iterator requirements (C++17 § 22.2). Add the missing type information (C++17 § 22.2.1.5). The pre-increment operator (Iterator::operator++()) is required to return a reference (Iterator&) (C++17 § 22.2.2.2.2).

A better idea is to use existing tools. You have a range of indices and you want index accesses into random-access containers. In C++, we use std::transform for such operations. For a range-based solution, see boost::adaptors::transformed, iter::imap, or soon™ std::ranges::action::transformed (Ranges proposal).

auto by_subscript = [](const auto& obj) {
    static_assert(has_subscript_op_v<decltype(obj)>);
    return [&obj](auto index) {
        return obj[index];
    };
};

int main() {
    std::vector<std::string> strs{"abc", "cde", "lol", "lal", "foo", "baz"};
    std::vector<size_t> indices{0,3,4,5};

    for (auto&& str : indices | iter::imap(by_subscript(strs)) {
        std::cout << str << '\n';
    }

    std::copy(boost::make_transform_iterator(indices.cbegin(), by_subscript(strs)),
              boost::make_transform_iterator(indices.cend(), by_subscript(strs)),
              std::ostream_iterator{std::cout, "\n"});
}

You should either document or statically check that the container be at least random accessible (requires subscript operator).

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions! I know the name isn't the best, your suggestions are good, although I'm a bit worried with using the term Map since it already kind of has a meaning. But maybe it is good anyway. For the existing tools, I have a couple of problems with those: one is that they tend to make code a bit harder to follow (for novices too), but also I tend to kind of lose track of exactly how costly all these abstractions end up to be, so I'm a bit afraid to use them. The code is for a library so I don't know in advance how it's going to be used - which makes profiling harder. \$\endgroup\$ – Svalorzen Aug 3 '18 at 9:13
  • \$\begingroup\$ Could also call it a SubscriptMapper or SubscriptAccessor or SubscriptTransformer if you want to be C++ish. \$\endgroup\$ – Snowhawk Aug 3 '18 at 9:15
  • \$\begingroup\$ Also, what do you mean with "making SubsetIterator its own class"? I've defined inside the SubsetIterable mostly because the iterator depends so much on the internals that it seemed difficult it could be reused. You think maybe I shouldn't care? \$\endgroup\$ – Svalorzen Aug 3 '18 at 9:20
  • \$\begingroup\$ The iterator is dependent on the existence of its parent class. Instead, have the parent class create standalone instances of its iterators. That standalone iterator would have a reference to the data container and an iterator into the indexed container. Break the dependence so your iterator can be constructed independently and be useful with the current standard api (passing iterators to methods and standalone functions). \$\endgroup\$ – Snowhawk Aug 3 '18 at 9:25
  • 1
    \$\begingroup\$ You have to construct an instance of the parent class first before you can use the iterators though. That's fine, but I'm just suggesting that the dependence isn't necessary. Object lifetimes will always be an issue, even for your parent class. \$\endgroup\$ – Snowhawk Aug 3 '18 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.