Subclassing Off Of Vector

[jackstah]

I've read before that subclassing off of std::vector is a bad idea
because it's a concrete class. I understand, but there shouldnt be any
issues with this. I just wanted to do a simple example in my project
to combine templates and inheritance so that I would brush up on both.

I have data that is mostly sorted, but there might be some flipflops
here and there. Thus I've subclassed off of vector, and written a
class that, given a comparison function, inserts in sorted order by
linear searching from the back. This is better for me than a b-search
because 99% of the time I want to push_back, and even if I don't, its
just one or two back. Since the class is so short, I include the whole
thing:

*************

#include <vector>

using namespace std;
template <class T>
class SortedVector : public vector<T> {

typedef int (*cmpFn)(const T&, const T&);
public:
SortedVector(cmpFn func) : vector<T>(), myFunc(func) {}
~SortedVector() {}

void push(const T& elem) {
vector<T>::iterator iter = end();
for (int i = vector<T>::size() - 1; i >= 0; i--) {
if (myFunc(vector<T>:perator[](i), elem) >= 0) {
vector<T>::insert(iter, elem);
return;
}
iter--;
}
vector<T>::insert(iter, elem);
}

private:
cmpFn myFunc;

};

************

My problem is with the iterators. I get two errors: "iter was not
declared in this scope" (at every all to iter), and "expected ; before
iter" (in what should be the declaration). I tried initially using
just int's (i.e. insert(i + 1, elem)) but that didn't work either.
Without shifting to the encapsualtion paradigm, what can I do?

 

[Daniel T.]

I've read before that subclassing off of std::vector is a bad idea
because it's a concrete class. I understand, but there shouldnt be any
issues with this. I just wanted to do a simple example in my project
to combine templates and inheritance so that I would brush up on both.

I would either inherit privately, or contain a vector.

I have data that is mostly sorted, but there might be some flipflops
here and there. Thus I've subclassed off of vector, and written a
class that, given a comparison function, inserts in sorted order by
linear searching from the back. This is better for me than a b-search
because 99% of the time I want to push_back, and even if I don't, its
just one or two back. Since the class is so short, I include the whole
thing:

*************

#include <vector>

using namespace std;
template <class T>
class SortedVector : public vector<T> {

typedef int (*cmpFn)(const T&, const T&);
public:
SortedVector(cmpFn func) : vector<T>(), myFunc(func) {}
~SortedVector() {}

void push(const T& elem) {
vector<T>::iterator iter = end();
for (int i = vector<T>::size() - 1; i >= 0; i--) {
if (myFunc(vector<T>:perator[](i), elem) >= 0) {
vector<T>::insert(iter, elem);
return;
}
iter--;
}
vector<T>::insert(iter, elem);
}

private:
cmpFn myFunc;

};

************

My problem is with the iterators. I get two errors: "iter was not
declared in this scope" (at every all to iter), and "expected ; before
iter" (in what should be the declaration). I tried initially using
just int's (i.e. insert(i + 1, elem)) but that didn't work either.
Without shifting to the encapsualtion paradigm, what can I do?

typename vector<T>::iterator

 

[David Harmon]

On 8 Aug 2006 11:31:37 -0700 in comp.lang.c++, (e-mail address removed)
wrote,

vector<T>::iterator iter = end();

Should be:
typename vector<T>::iterator iter = end();

(Don't know if that will solve your whole problem.)

 

[Cy Edmunds]

I've read before that subclassing off of std::vector is a bad idea
because it's a concrete class. I understand, but there shouldnt be any
issues with this. I just wanted to do a simple example in my project
to combine templates and inheritance so that I would brush up on both.

I have data that is mostly sorted, but there might be some flipflops
here and there. Thus I've subclassed off of vector, and written a
class that, given a comparison function, inserts in sorted order by
linear searching from the back. This is better for me than a b-search
because 99% of the time I want to push_back, and even if I don't, its
just one or two back. Since the class is so short, I include the whole
thing:

*************

#include <vector>

using namespace std;
template <class T>
class SortedVector : public vector<T> {

typedef int (*cmpFn)(const T&, const T&);
public:
SortedVector(cmpFn func) : vector<T>(), myFunc(func) {}
~SortedVector() {}

void push(const T& elem) {
vector<T>::iterator iter = end();
for (int i = vector<T>::size() - 1; i >= 0; i--) {
if (myFunc(vector<T>:perator[](i), elem) >= 0) {
vector<T>::insert(iter, elem);
return;
}
iter--;
}
vector<T>::insert(iter, elem);
}

private:
cmpFn myFunc;

};

************

My problem is with the iterators. I get two errors: "iter was not
declared in this scope" (at every all to iter), and "expected ; before
iter" (in what should be the declaration). I tried initially using
just int's (i.e. insert(i + 1, elem)) but that didn't work either.
Without shifting to the encapsualtion paradigm, what can I do?

Now you have another class which is the same as std::vector except it
implements your favorite algorithm. When you come up with a second algorithm
are you going to invert a third class? This is a Bad Idea.

Another way to look at is this: what does data storage have to do with a
specific way to keep things sorted? Abolutely nothing.

Algorithms in C++ are best coded as functions if at all possible. For
instance:

template <typename COLL, typename OP>
void
insert_sorted(COLL &c, typename COLL::value_type elem, OP op)
{
typename COLL::iterator i = c.end();
typename COLL::iterator k = i;
--k;
for (typename COLL::size_type j = 0; j < c.size(); ++j)
{
if (op(*k, elem))
{
c.insert(i, elem);
return;
}
--i;
--k;
}
c.insert(c.begin(), elem);
}

(untested)

If this works at all it will work with std::list and std::deque as well as
std::vector. You can use std::greater<> and std::less<> to get decreasing or
increasing sort order. To use it call

std::less<int> op;
insert_sorted(my_vector, 2, op);
insert_sorted(my_vector, 7, op);

and so forth. If you come up with a second algorithm you can code it the
same way without generating spurious classes.

Cy