array

template<typename Value, typename Index = size_t>
class array : public ygm::container::detail::base_async_insert_key_value<array<Value, size_t>, std::tuple<size_t, Value>>, public ygm::container::detail::base_misc<array<Value, size_t>, std::tuple<size_t, Value>>, public ygm::container::detail::base_async_visit<array<Value, size_t>, std::tuple<size_t, Value>>, public ygm::container::detail::base_iterators<array<Value, size_t>>, public ygm::container::detail::base_iteration_key_value<array<Value, size_t>, std::tuple<size_t, Value>>, public ygm::container::detail::base_async_reduce<array<Value, size_t>, std::tuple<size_t, Value>>

Container for key-value pairs with keys that are contiguous indices in the range [0, size()-1].

Assigns ranks contiguous chunks of indices using block_partitioner object. Resizing array is an expensive operation as it requires reassigning storage to ranks.

Public Types

using self_type = array<Value, Index>

using mapped_type = Value

using key_type = Index

using size_type = Index

using for_all_args = std::tuple<Index, Value>

using container_type = ygm::container::array_tag

using ptr_type = typename ygm::ygm_ptr<self_type>

using iterator = array_iterator<mapped_type, false>

using const_iterator = array_iterator<mapped_type, true>

Public Functions

array() = delete

inline array(ygm::comm &comm, const size_type size)

Array constructor.

Parameters:

• comm – Communicator to use for communication

• size – Global size to use to array

inline array(ygm::comm &comm, const size_type size, const mapped_type &default_value)

Array constructor taking default value.

Parameters:

• comm – Communicator to use for communication

• size – Global size to use for array

• default_value – Value to initialize all stored items with

inline array(ygm::comm &comm, std::initializer_list<mapped_type> l)

Array constructor from std::initializer_list of values.

Initializer list is assumed to be replicated on all ranks. Initializer list only contains values to place in array. Indices assigned to values are provided in sequential order. Array size is determined by size of initializer list.

Parameters:

• comm – Communicator to use for communication

• l – Initializer list of values to put in array

inline array(ygm::comm &comm, std::initializer_list<std::tuple<key_type, mapped_type>> l)

Array constructor from std::initializer_list of index-value pairs.

Initializer list is assumed to be replicated on all ranks. Initializer list contains index-value pairs to place in array. Indices are not assumed to be in sequential order or contiguous. Array size is determined by max index within initializer list.

Parameters:

• comm – Communicator to use for communication

• l – Initializer list of index-value pairs to put in array

template<typename T>
inline array(ygm::comm &comm, const T &t)

Construct array from existing YGM container.

Existing container contains only values. Indices are assigned sequentially across ranks. Partitioning will likely not be the same between existing container and constructed array.

Template Parameters:

T – Existing container type

Parameters:

• comm – Communicator to use for communication

• t – YGM container containing values to put in array

template<typename T>
inline array(ygm::comm &comm, const T &t)

Construct array from existing YGM container of key-value pairs.

Requires input container for_all_args to be a single item tuple that is itself a key-value pair (e.g. works from a ygm::container::bag). Array size is determined by finding the largest index across all ranks.

Template Parameters:

T – Existing container type

Parameters:

• comm – Communicator to use for communication

• t – YGM container of key-value pairs to put in array.

template<typename T>
inline array(ygm::comm &comm, const T &t)

Construct array from existing YGM container of key-value pairs.

Requires input container’s for_all_args to be a tuple containing keys and values (e.g. works from a ygm::container::map). Array size is determined by finding the largest index across all ranks.

Template Parameters:

T – Existing container type

Parameters:

• comm – Communicator to use for communication

• t – YGM container of key-value pairs to put in array

template<typename T>
inline array(ygm::comm &comm, const T &t)

Construct array from existing STL container.

Existing container contains only values. Values are assumed to be distinct between ranks. Indices are assigned sequentially across ranks. Partitioning will likely not be the same between existing container and constructed array.

Template Parameters:

T – Existing container type

Parameters:

• comm – Communicator to use for communication

• t – STL container containing values to put in array

