CPP/C++ STL Iterators and Algorithms
Table of Contents
- 1. STL Iterators and Algorithms
- 1.1. Overview
- 1.2. Iterators
- 1.2.1. Overview
- 1.2.2. Checking Iterators
- 1.2.3. Example: Making a class iterable
- 1.2.4. Example: Implementing a numeric range iterator
- 1.2.5. Example: Implementing an index-adapter iterator
- 1.2.6. Example: Implementing iterator with boost iterator facade
- 1.2.7. Example: Implementing enumerate for-loop with boost iterator facade
- 1.3. Standard STL Algorithms
- 1.3.1. distance
- 1.3.2. for_each
- 1.3.3. for_each and function objects (functors)
- 1.3.4. istream iterator
- 1.3.5. fill
- 1.3.6. Copy iterator to output stream
- 1.3.7. Copy
- 1.3.8. Copy_if
- 1.3.9. Count
- 1.3.10. CountIf
- 1.3.11. Equal
- 1.3.12. generator
- 1.3.13. reverse
- 1.3.14. iota
- 1.3.15. accumulate
- 1.3.16. adjacent different
- 1.3.17. max_element and min_element
- 1.4. Implementing custom algorithms
1 STL Iterators and Algorithms
1.1 Overview
STL Algorithms are a collection of useful generic functions which operates over iterators ranges of STL containers/collections for performing many common tasks such as sorting, copying elements, removing elements, computing sum of elements and so on. It is worth knowing how to use iterators as they are already solve many common tasks and problems and also avoids reiventing the wheel.
Notes:
- Function-object here means: function pointer, callable object which overloads the operator function-call operator()(int x) or C++11 lambda function.
- Many STL algorithsm works in similar way to higher order function of functional programming as they accept a function-object as argument.
- STL Algorithms makes uses of iterators (generalization of pointers) and function-object argument or function arguments for short.
- Benefits of STL Algorithms:
- Allows declarative programming since they allow one to perform a task by declaring what to do instead of how to do.
- Provide a common vocabulary for C++ developers as iterators are standardized and widely known what can increase the code readability.
- Provide many blocks general building blocks for C++ what saves times and headaches.
- Algorithms work with almost any STL container/collection/data structure and can also work with any custom collections which have iterators.
Iterator:
- Defintion: generalization of pointer - provides a standard interface for accessing elements of STL containers or any container supporting iterators without caring about the container implementation or the container internal data representation.
- Types of iterators:
- Input Iterator
- Read-only and can be read only once.
- istream_iterator(istream& is);
- Output Iterator
- Write-only
- Example: ostream_iterator(ostream& os);
- Forward Iterator
- Gathering input + output iterators
- Example: std::forward_list::iterator, std::unordered_map::iterator
- Bidirectional Iterator
- Like Forward Iterator, but also has operator–
- Example: std::list::iterator
- Random Access Iterator
- Has overloaded operator[], pointer arithmetic
- Example: pointer to C-array and vector or deque iterators.
- Input Iterator
Algorithms:
- Functional
- std::for_each
- Applies a function which performs side effects on every element of a collection.
- std::transform
- std::for_each
- Query
- std::count
- Count the number of elements equal to a given value
- std::count_if
- Count the number of elements matching a given predicate function.
- std::equal(iter begin1, iter end1, inter begin2)
- std::all_of(iter begin, iter end, PRED pred) -> bool
- Returns true if all elements satisfies a predicate function PRED which type is std::function<bool (X)> where X is the type of container elements. Note: For an empty container always returns true.
- std::any_of(iter begin, iter end, PRED pred) -> bool
- Returns true if at least one element of the container satifies a predicate. For an empty containers, always returns false.
- std::none_of(iter begin, iter end, PRED pred) -> bool
- Returns true if no element of a container satifies a given predicate.
- std::find
- std::find_if
- std::ajdacent_find
- std::binary_search
- std::count
- Moving
- std::copy(iter begin1, iter end1, iter begin2)
- Copy contents of container 1 to container 2. Note: it makes the assumption that the second container or output iterator has enough slots to accomodate the elements of container1.
- std::move(iter begin1, iter end1, iter begin2)
- std::swap(iter begin1, iter end1, iter begin2)
- Swap two containers with same size.
- std::copy(iter begin1, iter end1, iter begin2)
- Value Modifiers
- std::fill(iter begin1, iter end1, value);
- Fill a container with a given value.
- std::generate(iter begin1, iter end1, fn)
- Fill a container by calling the function fn of type (() => T) at every element. Note: T is the type of container elements.
- std::replace(iter begin1, iter end, T value1, T value2)
- Replace all elements equal to value1 by value2.
- std::fill(iter begin1, iter end1, value);
- Reordering
- std::sort(iter begin, iter end)
- std::reverse(iter begin, iter end)
- std::rotate
- std::shuffle(iter begin, iter end, std::default_random_engine(seed) - Note (C++11)
- std::random_shuffle(iter begin, iter end) [Deprecated]
- std::next_permutation
- std::prev_permutation
- Numeric - header <numeric>
- std::iota
- std::transform
- std::accumulate(iter begin, iter end, intial value)
- Computes the sum of elements in the container by calling the operator (+)
- std::adjacent_difference
- std::partial_sum
- std::inner_product
Further Reading:
- CppCon 2015: Michael VanLoon “STL Algorithms in Action ” - YouTube
- Advanced R
- The World Map of C++ STL Algorithms - Fluent C++
- Data structures and algorithms problems in C++ using STL
- C++ Tutorial: STL IV - Algorithms - 2018
- Top 5 Beautiful C++ std Algorithms Examples - CodeProject
- C++ STL Iterators | Go4Expert
- C++ Custom Iterators - Tobias Anderberg
- C++: Iterators | Dr Dobb's
- Iterators: an ADT for Positions
Documentation:
1.2 Iterators
1.2.1 Overview
An iterator is a generalization of pointers for decouple data structures from algorithms and accessing data structures in a uniform way regardless they implementation details and memory layout.
General format of an iterator object
An iterator object generally has the following structure:
See:
- std::iterator_traits documentation
- iterator_tags
template<typename T> class SomeIteratorClass { public: // ----- Iterator type tags ------------------// // using value_type = T; // Type that iterator refers to using pointer = T*; // Pointer using reference = T&; // Reference using difference_type = int; // (int or ptrdiff) Type of difference between two iterators. using iterator_category = .... ; // Tag Indicates the iterator's capabilities // can be std::forward_iterator_tag, std::input_iterator_tag and so on. // ----- Iterator Operationss ------------------// // // Dereference operator: T& operator*(); // Dereference operator const T& operator*() const; // Dereference operator: T* operator->() const // Advance iterator operation: // Prefix increment operator, allows ++iterator; SomeIteratorClass& operator++(); // Advance iterator operation: // Postfix increment operator, allows iterator++ SomeIteratorClass& operator++(int); // Equality operator bool operator==(const SomeIteratorClass& rhs) const; // Non-equality operator bool operator!=(const SomeIteratorClass& rhs) const; ... ... ... };
Random Access Iterator
Experimeting Iterators in ROOT REPL:
- Create a vector object:
>> std::vector<int> xs{1, 2, 3, 4, 5, 6}; >> xs (std::vector<int> &) { 1, 2, 3, 4, 5, 6 }
- Create an interator to the beginning of the container (object 'it')
>> auto it = xs.begin(); >> it (__gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > > &) @0x7fb750ce9028 // Dereference iterator to get the pointed object: >> *it (int) 1
- Manipulate iterator:
// Increment iterator >> it++; >> *it (int) 2 >> it++; >> *it (int) 3 // Check whether is the end of the iteration. >> it == xs.end() it == xs.end() (bool) false >> it++; >> *(it++) (int) 4 >> *(it++) (int) 5 >> *(it++) (int) 6 // End of iteration? >> it == xs.end() (bool) true >>
- Decrement iterator:
- A vector iterator is a random access iterator, so it can also be decremented.
>> auto itb = xs.end() (__gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > > &) @0x7fb750ce9030 >> itb-- (__gnu_cxx::__normal_iterator) @0x3e32550 >> *itb (int) 6 >> itb--,*itb (int) 5 >> itb--,*itb (int) 4 >> itb--,*itb (int) 3 >> itb--,*itb (int) 2 >> itb--,*itb (int) 1 // Stop iteration >> itb == xs.begin() (bool) true
Iterators and deque data structure
Create iterator for deque data structure:
>> std::deque<char> ds{'a', 'b', 'c', 'd', 'e'}; >> std::deque<char>::iterator itt = ds.begin(); >> ds (std::deque<char> &) { 'a', 'b', 'c', 'd', 'e' }
Manipulate Iterator:
>> itt (std::deque<char, std::allocator<char> >::iterator &) @0x7fb750ce9088 >> *itt (char) 'a' >> ++itt,*itt (char) 'b' >> ++itt,*itt (char) 'c' >> ++itt,*itt (char) 'd' >> ++itt,*itt (char) 'e' >> itt == ds.end() (bool) false >> ++itt (std::_Deque_iterator<char, char &, char *>::_Self &) @0x7fb750ce9088 >> itt == ds.end() (bool) true
Loop over iterators
Version 1: Loop over iterator - defining iterator without auto syntax.
>> auto xss = std::vector<std::string>{"generic", "programming", "C++", "low", "level", "high"}; >> xss { "generic", "programming", "C++", "low", "level", "high" } >> // ************* VERSION 1 ********************** // Explicit notation >> std::vector<std::string>::iterator xit = xss.begin(); >> for(; xit != xss.end(); xit++) std::cout << " => " << *xit << "\n"; => generic => programming => C++ => low => level => high >>
Or:
for(std::vector<std::string>::iterator xit2 = xss.begin(); xit2 != xss.end(); xit2++) { std::cout << " => " << *xit2 << "\n"; } // Output: => generic => programming => C++ => low => level => high
Version 2: Loop over iterator - defining iterator with auto syntax.
// ************* VERSION 2 ********************** // C++11 amazing auto type deduction! >> auto ait = xss.begin(); >> for(; ait != xss.end(); ait++) std::cout << " => " << *ait << "\n"; => generic => programming => C++ => low => level => high >>
Or:
>> for(auto ait = xss.begin(); ait != xss.end(); ait++) std::cout << " => " << *ait << "\n"; => generic => programming => C++ => low => level => high
1.2.2 Checking Iterators
Iterators of STL containers can be verified at compile-time using static_asserts, that yields a compile-time error when the predicate is false and do nothing when the predicate evaluates to true.
File: iterator_check.cpp
Headers and macros:
#include <iostream> #include <deque> #include <list> #include <vector> /** Compile-time static assertions that aborts compilation when types are not equal. * -----------------------------------------------------------------------------*/ #define ASSERT_TYPE_EQUAL(type, expr) \ static_assert(std::is_same<type, expr>::value, "Expected type equality")
Main Function: part 1 => Check vector<int>::iterator
using iter = std::vector<int>::iterator; // Iterator iter::iterator_category type tag indicates its category and // capabilities. // // Random access iterators can be manipulated like a pointer and accessed // at any position. ASSERT_TYPE_EQUAL(std::random_access_iterator_tag, iter::iterator_category); // Type of object that iterator refers to ASSERT_TYPE_EQUAL(int , iter::value_type ); // Type of pointer to object that iterator refers to. ASSERT_TYPE_EQUAL(int*, iter::pointer); // Type of references to object that iterator refers to ASSERT_TYPE_EQUAL(int&, iter::reference); // Type equivalent to the difference between two iterators ASSERT_TYPE_EQUAL(ptrdiff_t, iter::difference_type);
Main Function: part 2 => Check lsit<int>::iterator
// ======== std::list iterator assertions ===============// using iterd = std::list<double>::iterator; ASSERT_TYPE_EQUAL(std::bidirectional_iterator_tag, iterd::iterator_category); ASSERT_TYPE_EQUAL(double , iterd::value_type ); ASSERT_TYPE_EQUAL(double*, iterd::pointer); ASSERT_TYPE_EQUAL(double&, iterd::reference); ASSERT_TYPE_EQUAL(ptrdiff_t, iterd::difference_type); std::cout << " Successful OK! ..." << std::endl;
1.2.3 Example: Making a class iterable
The following code shows how to make a class iterable with for-range based loop or the old iterator-based loop.
File: iterable_class.cpp
#include <iostream> #include <vector> #include <deque> #include <tuple> #include <initializer_list> struct Point2D { double x = 0.0; double y = 0.0; Point2D(double x, double y): x(x), y(y) { } }; // Iterable class class Curve2D { private: std::deque<Point2D> m_points; public: Curve2D() { } // Initializer list constructor Curve2D(std::initializer_list<Point2D> const& list) : m_points(list.begin(), list.end()) { } // Iterator pair constructor template<typename Iterator> Curve2D(Iterator it_begin, Iterator it_end) : m_points(it_begin, it_end){ } Curve2D& addPoint(double x, double y) { m_points.emplace_back(x, y); return *this; } // Required for make the class iterable with for-range based loop auto begin() { return m_points.begin(); } auto end() { return m_points.end(); } // Required for make the class iterable with for-range based loop auto cbegin() { return m_points.cbegin(); } auto cend() { return m_points.cend(); } }; int main() { std::cout << "\n === EXPERIMENT 1 == Iterator-based for-loop ============" << std::endl; { std::vector<Point2D> curve_vector = {{10.0, 4.0}, {20.0, 12.5}, {4.5, 10.25}, {8.0, 3.51}}; // Range constructor Curve2D curve(curve_vector.begin(), curve_vector.end()); std::cout << " Drawing curve: "; for(auto it = curve.begin(); it != curve.end(); it++) { std::cout << " => Point( " << it->x << ", " << it->y << " ) "; } std::cout << std::endl; } std::cout << "\n === EXPERIMENT 2 -- Range-based for-loop ==================" << std::endl; { // Initializer list constructor Curve2D curve = {{10.0, 4.0}, {20.0, 12.5}, {4.5, 10.25}, {8.0, 3.51}}; std::cout << " Drawing curve: "; for(auto const& [x, y]: curve) { std::cout << " => Point( " << x << ", " << y << " ) "; } std::cout << std::endl; } return 0; }
Program output:
=== EXPERIMENT 1 == Iterator-based for-loop ============ Drawing curve: => Point( 10, 4 ) => Point( 20, 12.5 ) => Point( 4.5, 10.25 ) => Point( 8, 3.51 ) === EXPERIMENT 2 -- Range-based for-loop ================== Drawing curve: => Point( 10, 4 ) => Point( 20, 12.5 ) => Point( 4.5, 10.25 ) => Point( 8, 3.51 )
1.2.4 Example: Implementing a numeric range iterator
Headers:
Class RangeIterator:
template<typename T> class RangeIterator { public: // Type that iterator refers to using value_type = T; // Pointer using pointer = T*; // Reference using reference = T*; // Tag Indicates the iterator's capabilities using iterator_category = std::input_iterator_tag; // Type of difference between two iterators. using difference_type = int; RangeIterator(T value) : m_step(0), m_value(value) { } RangeIterator(T value, T step) : m_step(step), m_value(value) { } // Dereference operator: value_type& operator*() { return m_value; } // Dereference operator: const value_type& operator*() const { return m_value; } value_type* operator->() { return &m_value; } // Prefix increment operator RangeIterator& operator++() { m_value += m_step; return *this; } // Postfix increment operator RangeIterator& operator++(int) { m_value += m_step; return *this; } bool operator==(const RangeIterator& rhs) const { return this->m_value > rhs.m_value; } bool operator!=(const RangeIterator& rhs) const { return !this->operator==(rhs); } private: T const m_step; T m_value; };
Class NumericRange:
- Class that can be iterator in for-loops with range-based for-loops like STL containers std::vector, std::list and so on.
template<typename T> class NumericRange { public: NumericRange(T start, T step, T stop): m_start(start), m_step(step), m_stop(stop) { } RangeIterator<T> begin() { return RangeIterator<T>(m_start, m_step); } RangeIterator<T> end() { return RangeIterator<T>(m_stop); } private: T m_start; T m_step; T m_stop; };
Main function:
std::cout << std::fixed << std::setprecision(3); std::cout << "\n ==== EXPERIMENT 1 ==============================" << std::endl; { auto range = NumericRange(-10.0, 2.5, 10.0); int n = 0; for(auto it = range.begin(); it != range.end(); it++ ) { auto label = std::string(" x[") + std::to_string(n++) + "] = "; std::cout << std::setw(10) << label << std::setw(6) << *it << std::endl; } } std::cout << "\n ==== EXPERIMENT 2 ==============================" << std::endl; { int n = 0; for(auto x: NumericRange(-10.0, 2.5, 10.0)) { auto label = std::string(" x[") + std::to_string(n++) + "] = "; std::cout << std::setw(10) << label << std::setw(6) << x << std::endl; } } std::cout << "\n ==== EXPERIMENT 3 - STL algorithms ============" << std::endl; { auto range = NumericRange(-10.0, 2.5, 10.0); double result = std::accumulate( range.begin(), range.end() , 0.0 // Initial value of accumulator , [](double acc, double x) { return acc + x; }); // Initialize container from iterators std::vector<double> xs(range.begin(), range.end()); std::cout << " [INFO] Result = " << result << std::endl; } return 0;
Output:
==== EXPERIMENT 1 ============================== x[0] = -10.000 x[1] = -7.500 x[2] = -5.000 x[3] = -2.500 x[4] = 0.000 x[5] = 2.500 x[6] = 5.000 x[7] = 7.500 x[8] = 10.000 ==== EXPERIMENT 2 ============================== x[0] = -10.000 x[1] = -7.500 x[2] = -5.000 x[3] = -2.500 x[4] = 0.000 x[5] = 2.500 x[6] = 5.000 x[7] = 7.500 x[8] = 10.000 ==== EXPERIMENT 3 - STL algorithms ============ [INFO] Result = 0.000
1.2.5 Example: Implementing an index-adapter iterator
- Class: iterator_counter
- => Turns a given iterator passed as argument into an iterator that can be looped over with an index.
#include <iostream> #include <vector> #include <algorithm> #include <map> template<typename T> class iterator_counter { public: class itpair { // Only Class Iterator_counter can access the // internals of this class friend class iterator_counter<T>; size_t counter; T iterator; public: itpair(size_t counter, T it) : counter(counter), iterator(it) { } size_t index() const { return counter; } typename T::value_type& value() { return *iterator; } typename T::value_type const& value() const { return *iterator; } }; using value_type = itpair; using pointer = itpair*; using reference = itpair&; using iterator_category = std::input_iterator_tag; using difference_type = int; private: itpair mCurrent; public: iterator_counter(T ptr): mCurrent(0, ptr) { } // Dereference operator: itpair& operator*() { return mCurrent; } // Dereference operator: const itpair& operator*() const { return mCurrent; } itpair* operator->() { return &mCurrent; } // Prefix increment operator iterator_counter& operator++() { mCurrent.counter++; mCurrent.iterator++; return *this; } bool operator==(const iterator_counter& rhs) const { return this->mCurrent.iterator == rhs.mCurrent.iterator; } bool operator!=(const iterator_counter& rhs) const { return this->mCurrent.iterator != rhs.mCurrent.iterator; } };
- Class: CounterViewAdapter
- It can be iterated like a STL container, but it is not a container, it is a view and does not own or allocate any element.
template<typename Container> struct CounterViewAdapter { Container& mRef; CounterViewAdapter(Container& cont): mRef(cont) { } auto begin() { return iterator_counter(mRef.begin()); } auto end() { return iterator_counter(mRef.end()); } };
- Function main:
int main() { auto words = std::vector<std::string>{ "C++", "C++11", "asm", "asm-armeabi-32bits" , "PowerPC-PPC", "SuperH", "MIPS", "PLC S7-200" }; std::cout << " ======== Experiment 1 ===================" << std::endl; auto it_beg = iterator_counter(words.begin()); auto it_end = iterator_counter(words.end()); for(auto it = it_beg; it != it_end; ++it) { std::cout << " Counter = " << it->index() << " - value = " << it->value() << "\n"; } std::cout << "\n ======== Experiment 2 ===================" << std::endl; for(auto& x : CounterViewAdapter(words)) { std::cout << " Counter = " << x.index() << " - value = " << x.value() << "\n"; } std::cout << "\n ======== Experiment 3 ===================" << std::endl; auto view = CounterViewAdapter(words); std::for_each(view.begin(), view.end(), [](auto& x){ std::cout << " Counter = " << x.index() << " - value = " << x.value() << "\n"; }); return 0; }
Program Output:
======== Experiment 1 =================== Counter = 0 - value = C++ Counter = 1 - value = C++11 Counter = 2 - value = asm Counter = 3 - value = asm-armeabi-32bits Counter = 4 - value = PowerPC-PPC Counter = 5 - value = SuperH Counter = 6 - value = MIPS Counter = 7 - value = PLC S7-200 ======== Experiment 2 =================== Counter = 0 - value = C++ Counter = 1 - value = C++11 Counter = 2 - value = asm Counter = 3 - value = asm-armeabi-32bits Counter = 4 - value = PowerPC-PPC Counter = 5 - value = SuperH Counter = 6 - value = MIPS Counter = 7 - value = PLC S7-200 ======== Experiment 3 =================== Counter = 0 - value = C++ Counter = 1 - value = C++11 Counter = 2 - value = asm Counter = 3 - value = asm-armeabi-32bits Counter = 4 - value = PowerPC-PPC Counter = 5 - value = SuperH Counter = 6 - value = MIPS Counter = 7 - value = PLC S7-200
1.2.6 Example: Implementing iterator with boost iterator facade
The boost iterator facade uses the CRTP - Curious Recurring Template technique or simplifying the implementation of custom STL iterators. The client code inherits the class iterator_facade and implements some methods required by this class, then it generates all iterator member functions and operators.
Documentation:
Example: Numeric range iterator with Boost iterator_facade.
File: boost_iterator_range.cpp
#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <numeric> #include <cassert> #include <boost/iterator/iterator_facade.hpp> class RangeIterator : public boost::iterator_facade< // CRTP parameter => The inherited class RangeIterator // Type referred by the iterator , double // Iterator tag , boost::forward_traversal_tag > { mutable double m_value; double m_step; public: double value() const { return m_value; } explicit RangeIterator(double value) : m_value(value), m_step(0) { } RangeIterator(double value, double step) : m_value(value), m_step(step) { } private: friend class boost::iterator_core_access; // Required by boost_iterator_facade CRTP void increment() { m_value += m_step; } // Required by boost_iterator_facade CRTP bool equal(RangeIterator const& that) const { return m_value >= that.m_value + m_step; } // Required by boost_iterator_facade CRTP double& dereference() const { return m_value; } }; class NumericRange { double m_start; double m_step; double m_stop; public: NumericRange(double start, double step, double stop): m_start(start), m_step(step), m_stop(stop) { if(start > stop || step <= 0 ){ throw std::domain_error("Error: invalid range."); } } RangeIterator begin(){ return RangeIterator(m_start, m_step); } RangeIterator end(){ return RangeIterator(m_stop); } }; int main(int argc, char** argv) { std::cout << "\n ==== EXPERIMENT 1 ==============================" << std::endl; { int n = 0; for(auto const&x: NumericRange(-10.0, 2.5, 10.0)) { auto label = std::string(" x[") + std::to_string(n++) + "] = "; std::cout << std::setw(10) << label << std::setw(6) << x << std::endl; } } std::cout << "\n ==== EXPERIMENT 2 - STL algorithms ============" << std::endl; { auto range = NumericRange(-10.0, 2.5, 10.0); // Sum of all elements within range double result = std::accumulate( range.begin(), range.end() // Initial value of accumulator , 0.0 , [](double acc, double x) { return acc + x; }); std::cout << " Result = " << result << std::endl; } std::cout << "\n ==== EXPERIMENT 3 - Initialize Container =====" << std::endl; auto range = NumericRange(-12.0, 2.0, 12.0); // Initialize container from iterators // => Invoke iterator-pair constructor std::vector<double> xs(range.begin(), range.end()); std::cout << "\n [INFO] xs = [ "; for(auto const& x: xs){ std::cout << x << " "; } std::cout << " ]\n"; return 0; }
Program output:
==== EXPERIMENT 1 ============================== x[0] = -10 x[1] = -7.5 x[2] = -5 x[3] = -2.5 x[4] = 0 x[5] = 2.5 x[6] = 5 x[7] = 7.5 x[8] = 10 ==== EXPERIMENT 2 - STL algorithms ============ Result = 0 ==== EXPERIMENT 3 - Initialize Container ===== [INFO] xs = [ -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12 ]
1.2.7 Example: Implementing enumerate for-loop with boost iterator facade
The following code shows how to implement a Python-like enumerate for-loop with boost-iterator facade. This type of loop allows to iterate over sequence with a value and numeric index pair:
Python enumerate-loop:
$ python3 Python 3.6.8 (default, Mar 21 2019, 10:08:12) [GCC 8.3.1 20190223 (Red Hat 8.3.1-2)] on linux Type "help", "copyright", "credits" or "license" for more information. >>> >>> xs = ["C++", "Python3", "Python4", "Ruby", "OCaml", "F#"] >>> for x in enumerate(xs): print(x) ... (0, 'C++') (1, 'Python3') (2, 'Python4') (3, 'Ruby') (4, 'OCaml') (5, 'F#') >>> for index, value in enumerate(xs): print(" x = {0} value = {1}".format(index, value)) ... x = 0 value = C++ x = 1 value = Python3 x = 2 value = Python4 x = 3 value = Ruby x = 4 value = OCaml x = 5 value = F#
- File: enumerate_iterator.cpp
Headers:
#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <numeric> #include <cassert> #include <boost/iterator/iterator_facade.hpp>
Class itpair:
// Forwared declaration template<typename T> class EnumerateIterator; /// @brief Encapsulates index and iterator value pair /// @tparam T - Iterator type template<typename T> class itpair { // Only Class Iterator_counter can access the // internals of this class friend class EnumerateIterator<T>; size_t counter; T iterator; public: itpair(size_t counter, T it) : counter(counter), iterator(it) { } size_t index() const { return counter; } typename T::value_type& value() { return *iterator; } typename T::value_type const& value() const { return *iterator; } };
Class EnumerateIterator:
template<typename T> class EnumerateIterator : public boost::iterator_facade< // CRTP parameter => The inherited class EnumerateIterator<T> // Type referred by the iterator , itpair<T> // Iterator tag , boost::forward_traversal_tag > { public: EnumerateIterator(T iterator): m_current(0, iterator) {} private: mutable itpair<T> m_current; friend class boost::iterator_core_access; // Required by boost_iterator_facade CRTP void increment() { m_current.counter++; m_current.iterator++; } // Required by boost_iterator_facade CRTP bool equal(EnumerateIterator const& that) const { return m_current.iterator == that.m_current.iterator; } // Required by boost_iterator_facade CRTP itpair<T>& dereference() const { return m_current; } };
Class Enumerate:
template<typename Container> struct Enumerate { Container& mRef; Enumerate(Container& cont): mRef(cont) { } auto begin() { return EnumerateIterator(mRef.begin()); } auto end() { return EnumerateIterator(mRef.end()); } };
Function main:
auto words = std::vector<std::string>{ "C++", "C++11", "asm", "asm-armeabi-32bits" , "PowerPC-PPC", "SuperH", "MIPS", "PLC S7-200" }; std::cout << " ======== Experiment 1 ===================" << std::endl; auto it_beg = EnumerateIterator(words.begin()); auto it_end = EnumerateIterator(words.end()); for(auto it = it_beg; it != it_end; ++it) { std::cout << " Counter = " << it->index() << " - value = " << it->value() << "\n"; } std::cout << "\n ======== Experiment 2 ===================" << std::endl; for(auto& x : Enumerate(words)) { std::cout << " Counter = " << x.index() << " - value = " << x.value() << "\n"; } std::cout << "\n ======== Experiment 3 ===================" << std::endl; auto view = Enumerate(words); std::for_each(view.begin(), view.end(), [](auto& x){ std::cout << " Counter = " << x.index() << " - value = " << x.value() << "\n"; }); return 0;
Output:
======== Experiment 1 =================== Counter = 0 - value = C++ Counter = 1 - value = C++11 Counter = 2 - value = asm Counter = 3 - value = asm-armeabi-32bits Counter = 4 - value = PowerPC-PPC Counter = 5 - value = SuperH Counter = 6 - value = MIPS Counter = 7 - value = PLC S7-200 ======== Experiment 2 =================== Counter = 0 - value = C++ Counter = 1 - value = C++11 Counter = 2 - value = asm Counter = 3 - value = asm-armeabi-32bits Counter = 4 - value = PowerPC-PPC Counter = 5 - value = SuperH Counter = 6 - value = MIPS Counter = 7 - value = PLC S7-200 ======== Experiment 3 =================== Counter = 0 - value = C++ Counter = 1 - value = C++11 Counter = 2 - value = asm Counter = 3 - value = asm-armeabi-32bits Counter = 4 - value = PowerPC-PPC Counter = 5 - value = SuperH Counter = 6 - value = MIPS Counter = 7 - value = PLC S7-200
1.3 Standard STL Algorithms
1.3.1 distance
Returns the number of elements within an iterator range, aka iterator pair.
Documentation:
Example:
- std::distance with std::vector container
#include <vector> #include <iterator> // std::distance and std::begin >> std::vector<int> vec1 {4, 5, 10, 25, 40, -8, 9}; // Returns 7 => Number of elements between the >> std::distance(vec1.begin(), vec1.end()) (long) 7 >> >> std::distance(vec1.begin(), vec1.begin() + 5) (long) 5 >> std::vector<int>::iterator it_begin = vec1.begin(); >> std::vector<int>::iterator it_end = vec1.end(); >> std::distance(it_begin, it_end) (long) 7 >> std::distance(it_begin + 4, it_end) (long) 3
- std::distance with C-arrays
#include <iterator> // std::distance and std::begin >> double arr [] = {3.51, 9.81, 85.1, 85.6, 10.6, 9}; >> std::distance(std::begin(arr), std::end(arr)) (long) 6 >> std::distance(std::begin(arr) + 2, std::end(arr) - 1) (long) 3
1.3.2 for_each
- vector
#include <vector> #include <algorithm> void dispSqrt(double x){ std::cout << std::setw(10) << std::sqrt(x) << "\n"; } >> std::vector<int> v{2, 4, 56, 10, 25, 60, 10, 50, -10}; >> std::for_each(v.begin(), v.end(), [](double x){ std::cout << std::setw(10) << x << "\n";}); 2 4 56 10 25 60 10 50 -10 >> std::for_each(v.begin(), v.end(), dispSqrt); 1.41421 2 7.48331 3.16228 5 7.74597 3.16228 7.07107 -nan >> std::for_each(v.begin(), v.begin() + 4, dispSqrt); 1.41421 2 7.48331 3.16228
- deque
>> std::deque<int> vx{2, 4, 56, 10, 25, 50}; >> std::for_each(vx.begin(), vx.end(), [](double x){ std::cout << std::setw(10) << x << "\n";}); 2 4 56 10 25 50 >> std::for_each(vx.begin(), vx.end(), dispSqrt); 1.41421 2 7.48331 3.16228 5 7.07107 >> std::for_each(vx.begin(), vx.begin() + 3, dispSqrt); 1.41421 2 7.48331
- list
>> std::list<int> v{2, 4, 56, 10, 25, 60, 10}; >> std::for_each(v.begin(), v.end(), [](int x){ std::cout << std::setw(10) << x << "\n";}); 2 4 56 10 25 60 10
- map (aka dictionary, it's similar to hash table by usage (unordered_map in C++11 and higher), but uses different data structure inside: red-black tree (map) against hash table (unordered_map))
>> auto dataset = std::map<std::string, double> { {"x", 10.23}, {"z", -2.341}, {"k", sqrt(2)}}; >> std::cout << std::fixed << std::setprecision(3); std::for_each(dataset.begin(), dataset.end(), [](const std::pair<std::string, double>& p){ std::cout << std::setw(10) << p.first << std::setw(10) << p.second << "\n"; });
Output:
k 1.414 x 10.230 z -2.341
1.3.3 for_each and function objects (functors)
STL "algorithms" can also be used with callable objects function-objects or functors:
- vector + function-object (functor class)
/** Functor - Function Object * Encapsulates a quadratic function. */ struct QuadFun{ double a, b, c; QuadFun(double a, double b, double c): a(a), b(b), c(c) { } // Delegated constructor QuadFun(): QuadFun(1.0, 1.0, 1.0) { } double eval(double x){ // a * x^2 + b * x + c return a * x * x + b * x + c; } void operator()(double x){ std::cout << std::setw(10) << x << std::setw(10) << this->eval(x) << "\n"; } };
Example 1:
>> std::vector<int> v{2, 4, 56, 10, 25, 60, 10, 50, -10}; >> std::for_each(v.begin(), v.end(), QuadFun()) 2 7 4 21 56 3193 10 111 25 651 60 3661 10 111 50 2551 -10 91
Example 2:
>> auto q = QuadFun(2, 1, 5) (QuadFun &) @0x7f95a601c028 >> q.a (double) 2.0000000 >> q.b (double) 1.0000000 >> q.c (double) 5.0000000 >> >> q(0) 0 5 >> q(1) 1 8 >> q(2) 2 15 >> q.eval(0) (double) 5.0000000 >> q.eval(1) (double) 8.0000000 >> q.eval(2) (double) 15.000000 >> q.operator()(0) 0 5 >> q.operator()(1) 1 8 >> q.operator()(2) 2 15 >> q.operator()(3) 3 26 >> std::for_each(v.begin(), v.end(), q) 2 15 4 41 56 6333 10 215 25 1280 60 7265 10 215 50 5055 -10 195 >> q.a = 0 (double) 0.0000000 >> q.b = 0; >> q.c = 0; >> std::for_each(v.begin(), v.end(), q) 2 0 4 0 56 0 10 0 25 0 60 0 10 0 50 0 -10 0
1.3.4 istream iterator
- File
>> std::list<int> vy{2, 4, 56, 10, 25, 50}; >> std::for_each(vy.begin(), vy.end(), [](double x){ std::cout << std::setw(10) << x << "\n";}); 2 4 56 10 25 50
- file:
auto file = std::ifstream("/etc/hosts"); auto b = std::istream_iterator<std::string>(file); auto e = std::istream_iterator<std::string>(); std::for_each(b, e, [](std::string word){ std::cout << word << "\n";}); >> auto file = std::ifstream("/etc/hosts"); >> auto b = std::istream_iterator<std::string>(file); >> auto e = std::istream_iterator<std::string>(); >> std::for_each(b, e, [](std::string word){ std::cout << word << "\n";}); 127.0.0.1 localhost localhost.localdomain localhost4 localhost4.localdomain4 ::1 localhost localhost.localdomain localhost6 localhost6.localdomain6 >>
- String
std::string price = "10.23 12.0 10.05 10.8 15.80 16.24"; std::stringstream ss(price); std::istream_iterator<double> b(ss); std::istream_iterator<double> e; std::cout << std::fixed << std::setprecision(3); std::for_each(b, e, [](double x){ std::cout << std::setw(10) << x << "\n";}) >> std::for_each(b, e, [](double x){ std::cout << std::setw(10) << x << "\n";}) 10.230 12.000 10.050 10.800 15.800 16.240
1.3.5 fill
Set or initialize all container elements with a given element.
- Header: <algorithm>
Usage:
std::fil(IteratorBegin, IteratorEnd, value);
- Vector
>> std::vector<double> xs1(5); >> xs1 (std::vector<double> &) { 0.0000000, 0.0000000, 0.0000000, 0.0000000, 0.0000000 } >> >> std::fill(xs1.begin(), xs1.end(), 3.5) >> xs1 (std::vector<double> &) { 3.5000000, 3.5000000, 3.5000000, 3.5000000, 3.5000000 } >> >> std::fill(xs1.begin(), xs1.begin() + 3, 4.0) >> xs1 (std::vector<double> &) { 4.0000000, 4.0000000, 4.0000000, 3.5000000, 3.5000000 } >>
- List
>> std::list<double> xs2(5); >> xs2 (std::list<double> &) { 0.0000000, 0.0000000, 0.0000000, 0.0000000, 0.0000000 } >> std::fill(xs2.begin(), xs2.end(), 15.0) >> xs2 (std::list<double> &) { 15.000000, 15.000000, 15.000000, 15.000000, 15.000000 } >> >>
1.3.6 Copy iterator to output stream
>> vector<double> p {3.0, 5.0, 5.0, -10.0}; >> std::copy(p.begin(), p.end(), std::ostream_iterator<double>(std::cout, "\n")); 3 5 5 -10
1.3.7 Copy
Copy elements from a range (iterator pair) to an output iterator.
Example: copy vector to deque.
>> std::vector<int> xs{1, 2, 10, 20, 30, 50}; >> std::deque<int> ds; >> >> ds (std::deque<int> &) {} >> >> std::copy(xs.begin(), xs.end(), std::back_inserter(ds)); >> ds (std::deque<int> &) { 1, 2, 10, 20, 30, 50 } >>
- Copy deque to stdout
#include <iostream> #include <deque> #include <iterator> // ostream_iterator #include <algorithm> auto xs = std::deque<int> {15, -2, 10, 20, 30, 5}; auto oit = std::ostream_iterator<int>(std::cout, "\n "); std::copy(xs.begin(), xs.end(), oit); >> std::copy(xs.begin(), xs.end(), oit); 15 -2 10 20 30 5 >>
- Copy deque to string
#include <iostream> #include <deque> #include <iterator> // ostream_iterator #include <algorithm> #include <string> #include <sstream> auto xs = std::deque<int> {15, -2, 10, 20, 30, 5}; std::stringstream ss; auto oit = std::ostream_iterator<int>(ss, " "); std::copy(xs.begin(), xs.end(), oit); >> std::cout << ss.str() << "\n"; 15 -2 10 20 30 5 >>
- Copy C-array to vector
>> auto v1 = std::vector<double>{} (std::vector<double, std::allocator<double> > &) {} >> auto v2 = std::vector<double>{} (std::vector<double, std::allocator<double> > &) {} >> double dataset[] = {-2.23, 10.94, 8.87, 4.56, 2.15} (double [5]) { -2.2300000, 10.940000, 8.8700000, 4.5600000, 2.1500000 } >> >> std::copy(std::begin(dataset), std::end(dataset), std::back_inserter(v1)) (std::back_insert_iterator<std::vector<double, std::allocator<double> > >) @0x250d860 >> v1 (std::vector<double, std::allocator<double> > &) { -2.2300000, 10.940000, 8.8700000, 4.5600000, 2.1500000 } >> >> std::copy(dataset, dataset + 5, std::back_inserter(v2)); >> v2 (std::vector<double, std::allocator<double> > &) { -2.2300000, 10.940000, 8.8700000, 4.5600000, 2.1500000 } >>
1.3.8 Copy_if
Copy elements from a range (iterator pair) to an output iterator which matches some predicate (unary boolean function).
Example 1: std::copy_if with lambda function
#include <vector> #include <deque> #include <algorithm> auto xs = std::vector<int> {10, 2, 25, 90, 4, 50, 80, 120, 35, 67}; auto out1 = std::deque<int>{}; >> std::copy_if(xs.begin(), xs.end(), std::back_inserter(out1), [](int x){ return x < 40; }); >> out1 { 10, 2, 25, 4, 35 } >> >> out1.clear(); >> out1 {}
Example 2: std::copy_if with predefined function-objects and std::bind.
- See: <functional> - contains lots of built-in function objects which can be comnbined with iterators and higher order functions.
#include <vector> #include <deque> #include <algorithm> #include <functional> // Import _1, _2, _2 for std::bind using namespace std::placeholders; auto xs = std::vector<int> {10, 2, 25, 90, 4, 50, 80, 120, 35, 67}; auto out1 = std::deque<int>{}; // Copy only elements < 40 >> std::copy_if(xs.begin(), xs.end(), std::back_inserter(out1), std::bind(std::less<int>(),_1, 40)); >> out1 { 10, 2, 25, 4, 35 }
1.3.9 Count
The algorithm count returns how many elements of a container are equal to a given value.
- Vector:
>> auto xs = std::vector<int> {1, 2, 3, 2, 2, 5, 9, 8, 10, 5, 9, 4, 2, 9, 1}; >> >> std::count(xs.begin(), xs.end(), 1) (long) 2 >> std::count(xs.begin(), xs.end(), 2) (long) 4 >> std::count(xs.begin(), xs.end(), 8) (long) 1 >> std::count(xs.begin(), xs.end(), 100) (long) 0 >>
- C arrays
>> int arr [] = {1, 2, 3, 2, 2, 5, 9, 8, 10, 5, 9, 4, 2, 9, 1}; // Number of array elements >> int size = sizeof(arr) / sizeof(int) (int) 15 >> std::count_if(arr, arr + size, [](int x){ return x == 100;}) (long) 0 >> std::count_if(arr, arr + size, [](int x){ return x == 2;}) (long) 4 >> std::count_if(arr, arr + size, [](int x){ return x == 8;}) (long)
1.3.10 CountIf
Count how many elements satifies a given predicate.
>> std::count_if(xs.begin(), xs.end(), [](int x){ return x == 100;}) (long) 0 >> >> std::count_if(xs.begin(), xs.end(), [](int x){ return x == 2;}) (long) 4 >> std::count_if(xs.begin(), xs.end(), [](int x){ return x == 100;}) (long) 0 >> >> std::count_if(arr, arr + size, [](int x){ return x <= 5;}) (long) 10 >>
1.3.11 Equal
Check whether two sequences are equal, example:
- Docs: equal - C++ Reference
>> >> std::vector<int> xs{1, 2, 3, 4, 5, 6}; >> std::list<int> xslist{1, 2, 3, 4, 5, 6}; >> >> std::equal(xs.begin(), xs.end(), xslist.begin()) (bool) true >> std::equal(xslist.begin(), xslist.end(), xs.begin()) (bool) true >> xslist.push_front(7) >> xslist (std::list<int> &) { 7, 1, 2, 3, 4, 5, 6 } >> std::equal(xslist.begin(), xslist.end(), xs.begin()) (bool) false >> std::equal(xs.begin(), xs.end(), xslist.begin()) (bool) false >>
1.3.12 generator
Header: <algorithm>
>> std::vector<int> xs(10); >> xs (std::vector<int> &) { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } >> std::generate(xs.begin(), xs.end(), [](){ return 5; }) >> xs (std::vector<int> &) { 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 } >> int x = 0; >> std::generate(xs.begin(), xs.end(), [&](){ x++ ; return x; }) >> xs (std::vector<int> &) { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } >> >> int k = 1; >> std::generate(xs.begin(), xs.end(), [&](){ k++ ; return k * 3; }) >> xs (std::vector<int> &) { 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 } >>
1.3.13 reverse
Reverse a sequence.
- Header: <algorithm>
- https://en.cppreference.com/w/cpp/algorithm/reverse
STL List
>> std::list<std::string> data = { "hello" , "world", "C++", "iterators", "assembly"}; >> data (std::list<std::string> &) { "hello", "world", "C++", "iterators", "assembly" } >> std::reverse(data.begin(), data.end()) >> data (std::list<std::string> &) { "assembly", "iterators", "C++", "world", "hello" } >>
STL Vector
>> std::vector<std::string> data2 = { "hello" , "world", "C++", "iterators", "assembly"}; >> std::reverse(data2.begin(), data2.end()) >> data2 (std::vector<std::string> &) { "assembly", "iterators", "C++", "world", "hello" } >>
1.3.14 iota
Header: <numeric>
>> std::iota(xsa.begin(), xsa.end(), 1) >> xsa (std::vector<int> &) { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } >> std::iota(xsa.begin(), xsa.end(), 2) >> xsa (std::vector<int> &) { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 } >> std::iota(xsa.begin(), xsa.end(), 2) >> xsa (std::vector<int> &) { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 } >> std::iota(xsa.begin(), xsa.end(), 4) >> xsa (std::vector<int> &) { 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 } >>
1.3.15 accumulate
This function works in a similar way to the fold-left operation common in functional programming languages.
- header: <numeric>
- https://en.cppreference.com/w/cpp/algorithm/accumulate
>> std::vector<int> xss{1, 2, 4, 5, 6, 7, 8, 9}; >> xss (std::vector<int> &) { 1, 2, 4, 5, 6, 7, 8, 9 } >> >> std::accumulate(xss.begin(), xss.end(), 0, [](int acc, int x){ return 10 * acc + x;}) (int) 12456789 >> // Sum of all elements >> std::accumulate(xss.begin(), xss.end(), 1, [](int acc, int x){ return acc + x;}) (int) 43 >> // Product of all elements >> std::accumulate(xss.begin(), xss.end(), 1, [](int acc, int x){ return acc * x;}) (int) 120960 >>
1.3.16 adjacent different
- header: <numeric>
- https://en.cppreference.com/w/cpp/algorithm/adjacent_difference
>> std::vector<int> v{2, 4, 56, 10, 25, 60}; >> std::deque<int> d(v.size()); >> std::adjacent_difference(v.begin(), v.end(), d.begin()) (std::_Deque_iterator<int, int &, int *>) @0x3c84010 >> d (std::deque<int> &) { 2, 2, 52, -46, 15, 35 } >>
1.3.17 max_element and min_element
Max element iterator -> Get the maximum element of an STL-like container/collection.
References:
Usage:
- Note: T is the type of container elements.
max_element(iterator Begin, iterator End) -> iterator max_element(iterator Begin, iterator End, Comparator comp) -> iterator
Example:
std::vector<double> xs = {-1.2, -50.0, 100.0, -4.2, 105, -200.423}; auto it = std::max_element(xs.begin(), xs.end()); >> *it (double) 105.00000 >> for(; it != xs.end(); it++){ std::cout << *it << "\n"; } >> for(; it != xs.end(); it++){ std::cout << *it << "\n"; } 105 -200.423 >> // Find maximum element with custom comparator auto it2 = std::max_element(xs.begin(), xs.end(), [](double x, double y){ return std::abs(x) < std::abs(y);} ) >> *it2 (double) -200.42300 >> >> >> for(; it2 != xs.end(); it2++){ std::cout << *it2 << "\n"; } -200.423 -200.423 >> >> xs.clear() >> xs (std::vector<double> &) {} >> auto it3 = std::max_element(xs.begin(), xs.end(), [](double x, double y){ return std::abs(x) < std::abs(y);}); // If returns true, then no value is found. >> it3 == xs.end() (bool) true >> it3 != xs.end() (bool) false
1.4 Implementing custom algorithms
1.4.1 Example - Implement algorithm similar to std::for_each
- File: algorithm_for_each.cpp
Headers:
#include <iostream> #include <iomanip> #include <vector> #include <array> #include <list> #include <cassert>
Functions:
// Similar to std::for_each - using iterator template<typename Iterator, typename Callable> void for_each_iterator(Iterator begin, Iterator end, Callable&& callable) { size_t index = 0; for(auto it = begin; it != end; ++it) callable(*it, index++); } // Similar to std::for_each - using range template<typename Container, typename Callable> void for_each_range(Container const& container, Callable&& callable) { size_t index = 0; for(auto& x: container) callable(x, index++); }
Convenience classes:
template<typename T, std::size_t N> class ArrayView{ public: template<typename U> using Iterator_t = decltype(std::begin(std::declval<U>())); using value_type = T; ArrayView(T (& arr) [N]) : m_begin{ std::begin(arr) } ,m_end{ std::end(arr) } { } auto begin() const { return m_begin; } auto end() const { return m_end; } private: Iterator_t<T(&)[N]> m_begin; Iterator_t<T(&)[N]> m_end; }; struct Functor{ std::string m_name; Functor(std::string name) : m_name(std::move(name)){ } void operator() (std::string const& str, size_t index) { std::cout << " ARR<" << m_name << "> [" << index << "] = " << str << "\n"; } };
Main function:
int main(int argc, char** argv) { std::cout << "\n === EXPERIMENT 1.A ==================" << std::endl; int arr1 [] = { 3, 10, -90, 100, 300}; for_each_iterator(std::begin(arr1), std::end(arr1), [](auto x, size_t index) { std::cout << " x[" << index << "] = " << x << "\n"; }); std::cout << "\n === EXPERIMENT 1.B ==================" << std::endl; for_each_range(ArrayView(arr1), [](auto x, size_t index) { std::cout << " x[" << index << "] = " << x << "\n"; }); std::cout << "\n === EXPERIMENT 2.A ==================" << std::endl; std::vector<std::string> vecA = {"C++", "C++17", "ADA Spark", "Rust", "C", "C11"}; for_each_iterator( vecA.begin(), vecA.end() ,[](auto x, size_t index) { std::cout << " x[" << index << "] = " << x << "\n"; }); std::cout << "\n === EXPERIMENT 2.A ==================" << std::endl; for_each_range(vecA, Functor("VecA")); return 0; }
Program output:
=== EXPERIMENT 1.A ================== x[0] = 3 x[1] = 10 x[2] = -90 x[3] = 100 x[4] = 300 === EXPERIMENT 1.B ================== x[0] = 3 x[1] = 10 x[2] = -90 x[3] = 100 x[4] = 300 === EXPERIMENT 2.A ================== x[0] = C++ x[1] = C++17 x[2] = ADA Spark x[3] = Rust x[4] = C x[5] = C11 === EXPERIMENT 2.A ================== ARR<VecA> [0] = C++ ARR<VecA> [1] = C++17 ARR<VecA> [2] = ADA Spark ARR<VecA> [3] = Rust ARR<VecA> [4] = C ARR<VecA> [5] = C11
1.4.2 Example - Sum of container elements
File: sum_algorithm.cpp
#include <iostream> #include <iomanip> #include <vector> #include <array> #include <list> #include <cassert> template<typename Iterator, typename Acc = typename Iterator::value_type> auto sum_of_elementsA(Iterator begin, Iterator end, Acc const& init = {}) -> Acc { Acc acc = init; for(auto it = begin; it != end; it++) { acc = acc + *it; } return acc; } template<typename Container> typename Container::value_type sum_of_elementsB(Container const& container , typename Container::value_type const& init) { typename Container::value_type acc = init; for(auto const& elem: container) { acc = acc + elem; } return acc; } template<typename T, std::size_t N> class ArrayView{ public: template<typename U> using Iterator_t = decltype(std::begin(std::declval<U>())); using value_type = T; ArrayView(T (& arr) [N]) : m_begin{ std::begin(arr) } ,m_end{ std::end(arr) } { } auto begin() const { return m_begin; } auto end() const { return m_end; } private: Iterator_t<T(&)[N]> m_begin; Iterator_t<T(&)[N]> m_end; }; int main(int argc, char** argv) { int arr1 [] = { 3, 10, -90, 100, 300}; assert(sum_of_elementsA(std::begin(arr1), std::end(arr1), 0) == 323 ); assert(sum_of_elementsB(ArrayView(arr1), 0) == 323); std::vector<int> vecA = { 10, 20, 50, 60, 90, 100}; assert(sum_of_elementsA(vecA.begin(), vecA.end(), 0) == 330); assert(sum_of_elementsB(vecA, 0) == 330 ); std::array<int, 10> cppArr1 = { 10, -20, -50, 60, 90, 100}; assert(sum_of_elementsA(cppArr1.begin(), cppArr1.end(), 0) == 190); assert(sum_of_elementsB(cppArr1, 0) == 190); std::list<int> list1 = { 10, -20, -50, 60, 90, 100}; list1.push_back(20); list1.push_back(50); assert(sum_of_elementsA(list1.begin(), list1.end(), 0) == 190 + 70); assert(sum_of_elementsB(list1, 60) == 190 + 70 + 60); std::cout << " [INFO] All tests passed. OK" << std::endl; return 0; }
Program output:
[INFO] All tests passed. OK
1.4.3 Example - Algorithm for filling a container
File: algorithm_fillcontainer.cpp
#include <iostream> #include <iomanip> #include <vector> #include <array> #include <list> #include <cassert> template<typename Flt, typename Iterator> void fill_container(Iterator begin, Iterator end, Flt start, Flt step) { Flt x = start; for(auto it = begin; it != end; it++){ *it = x; x = x + step; } } template<typename Flt, typename Container> void fill_container(Container& container, Flt start, Flt step) { Flt x = start; for(auto& elem: container){ elem = x; x = x + step; } } int main(int argc, char** argv) { std::array<int, 10> xs1{}; fill_container(xs1.begin(), xs1.end(), -10, 2); bool res1 = xs1 == std::array<int, 10>{-10, -8, -6, -4, -2, 0, 2, 4, 6, 8}; assert(res1); std::vector<int> xs2(10, 0); fill_container(xs2, -10, 1); bool res2 = xs2 == std::vector<int>{-10, -9, -8, -7, -6, -5, -4, -3, -2, -1}; assert(res2); std::cout << " [RESULT] All tests passed OK" << std::endl; return 0; }
Program output:
[RESULT] All tests passed OK