Variable Sized Arrays¶
Title: Variable Sized Arrays
Link: https://www.hackerrank.com/challenges/variable-sized-arrays/problem
Direct Solution with Vectors¶
We are being challenged to take a number n of arrays and then take q pairs of integers, i and j, that will be used to search first over the list of n arrays with i and then the element j in the referenced array.
Let us spare us using dynamically allocated arrays with new[] and then deallocating them with delete[] before ending the program (or having used an std::unique_ptr) and go directly for a manual solution featuring std::vector.
#include <iostream> // std::cin, std::cout
#include <vector> // std::vector
int
main(int, char *[]) {
// problem parameters (const and from input)
int n, q; // number of arrays, number of queries
std::cin >> n >> q;
// define matrix, create and gather array elements
auto vmatrix = std::vector<std::vector<int>>{};
for(int k; n--;) {
std::cin >> k;
auto &vec = *vmatrix.emplace(vmatrix.end());
for(int ki; k--; vec.push_back(ki))
std::cin >> ki;
}
// run the queries
for(int i, j; q--;std::cout << vmatrix[i][j] << std::endl)
std::cin >> i >> j;
return 0;
}
As we already know we need a lot of std::cin >> varname boilerplate after having defined the variables. The only novelty here is that we use std::vector::emplace, to let the inner vectors be constructed for us.
Since we get an iterator to where the new std::vector<int> has been positioned, we keep a reference and using std::vector::push_back is straightforward.
To get the code in as few lines as possible, we use the “dirty” trick of defining the input variables in the for loop and then performing the storage or output operations in the final statement of the loop.
Iterator-Based Solution¶
Converting to an iterator based solution is easy. Even better, the “real” solution takes less lines if we take into account the two extra #include files we need. We do, of course, apply the same “dirty” for trick to save some lines.
Because the vector is being created for us, we can use the reference we keep to std::copy_n the n elements for each instance with std::back_inserter. We already used in a previous challenge in which we also worked with arrays. Let us remark the fact, that by using it we are in fact also using an iterator. It is created in the background for us and takes advantage of the std::vector::push_back method.
Prototyping A Container¶
Given that we have a container, std::vector, holding another container, also an std::vector, it seems like natural that we try to prototype a container to do the work.
To save us some work later during the refinement phase, let us already add some SFINAE checks. To do so we are going to resort to one of the oldest technologies in C++ (coming from the C times), the preprocessor. Yes, that macro machinery that evoke the 80s.
// Macro for trait definitions
#define DEFINE_HAS_METHOD(method) \
template<typename, typename = void> \
constexpr bool has_##method##_v = false; \
template<typename T> \
constexpr bool has_##method##_v<T,\
std::void_t<decltype(std::declval<T>().method())>> = true;
// Macro for trait definitions where a value_type arg is expected
#define DEFINE_HAS_METHOD_ARG(method) \
template<typename, typename = void> \
constexpr bool has_##method##_v = false; \
template<typename T> \
constexpr bool has_##method##_v<T, \
std::void_t<decltype(std::declval<T>().method(\
std::declval<typename T::value_type>()))>> = true;
DEFINE_HAS_METHOD(begin)
DEFINE_HAS_METHOD(end)
DEFINE_HAS_METHOD(rbegin)
DEFINE_HAS_METHOD(rend)
DEFINE_HAS_METHOD_ARG(push_back)
DEFINE_HAS_METHOD_ARG(push_front)
Looking at that code the reason is obvious: “DRY” (Don't Repeat Yourself). With the DEFINE_HAS_METHOD and DEFINE_HAS_METHOD_ARG we avoid almost endlessly repeating the same boilerplate to look for methods in classes. Although not shown above, we also have a has_insert_v checker. This one looks for a method with two arguments and the macro would have taken exactly the same place as the only use we make of it.
All those will be combined in a two extra checks to see if the template parameters for our container prototype are supported.
// is_container_v
template<typename C>
constexpr bool is_container_v =
(has_push_back_v<C> and has_begin_v<C> and has_end_v<C>) or
(has_push_front_v<C> and has_rbegin_v<C> and has_rend_v<C>) or
(has_insert_v<C> and has_begin_v<C> and has_end_v<C>);
// enable_if
template <typename ContOut, typename ContIn>
using enable_if_containers =
std::enable_if_t<is_container_v<ContOut> and is_container_v<ContIn>>;
// solution class
template <
template <typename> class ContOut = std::vector,
template <typename> class ContIn = std::vector,
typename T = int,
typename = enable_if_containers<ContOut<ContIn<T>>, ContIn<T>>
>
class VariableSizedArrays {
using Inner = ContIn<T>; // inner array
using Outer = ContOut<Inner>; // outer array
VariableSizedArrays will also use the checks in combination with if constexpr to select the appropriate methods at compile time, to support our solution. For example, a get_inserter method will choose if std::back_inserter is the one to use or std::front_inserter is the one to go for.
template <typename C>
auto get_inserter(C &c) const {
// constexpr chooses the right iterator inserter for C
if constexpr (has_push_front_v<C>)
return std::front_inserter(c);
else if constexpr (has_push_back_v<C>)
return std::back_inserter(c);
else if constexpr (has_insert_v<C>)
return std::inserter(c, c.end());
// Unreachable SFINAE has checked before
}
This method works for the selection of the outer array and the inner arrays, the ones holding the values. And because we have used different methods for the insertion and that means a different positioning, we also need to use if constexpr to select the method taking us to a given position, the query, in the outer and inner arrays.
template<typename C>
auto get_iterator(const C &c, size_t s) const {
// constexpr chooses the right iterator to start with
if constexpr (has_push_front_v<C>)
return std::next(c.rbegin(), s);
else if constexpr (has_push_back_v<C> or has_insert_v<C>)
return std::next(c.begin(), s);
// Unreachable SFINAE has checked before
}
Both methods are used to implement the read_array and query methods, the ones doing the work for the outside world, i.e., for main.
template <typename I>
auto read_array(I &in, size_t n) {
// read n values of type "S" from "in" to a container Inner
// add the container to our outer container
auto inner = Inner{};
std::copy_n(in, n, get_inserter(inner));
*get_inserter(m_c)++ = inner;
}
auto query(size_t j, size_t i) const {
return *get_iterator(*get_iterator(m_c, i), j);
}
The final solution offers a CASE1 option (build and test with make 03 case1) that uses std::deque for both the inner and outer arrays, selecting std::deque::push_front and std::front_inserter for the implementation of the private methods supporting the external interface.
#include <algorithm> // std::cin, std::cout
#include <deque> // std::deque
#include <iostream> // std::cin, std::cout
#include <iterator> // std::istream, std::ostream_iterator, std::inserter
#include <vector> // std::vector
#include <type_traits> // std::void_t, std::enable_if ...
// Macro for trait definitions
#define DEFINE_HAS_METHOD(method) \
template<typename, typename = void> \
constexpr bool has_##method##_v = false; \
template<typename T> \
constexpr bool has_##method##_v<T,\
std::void_t<decltype(std::declval<T>().method())>> = true;
// Macro for trait definitions where a value_type arg is expected
#define DEFINE_HAS_METHOD_ARG(method) \
template<typename, typename = void> \
constexpr bool has_##method##_v = false; \
template<typename T> \
constexpr bool has_##method##_v<T, \
std::void_t<decltype(std::declval<T>().method(\
std::declval<typename T::value_type>()))>> = true;
DEFINE_HAS_METHOD(begin)
DEFINE_HAS_METHOD(end)
DEFINE_HAS_METHOD(rbegin)
DEFINE_HAS_METHOD(rend)
DEFINE_HAS_METHOD_ARG(push_back)
DEFINE_HAS_METHOD_ARG(push_front)
// has_insert
template <typename, typename = void>
constexpr bool has_insert_v = false;
template <typename C>
constexpr bool has_insert_v<
C,
std::void_t<
decltype(
std::declval<C>().insert(
std::declval<typename C::const_iterator>(),
std::declval<typename C::value_type>()))>> = true;
// is_container_v
template<typename C>
constexpr bool is_container_v =
(has_push_back_v<C> and has_begin_v<C> and has_end_v<C>) or
(has_push_front_v<C> and has_rbegin_v<C> and has_rend_v<C>) or
(has_insert_v<C> and has_begin_v<C> and has_end_v<C>);
// enable_if
template <typename ContOut, typename ContIn>
using enable_if_containers =
std::enable_if_t<is_container_v<ContOut> and is_container_v<ContIn>>;
// solution class
template <
template <typename> class ContOut = std::vector,
template <typename> class ContIn = std::vector,
typename T = int,
typename = enable_if_containers<ContOut<ContIn<T>>, ContIn<T>>
>
class VariableSizedArrays {
using Inner = ContIn<T>; // inner array
using Outer = ContOut<Inner>; // outer array
Outer m_c; // outer container, keeps the other arrays in pace
template<typename C>
auto get_iterator(const C &c, size_t s) const {
// constexpr chooses the right iterator to start with
if constexpr (has_push_front_v<C>)
return std::next(c.rbegin(), s);
else if constexpr (has_push_back_v<C> or has_insert_v<C>)
return std::next(c.begin(), s);
// Unreachable SFINAE has checked before
}
template <typename C>
auto get_inserter(C &c) const {
// constexpr chooses the right iterator inserter for C
if constexpr (has_push_front_v<C>)
return std::front_inserter(c);
else if constexpr (has_push_back_v<C>)
return std::back_inserter(c);
else if constexpr (has_insert_v<C>)
return std::inserter(c, c.end());
// Unreachable SFINAE has checked before
}
public:
template <typename I>
auto read_array(I &in, size_t n) {
// read n values of type "S" from "in" to a container Inner
// add the container to our outer container
auto inner = Inner{};
std::copy_n(in, n, get_inserter(inner));
*get_inserter(m_c)++ = inner;
}
auto query(size_t j, size_t i) const {
return *get_iterator(*get_iterator(m_c, i), j);
}
};
// main solution
int
main(int, char *[]) {
// prepare iterators for input/output
auto in = std::istream_iterator<int>{std::cin};
auto out = std::ostream_iterator<int>{std::cout, "\n"};
// problem parameters (const and from input)
auto n = *in++, q = *in++; // number of arrays, number of queries
// define matrix, create and gather array elements
#ifdef CASE1
auto vsa = VariableSizedArrays<std::deque, std::deque>{};
#else
auto vsa = VariableSizedArrays{};
#endif
for(; n--; in++) // resync "in" iterator after copy action
vsa.read_array(in, *in++); // *in++ = k, number of elements
// run the queries
while(q--)
*out++ = vsa.query(*in++, *in++);
return 0;
}
An (almost) real container¶
The container prototype we crafted above does the job, but it feels awkward. It has no begin, no end and no push_xxx methods and that means we have to resort to handmade read_array and query methods.
Let us therefore implement those container methods to have an (almost) real container. begin and end will have to return an iterator and that means we have to also code one inside the container class.
And Houston ... we have a problem. Iterators are supposed to work linearly and the distance from one point to another must be linear because it has to be integer-like. It is in the standard. Nevertheless, we can work around the “limitations” by tagging our iterator as n RandomAccessIterator.
In the case of other iterator types, moving the iterator forward or backwards is done in this fashion. Going forward, for example:
When distance reaches 0, the iterator is no longer ++ed. The iterator can only operated inside the increment operator without actually knowing what the value of distance is.
But for a RandomAccessIterator the movement works like this:
The iterator itself has to move using the distance. That is exactly what we are going to “abuse” by creating a 2-D distance, that will always take us from the beginning of the container to the position the query wants resolved.
Here is our Distance/Position implementation
struct ReIterator {
using pos_t = std::pair<int, int>;
template <typename Pair>
struct PosT {
typename Pair::first_type first;
typename Pair::second_type second;
PosT(const Pair& pos) : first{pos.first}, second{pos.second} {};
template <typename P>
auto operator ==(const P &) const { return false; }
auto operator ==(const Pair &p) const {
return p.first == first and p.second == second;
}
};
using Pos = PosT<pos_t>;
Ideally we would have used an std::pair<int, int> directly, but reality killed the cat. The library implementation used by GCC relies on the fact that the distance for iterators has to be integer-like and makes a comparison with 1 and -1. Hence the need to wrap our std:pair<int, int> to provide the proper comparison operator and avoid chaos during compilation.
That distance definition will be used in the operator += to move to the desired position. The implementation does not consider the current position: it does simply take the given position as the new point the iterator has moved to. That position will later be used when the iterator is dereferenced with the operator *.
auto &operator +=(const Pos &pos) {
m_pos = pos;
return *this;
}
constexpr auto operator *() const {
using InnerT = typename std::iterator_traits<I>::value_type;
auto inner = *std::next(m_it, m_pos.first);
// constexpr chooses the right iterator to start with
if constexpr (has_push_front_v<InnerT>)
return *std::next(inner.rbegin(), m_pos.second);
else if constexpr (has_push_back_v<InnerT> or has_insert_v<InnerT>)
return *std::next(inner.begin(), m_pos.second);
// Unreachable SFINAE has checked before
}
As it can be seen, the dereferencing uses a real iterator passed during construction, m_it to find first the inner container and then move into the final position within it.
Our container chooses if the iterator from which the position is calculated, will be begin or rbegin from the outer array container.
constexpr auto get_begin_end(bool begin) const {
// constexpr chooses the right iterator to start with
if constexpr (has_push_front_v<Outer>)
return begin ? ReIterator(m_c.rbegin()) : ReIterator(m_c.rend());
else if constexpr (has_push_back_v<Outer> or has_insert_v<Outer>)
return begin ? ReIterator(m_c.begin()) : ReIterator(m_c.end());
// Unreachable SFINAE has checked before
}
public:
using value_type = T; // needed to support std::back_inserter
auto begin() const { return get_begin_end(true); }
auto end() const { return get_begin_end(false); }
To complete the container, we reuse the previous get_inserter to implement the push_back method.
constexpr auto push_back(const T &t) {
if constexpr (has_push_front_v<Outer>)
return *get_inserter(*(--m_c.rend())) = t;
else if constexpr (has_push_back_v<Outer> or has_insert_v<Outer>)
return *get_inserter(*(--m_c.end())) = t;
// Unreachable SFINAE has checked before
}
With the container in place, we can now use the standard library tools to store the input arrays and to execute the queries. Creating an array with the standard template parameters is now a matter of directly applying std::copy_n.
#else
auto vsa = VariableSizedArrays{};
#endif
for(; n--; in++) // resync "in" iterator after copy action
std::copy_n(in, *in++, std::back_inserter(++vsa)); // *in++ = k
And executing the query a matter of moving the begin iterator with a 2-D distance, i.e., a pair of integers to the required destination and dereferencing the resulting iterator.
auto &&vsa = variable_sized_arrays(in, n); // get matrix
while(in != in_last) // run queries until input is exhausted
*out++ = *std::next(vsa.begin(), {{*in++, *in++}}); // *in++ => i, j
Summary¶
As in previous examples we have iterated from a straightforward solution to an iterator based solution and we have moved a step further by implementing a container that does the iteration for us. The container uses a 2-D distance to reach the destination desired by the query. We have even removed the limitation on the number of queries by testing for the end of input before we stop reading values.
Here is the complete code.
#include <algorithm> // std::cin, std::cout
#include <deque> // std::deque
#include <iostream> // std::cin, std::cout
#include <iterator> // std::istream, std::ostream_iterator, std::inserter
#include <vector> // std::vector
#include <type_traits> // std::void_t, std::enable_if ...
// Macro for trait definitions
#define DEFINE_HAS_METHOD(method) \
template<typename, typename = void> \
constexpr bool has_##method##_v = false; \
template<typename T> \
constexpr bool has_##method##_v<T,\
std::void_t<decltype(std::declval<T>().method())>> = true;
// Macro for trait definitions where a value_type arg is expected
#define DEFINE_HAS_METHOD_ARG(method) \
template<typename, typename = void> \
constexpr bool has_##method##_v = false; \
template<typename T> \
constexpr bool has_##method##_v<T, \
std::void_t<decltype(std::declval<T>().method(\
std::declval<typename T::value_type>()))>> = true;
DEFINE_HAS_METHOD(begin)
DEFINE_HAS_METHOD(end)
DEFINE_HAS_METHOD(rbegin)
DEFINE_HAS_METHOD(rend)
DEFINE_HAS_METHOD_ARG(push_back)
DEFINE_HAS_METHOD_ARG(push_front)
// has_insert
template <typename, typename = void>
constexpr bool has_insert_v = false;
template <typename C>
constexpr bool has_insert_v<
C,
std::void_t<
decltype(
std::declval<C>().insert(
std::declval<typename C::const_iterator>(),
std::declval<typename C::value_type>()))>> = true;
// is_container_v
template<typename C>
constexpr bool is_container_v =
(has_push_back_v<C> and has_begin_v<C> and has_end_v<C>) or
(has_push_front_v<C> and has_rbegin_v<C> and has_rend_v<C>) or
(has_insert_v<C> and has_begin_v<C> and has_end_v<C>);
// enable_if
template <typename ContOut, typename ContIn>
using enable_if_containers =
std::enable_if_t<is_container_v<ContOut> and is_container_v<ContIn>>;
// solution class
template <
template <typename> class ContOut = std::vector,
template <typename> class ContIn = std::vector,
typename T = int,
typename = enable_if_containers<ContOut<ContIn<T>>, ContIn<T>>
>
class VariableSizedArrays {
template <typename I>
struct ReIterator {
using pos_t = std::pair<int, int>;
template <typename Pair>
struct PosT {
typename Pair::first_type first;
typename Pair::second_type second;
PosT(const Pair& pos) : first{pos.first}, second{pos.second} {};
template <typename P>
auto operator ==(const P &) const { return false; }
auto operator ==(const Pair &p) const {
return p.first == first and p.second == second;
}
};
using Pos = PosT<pos_t>;
// Iterator tags
using iterator_category = std::random_access_iterator_tag;
using difference_type = Pos;
using value_type = T;
using reference = value_type &; // usually value_type &
using pointer = value_type *; // usually value_type *
I m_it;
Pos m_pos = pos_t{0, 0};
ReIterator(I it) : m_it{it} {}
auto &operator ++() { return *this; } // nop - needed by std::advance
auto &operator --() { return *this; } // nop - needed by std::advance
auto &operator +=(const Pos &pos) {
m_pos = pos;
return *this;
}
constexpr auto operator *() const {
using InnerT = typename std::iterator_traits<I>::value_type;
auto inner = *std::next(m_it, m_pos.first);
// constexpr chooses the right iterator to start with
if constexpr (has_push_front_v<InnerT>)
return *std::next(inner.rbegin(), m_pos.second);
else if constexpr (has_push_back_v<InnerT> or has_insert_v<InnerT>)
return *std::next(inner.begin(), m_pos.second);
// Unreachable SFINAE has checked before
}
auto operator ==(const ReIterator& o) const { return m_it == o.m_it; }
auto operator !=(const ReIterator& o) const { return m_it != o.m_it; }
};
using Inner = ContIn<T>; // inner array
using Outer = ContOut<Inner>; // outer array
Outer m_c; // outer container, keeps the other arrays in pace
template <typename C>
auto get_inserter(C &c) const {
// constexpr chooses the right iterator inserter for C
if constexpr (has_push_front_v<C>)
return std::front_inserter(c);
else if constexpr (has_push_back_v<C>)
return std::back_inserter(c);
else if constexpr (has_insert_v<C>)
return std::inserter(c, c.end());
// Unreachable SFINAE has checked before
}
constexpr auto get_begin_end(bool begin) const {
// constexpr chooses the right iterator to start with
if constexpr (has_push_front_v<Outer>)
return begin ? ReIterator(m_c.rbegin()) : ReIterator(m_c.rend());
else if constexpr (has_push_back_v<Outer> or has_insert_v<Outer>)
return begin ? ReIterator(m_c.begin()) : ReIterator(m_c.end());
// Unreachable SFINAE has checked before
}
public:
using value_type = T; // needed to support std::back_inserter
auto begin() const { return get_begin_end(true); }
auto end() const { return get_begin_end(false); }
auto &operator ++() {
*get_inserter(m_c)++ = Inner{};
return *this;
}
constexpr auto push_back(const T &t) {
if constexpr (has_push_front_v<Outer>)
return *get_inserter(*(--m_c.rend())) = t;
else if constexpr (has_push_back_v<Outer> or has_insert_v<Outer>)
return *get_inserter(*(--m_c.end())) = t;
// Unreachable SFINAE has checked before
}
};
template <typename I>
auto
variable_sized_arrays(I &in, size_t n) {
#ifdef CASE1
auto vsa = VariableSizedArrays<std::deque, std::deque>{};
#elif defined CASE2
auto vsa = VariableSizedArrays<std::deque, std::vector>{};
#elif defined CASE3
auto vsa = VariableSizedArrays<std::vector, std::deque>{};
#else
auto vsa = VariableSizedArrays{};
#endif
for(; n--; in++) // resync "in" iterator after copy action
std::copy_n(in, *in++, std::back_inserter(++vsa)); // *in++ = k
return vsa;
}
int
main(int, char *[]) {
// prepare iterators for input/output
auto in = std::istream_iterator<int>{std::cin};
auto in_last = std::istream_iterator<int>{};
auto out = std::ostream_iterator<int>{std::cout, "\n"};
// problem parameters (const and from input)
auto n = *in++;
[[maybe_unused]] auto q = *in++; // num arrays, num queries
auto &&vsa = variable_sized_arrays(in, n); // get matrix
while(in != in_last) // run queries until input is exhausted
*out++ = *std::next(vsa.begin(), {{*in++, *in++}}); // *in++ => i, j
return 0;
}