template<typename T>
inline array(ygm::comm &comm, const T &t)

Construct array from existing STL container of key-value pairs.

Requires existing container to have a value_type that contains keys and values. Array size is determined by finding the largest index across all ranks.

Template Parameters:

T – Existing container type

Parameters:

• comm – Communicator to use for communication

• t – STL container of key-value pairs to put in array.

inline ~array()

inline array(const self_type &other)

inline array(self_type &&other) noexcept

inline array &operator=(const self_type &other)

inline array &operator=(self_type &&other) noexcept

inline iterator local_begin()

Access to begin iterator of locally-held items.

Does not call barrier().

Returns:

Local iterator to beginning of items held by process.

inline const_iterator local_begin() const

Access to begin const_iterator of locally-held items for const array.

Does not call barrier().

Returns:

Local const iterator to beginning of items held by process.

inline const_iterator local_cbegin() const

Access to begin const_iterator of locally-held items for const array.

Does not call barrier().

Returns:

Local const iterator to beginning of items held by process.

inline iterator local_end()

Access to end iterator of locally-held items.

Does not call barrier().

Returns:

Local iterator to ending of items held by process.

inline const_iterator local_end() const

Access to end const_iterator of locally-held items for const array.

Does not call barrier().

Returns:

Local const iterator to ending of items held by process.

inline const_iterator local_cend() const

Access to end const_iterator of locally-held items for const array.

Does not call barrier().

Returns:

Local const iterator to ending of items held by process.

inline void local_insert(const key_type &key, const mapped_type &value)

Insert a key and value into local storage.

Assumes key (index) has already been converted to a local index.

Parameters:

• key – Local index to store value at

• value – Vale to store

template<typename Function, typename ...VisitorArgs>
inline void local_visit(const key_type index, Function &&fn, const VisitorArgs&... args)

Visit an item stored locally.

Template Parameters:

• Function – functor type

• VisitorArgs... – Variadic argument types

Parameters:

• index – Index to visit

• fn – User-provided function to execute at item

• args... – Arguments to pass to user functor

inline void async_set(const key_type index, const mapped_type &value)

Set the value associated to given index.

Parameters:

• index – Index to store value at

• value – Value to store

template<typename BinaryOp>
inline void async_binary_op_update_value(const key_type index, const mapped_type &value, const BinaryOp &b)

Apply a binary operation to a provided value and the value already stored at a given index to update the stored value.

Template Parameters:

BinaryOp – functor type

Parameters:

• index – Index to apply update at

• value – New value to update with

• b – Binary operation to apply

inline void async_bit_and(const key_type index, const mapped_type &value)

Apply bitwise and to update stored value.

Parameters:

• index – Index to perform update at

• value – Value to “and” with current value

inline void async_bit_or(const key_type index, const mapped_type &value)

Apply bitwise or to update stored value.

Parameters:

• index – Index to perform update at

• value – Value to “or” with current value

inline void async_bit_xor(const key_type index, const mapped_type &value)

Apply bitwise xor to update stored value.

Parameters:

• index – Index to perform update at

• value – Value to “xor” with current value

inline void async_logical_and(const key_type index, const mapped_type &value)

Apply logical and to update stored value.

Parameters:

• index – Index to perform update at

• value – Value to “and” with current value

inline void async_logical_or(const key_type index, const mapped_type &value)

Apply logical or to update stored value.

Parameters:

• index – Index to perform update at

• value – Value to “or” with current value

inline void async_multiplies(const key_type index, const mapped_type &value)

Apply multiplication to update stored value.

Parameters:

• index – Index to perform update at

• value – Value to multiply with current value

inline void async_divides(const key_type index, const mapped_type &value)

Apply division to update stored value.

Parameters:

• index – Index to perform update at

• value – Value to divide current value by

inline void async_plus(const key_type index, const mapped_type &value)

Apply addition to update stored value.

Parameters:

• index – Index to perform update at

• value – Value to add to current value

inline void async_minus(const key_type index, const mapped_type &value)

Apply subtraction to update stored value.

Parameters:

