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 am not very familiar with c++. Can anyone help?
Make sure you have quite new version of g++
and try adding -std=c++11
during compilation:
g++ -std=c++11 main.cc
You need to have at least g++-4.7
to make it work.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With