main.cc:
#include <cstdio> #include <functional> #include "segtree.h" // NOLINT int main() { const int n = 8; SegmentTree<int> segmentTree(n, 1, std::multiplies<int>()); for (int i = 0; i < n; ++i) segmentTree.set(i, i + 1); for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) { int s = segmentTree.get(i, j); std::printf( "Function applied from data[%d] to data[%d] is equal to %d \n", i, j, s); } return 0; }
segtree.h: #ifndef SEGTREE_H _ // NOLINT #define SEGTREE_H _
#include <cassert> #include <functional> #include <vector> template <typename T> class SegmentTree { private: std::vector<T> tree; int levels; int n; int el; std::function<T(T, T)> f; T query(int l, int r, int st, int fi) { if (l == r) return get(l); int mid = (st + fi + 1) / 2; if (r < mid) { return query(l, r, st, mid - 1); } else if (l >= mid) { return query(l, r, mid, fi); } else { T left = query(l, mid - 1, st, mid - 1); T right = query(mid, r, mid, fi); return f(left, right); } } public: SegmentTree(const std::vector<T>& data, std::function<T(T, T)> f = std::plus <T>()) { this->f = f; this->n = data.size(); // build tree levels = 1, el = 1; while (el < static_cast<int>(data.size())) { el <<= 1; ++levels; } tree.assign(2 * el, T()); for (size_t i = 0; i < data.size(); ++i) tree[i + el - 1] = data[i]; for (int i = el - 2; i >= 0; --i) tree[i] = f(tree[2 * i + 1], tree[2 * i + 2]); } SegmentTree(int n, T val = T(), std::function<T(T, T)> f = std::plus <T>()) : SegmentTree(std::vector<T>(n, val), f) { } T get(int l, int r) { return query(l, r, 0, n); } T get(int index) { return tree[el - 1 + index]; } void set(int index, T value) { int i = el - 1 + index; tree[i] = value; do { i = (i-1) / 2; tree[i] = f(tree[i*2 + 1], tree[i*2 + 2]); } while (i > 0); } };
Error information after g++ main.cc :
In file included from main.cc:9:0: segtree.h:22:3: error: 'function' in namespace 'std' does not name a type segtree.h:42:12: error: 'std::function' has not been declared segtree.h:42:20: error: expected ',' or '...' before '<' token segtree.h:60:12: error: 'std::function' has not been declared segtree.h:60:20: error: expected ',' or '...' before '<' token segtree.h:59:3: error: default argument missing for parameter 3 of 'SegmentTree<T>::SegmentTree(int, T, int)' segtree.h: In constructor 'SegmentTree<T>::SegmentTree(const std::vector<T>&, int)': segtree.h:43:15: error: 'f' was not declared in this scope segtree.h: In constructor 'SegmentTree<T>::SegmentTree(int, T, int)': segtree.h:61:45: error: 'f' was not declared in this scope main.cc: In function 'int main()': main.cc:14:29: error: no matching function for call to 'SegmentTree<int>::SegmentTree(const int&, int, std::multiplies<int>)' main.cc:14:29: note: candidates are: segtree.h:59:3: note: SegmentTree<T>::SegmentTree(int, T, int) [with T = int] segtree.h:59:3: note: no known conversion for argument 3 from 'std::multiplies<int>' to 'int' segtree.h:41:3: note: SegmentTree<T>::SegmentTree(const std::vector<T>&, int) [with T = int] segtree.h:41:3: note: candidate expects 2 arguments, 3 provided segtree.h:16:7: note: SegmentTree<int>::SegmentTree(const SegmentTree<int>&) segtree.h:16:7: note: candidate expects 1 argument, 3 provided In file included from main.cc:9:0: segtree.h: In member function 'void SegmentTree<T>::set(int, T) [with T = int]': main.cc:16:29: instantiated from here segtree.h:78:7: error: 'f' was not declared in this scope segtree.h: In member function 'T SegmentTree<T>::query(int, int, int, int) [with T = int]': segtree.h:66:28: instantiated from 'T SegmentTree<T>::get(int, int) [with T = int]' main.cc:20:35: instantiated from here segtree.h:36:27: error: 'f' was not declared in this scope
I got this piece of code from github, but I'm not very familiar with C ++. Can anyone help?