• index – Index to perform update at

• value – Value to subtract from current value

template<typename UnaryOp>
inline void async_unary_op_update_value(const key_type index, const UnaryOp &u)

Apply a unary operation to the value already stored at a given index to update the stored value.

Template Parameters:

UnaryOp – functor type

Parameters:

• index – Index to apply update at

• u – Unary operation to apply

inline void async_increment(const key_type index)

Increment stored value.

Parameters:

index – Index to perform update at

inline void async_decrement(const key_type index)

Decrement stored value.

Parameters:

index – Index to perform update at

const mapped_type &default_value() const

inline void resize(const size_type size, const mapped_type &fill_value)

Set new global size for array.

This operation requires repartitioning the data already stored in a container, which is a O(old_size) operation.

Parameters:

• size – New global size

• fill_value – Value to initialize new values to (when expanding an array)

inline void resize(const size_type size)

Set new global size for array with a default fill value.

Equivalent to resize(size, m_default_value)

Parameters:

size – New global size

inline size_t local_size()

Get the number of elements stored on the local process.

Returns:

Local size of array

inline size_t size() const

Get the global size of the array.

Returns:

Array’s global size

inline void local_clear()

Clear the local contents of the array and set size to 0.

Setting the local size to 0 cannot be performed independently of other ranks. This operation needs to be called collectively for the array.

inline void local_swap(self_type &other)

Swap the local contents of an array.

Parameters:

other – The array to swap local contents with

template<typename Function>
inline void local_for_all(Function &&fn)

Apply a lambda to all local elements.

This operation can be called non-collectively.

Template Parameters:

Function – functor type

Parameters:

fn – Functor object to apply to all elements locally stored in the array

template<typename ReductionOp>
inline void local_reduce(const key_type index, const mapped_type &value, ReductionOp reducer)

Update a locally stored element by performing a binary operation between it and a provided value.

Template Parameters:

ReductionOp – functor type

Parameters:

• index – Global index to perform binary operation at. Must be found on the local process.

• value – Value to combine with the currently-held value

• reducer – Binary operation to perform

inline void sort()

Globally sort values in array in increasing order.

Partitions data using sampled pivots to approximately balance values on ranks. Then use std::sort locally on values before reinserting into the array.

inline void async_insert(const typename std::tuple_element<0, for_all_args>::type &key, const typename std::tuple_element<1, for_all_args>::type &value)

Asynchronously insert a key-value pair into a container.

The container’s local_insert() function is free to determine the behavior when key is already in the container

ygm::container::map<int, std::string> my_map(world);
my_map.async_insert(1, "one");

Parameters:

• key – Key to insert

• value – Value to associate to key

inline void async_insert(const std::pair<const typename std::tuple_element<0, for_all_args>::type, typename std::tuple_element<1, for_all_args>::type> &kvp)

Asynchronously insert a key-value pair into a container.

Equivalent to async_insert(kvp.first, kvp.second)

Parameters:

kvp – Key-value pair to insert

inline void clear()

Clears the contents of a YGM container.

inline void swap(derived_type &other)

Swaps the contents of a YGM container.

Parameters:

other – Container to swap with

inline ygm::comm &comm() const

Access to underlying YGM communicator.

Returns:

YGM communicator used for communication by container

inline ygm::ygm_ptr<derived_type> get_ygm_ptr()

Access to the ygm_ptr used by the container.

Returns:

ygm_ptr used by the container when identifying itself in async calls on the ygm::comm

inline const ygm::ygm_ptr<derived_type> get_ygm_ptr() const

Const access to the ygm ptr used by the container.

Returns:

ygm_ptr to const version of container

template<typename Visitor, typename ...VisitorArgs>
inline void async_visit(const typename std::tuple_element<0, for_all_args>::type &key, Visitor &&visitor, const VisitorArgs&... args)

Asynchronously visit key within a container and execute a user-provided function.

ygm::container::map<std::string, int> my_map(world);
my_map.async_insert("one", 1);
world.barrier();
my_map.async_visit("one", [](const auto &key, auto &val, int &to_add) {
   val += to_add;
   }, world.size())
world.barrier();

will result in a value of world.size() * world.size() + 1 associated to the key "one".

Template Parameters:

• Visitor – Type of user-provided function

• VisitorArgs... – Variadic argument types to give to user function

Parameters:

• key – Key to visit in container

• visitor – User-provided function to execute at key

• args... – Variadic arguments to pass to user-provided function

template<typename Visitor, typename ...VisitorArgs>
inline void async_visit_if_contains(const typename std::tuple_element<0, for_all_args>::type &key, Visitor visitor, const VisitorArgs&... args)

Asynchronously visit key within a container and execute a user-provided function only if the key already exists.

This function differs from async_visit in that it will not default construct a value within the container prior to visiting a key that does not already exist.

Template Parameters:

• Visitor – Type of user-provided function

• VisitorArgs... – Variadic argument types to give to user function

Parameters:

• key – Key to visit in container

• visitor – User-provided function to execute at key

• args... – Variadic arguments to pass to user-provided function

template<typename Visitor, typename ...VisitorArgs>
inline void async_visit_if_contains(const typename std::tuple_element<0, for_all_args>::type &key, Visitor visitor, const VisitorArgs&... args) const

Version of async_visit_if_contains that works on const objects and provides const arguments to the user-provided lambda.

inline auto begin()

Returns an iterator to the beginning of the local container’s data.

This function is primarly a convienience function for range based for loops

Warning

The iterator is a local iterator, not a global iterator

Returns:

iterator to the beginning of the local container’s data.

inline auto begin() const

Returns a const_iterator to the beginning of the local container’s data.

This function is primarly a convienience function for range based for loops

Warning

The const_iterator is a local iterator, not a global iterator

Returns:

auto const_iterator to the beginning of the local container’s data.

inline auto cbegin() const

Returns a const_iterator to the beginning of the local container’s data.

This function is primarly a convienience function for range based for loops

Warning

The const_iterator is a local iterator, not a global iterator

Returns:

auto const_iterator to the beginning of the local container’s data.

inline auto end()

Returns an iterator to the end of the local container’s data.

This function is primarly a convienience function for range based for loops

Warning

The iterator is a local iterator, not a global iterator

Returns:

iterator to the end of the local container’s data.

inline auto end() const

Returns a const_iterator to the end of the local container’s data.

This function is primarly a convienience function for range based for loops

Warning

The const_iterator is a local iterator, not a global iterator

Returns:

auto const_iterator to the end of the local container’s data.

inline auto cend() const

Returns a const_iterator to the end of the local container’s data.

This function is primarly a convienience function for range based for loops

Warning

The const_iterator is a local iterator, not a global iterator

Returns:

auto const_iterator to the end of the local container’s data.

template<typename Function>
inline void for_all(Function fn)

Iterates over all items in a container and executes a user-provided function object on each.

The user-provided function is expected to take a single key and value as separate arguments that make a (key, value) pair within the container. If the user provides a lambda as their function object, the lambda is allowed to capture.

Template Parameters:

Function – Type of user-provided function

Parameters:

fn – User-provided function

template<typename Function>
inline void for_all(Function &&fn) const

Const version of for_all that iterates over all items and passes them to the user function as const *.

The user-provided function is expected to take a single key and value as separate arguments that make a (key, value) pair within the container. If the user provides a lambda as their function object, the lambda is allowed to capture.

Template Parameters:

Function – Type of user-provided function

Parameters:

fn – User-provided function

template<typename STLContainer>
inline void gather(STLContainer &gto, int rank) const

Gather all values in an STL container.

Requires STL container to have a value_type that is (key, value) pairs from the YGM container

Template Parameters:

STLContainer – Type of STL container to gather to

Parameters:

• gto – Container to store results in

• rank – Rank to tather results on. Use -1 to gather to all ranks

template<typename STLContainer>
inline void gather(STLContainer &gto) const

Gather all values in an STL container on all ranks.

Equivalent to gather(gto, -1)

Template Parameters:

STLContainer – Type of STL container to gather to

Parameters:

gto – Container to store results in

template<typename Compare = std::greater<std::pair<key_type, mapped_type>>>
inline std::vector<std::pair<key_type, mapped_type>> gather_topk(size_t k, Compare comp = Compare()) const

Gather the k “largest” key-value pairs according to provided comparison function.

Template Parameters:

Compare – Type of comparison operator

Parameters:

• k – Number of key-value pairs to gather

• comp – Comparison function for identifying elements to gather

Returns:

vector of largest key-value pairs

template<typename YGMContainer>
inline void collect(YGMContainer &c) const

Collects all items in a new YGM container.

Template Parameters:

YGMContainer – Container type

Parameters:

c – Container to collect into

template<typename MapType, typename ReductionOp>
inline void reduce_by_key(MapType &map, ReductionOp reducer) const

Reduces all values in key-value pairs with matching keys.

Template Parameters:

• MapType – Result YGM container type

• ReductionOp – Functor type

Parameters:

• map – YGM container to hold result

• reducer – Functor for combining values

template<typename TransformFunction>
transform_proxy_key_value<derived_type, TransformFunction> transform(TransformFunction &&ffn)

Creates proxy that transforms key-value pairs in a container that are presented to user for_all calls.

The underlying items within the container are not modified.

Template Parameters:

TransformFunction – functor type

Parameters:

ffn – Function to transform items in container

inline auto keys()

Access to container presenting only keys.

Returns:

Transform object that returns only keys to user

inline auto values()

Access to container presenting only values.

Returns:

Transform object that returns only values to user

inline flatten_proxy_key_value<derived_type> flatten()

Flattens STL containers of values to allow a function to be called on inner items individually.

Underlying container is not modified.

template<typename FilterFunction>
filter_proxy_key_value<derived_type, FilterFunction> filter(FilterFunction &&ffn)

Filters items in a container so only allow for_all to execute on those that satisfy a given predicate function.

Filtered items are not removed from underlying container.

Template Parameters:

FilterFunction – Functor type

Parameters:

ffn – Function used to filter items in container.

template<typename ReductionOp>
inline void async_reduce(const typename std::tuple_element<0, for_all_args>::type &key, const typename std::tuple_element<1, for_all_args>::type &value, ReductionOp reducer)

Combines existing mapped_type item with value using a user-provided binary operation if key is found in container. Inserts default mapped_type prior to reduction if key does not already exist in container.

ygm::container::map<std::string, int> my_map(world);
my_map.async_insert("one", 1);
if (world.rank0()) {
   my_map.async_reduce("one", 2, std::plus<int>());
   my_map.async_reduce("two", 2, std::plus<int>());
}
world.barrier()

will result in my_map containing the pairs ("one", 3) and ("two", 2).

Template Parameters:

ReductionOp – Type of function provided by usert to perform reduction

Parameters:

• key – Key to search for within container

• value – Provided value to combine with existing value in container

Public Members

detail::block_partitioner<key_type> partitioner

Friends

friend struct detail::base_misc< array< Value, Index >, std::tuple< Index, Value > >

template<typename T, bool IsConst>
class array_iterator

Public Types

using value_type = std::pair<key_type, mapped_type&>

using iterator_proxy_type = iterator_proxy<T, IsConst>

Public Functions

inline array_iterator(self_type *arr, const key_type offset, const key_type index)

inline iterator_proxy_type operator*() const

inline arrow_proxy operator->() const

inline array_iterator &operator++()

inline array_iterator operator++(int)

inline bool operator==(const array_iterator &other)

inline bool operator!=(const array_iterator &other)

struct arrow_proxy

Public Functions

inline iterator_proxy_type *operator->()

Public Members

iterator_proxy_type m_proxy

template<typename T, bool IsConst>
struct iterator_proxy

Public Types

using value_ref_type = std::conditional_t<IsConst, const T&, T&>

Public Functions

inline iterator_proxy(const key_type i, value_ref_type v)

template<std::size_t N>
inline decltype(auto) get() const

Public Members

const key_type index

value_ref_type value