stl help needed

[DJ Dharme]

Hi,
I really like to use stl as much as possible in my code. But I
found it really hard to understand by looking into there source code.
I have no idea about what iterator traits, heaps and allocators are.
So I started to write my own container class to learn templates. I
thought about a sorted vector class which have a additional two
methods sort and insert sorted. The usage of this class is like this.

1. We can reserve some space and push all the items to the vector and
then do a sort.
2. We can insert a new item to a sorted vector by using a binary
search.

Here is my initial code. Can somebody help me to modify it so that I
can understand the concepts behind stl. How can I use allocators,
iterator traits in this class?

#include <algorithm>
#include <string.h>

template<typename T, typename Cmp>
class sorted_vector
{
public:
typedef T value_type;
typedef Cmp compare_type;
typedef value_type& reference_type;
typedef value_type* pointer_type;
typedef pointer_type iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;

sorted_vector(const compare_type& pred = Cmp())
:_cmp(pred), _array(0), _capacity(0), _size(0)
{
}

~sorted_vector()
{
clear();
}

iterator begin()
{
return _array;
}

iterator end()
{
return (_array + _size);
}

void reserve(size_type size)
{
_allocate(size);
_capacity = size;
}

void push_back(const T& val)
{
insert(end(), val);
}

void push_front(const T& val)
{
insert(begin(), val);
}

void insert(iterator pos, const T& val)
{
difference_type index = (pos - begin());
pointer_type new_array = _allocate_on_insert();

if(index == 0)
{
if(new_array)
{
_copy(new_array + 1, _array, _array + _size);
_deallocate(_array);
_array = new_array;
}
else
{
_move(_array + 1, _array, _size);
}
}
else if(index == _size)
{
if(new_array)
{
_copy(new_array, _array, _array + index);
_deallocate(_array);
_array = new_array;
}
}
else
{
if(new_array)
{
_copy(new_array, _array, _array + index);
_copy(new_array + index + 1, _array + index, _array + _size);
_deallocate(_array);
_array = new_array;
}
else
{
_move(_array + index + 1, _array + index, _size - index);
}
}

_array[index] = val;
++_size;
}

void pop_back()
{
erase(end() - 1);
}

void pop_front()
{
erase(begin());
}

void erase(iterator pos)
{
difference_type index = (pos - begin());

if(index < _size)
{
_move(_array + index, _array + index + 1, _size - index - 1);
--_size;
}
}

void insert_sorted(const T& val)
{
insert(std::lower_bound(begin(), end(), val, _cmp), val);
}

void sort()
{
std::sort(begin(), end(), _cmp);
}

reference_type operator[](size_type index)
{
return _array[index];
}

size_type size() const
{
return _size;
}

size_type capacity() const
{
return _capacity;
}

void clear()
{
_deallocate(_array);
_array = 0;
_size = 0;
_capacity = 0;
}

protected:

pointer_type _allocate(size_type size)
{
return new value_type[size];
}

void _deallocate(pointer_type p)
{
delete[] p;
}

pointer_type _allocate_on_insert()
{
size_type new_size = _size + 1;

if(new_size >= _capacity)
{
_capacity = new_size * 2;
return _allocate(_capacity);
}

return 0;
}

void _move(pointer_type to, pointer_type from, size_type count)
{
memmove(to, from, count * sizeof(value_type));
}

void _copy(pointer_type dest_begin, pointer_type src_begin,
pointer_type src_end)
{
memcpy(dest_begin, src_begin, (src_end - src_begin) *
sizeof(value_type));
}

compare_type _cmp;
pointer_type _array;
size_type _capacity;
size_type _size;
};

 

[Salt_Peter]

Hi,
       I really like to use stl as much as possible in my code. But I
found it really hard to understand by looking into there source code.
I have no idea about what iterator traits, heaps and allocators are.
So I started to write my own container class to learn templates. I
thought about a sorted vector class which have a additional two
methods sort and insert sorted. The usage of this class is like this.

1. We can reserve some space and push all the items to the vector and
then do a sort.
2. We can insert a new item to a sorted vector by using a binary
search.

Here is my initial code. Can somebody help me to modify it so that I
can understand the concepts behind stl. How can I use allocators,
iterator traits in this class?

[ snip ]

Why aren't you using a std::vector in your type instead of reinventing
the wheel?
The type's name is missleading to me unless you sort upon insertion
(in which case you then have an associative container, see std::set<

).

#include <iostream>
#include <ostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

template < typename T, typename Predicate = std::less< T > >
class sorted_vector
{
std::vector< T > m_vt;
public:
sortable_vector() : m_vt() { }
// member functions
void push_back( const T& r_t )
{
m_vt.push_back( r_t );
}
void sort()
{
std::sort( m_vt.begin(), m_vt.end() );
}
// iteration
typedef typename std::vector< T >::iterator iterator;
iterator begin() { return m_vt.begin(); }
iterator end() { return m_vt.end(); }
typedef typename std::vector< T >::const_iterator const_iterator;
const_iterator begin() const { return m_vt.begin(); }
const_iterator end() const { return m_vt.end(); }
// friend op<<
friend
std:stream&
operator<<( std:stream& os, const sorted_vector< T >& sv )
{
std::copy( sv.begin(),
sv.end(),
std:stream_iterator< T >(os, "\n") );
return os;
}
};

int main()
{
sortable_vector< std::string > strings;
strings.push_back("bbb bbb");
strings.push_back("aaa aaa");
strings.push_back("ccc ccc");

std::cout << strings << std::endl;

strings.sort();
std::cout << strings << std::endl;

std::cout << "Press ENTER to EXIT.\n";
std::cin.get();
}

/*
bbb bbb
aaa aaa
ccc ccc

aaa aaa
bbb bbb
ccc ccc
*/

As far as iterator traits are concerned, you worry about
iterator_tag(s) when some templated algorithm has specializations for
the different types of iterators (random access iterators, input
iterators, output iterators, etc).

 

[annamalai]

Hi,
       I really like to use stl as much as possible in my code. But I
found it really hard to understand by looking into there source code.
I have no idea about what iterator traits, heaps and allocators are.

Iterators have associated types. The std::iterator_traits<> class
helps to access those associated types. The associated types are

1. value type
2. pointer type
3. reference type
4. distance type
5. iterator category

Check the following URL for details:

http://www.sgi.com/tech/stl/iterator_traits.html

It is not possible to learn C++ via newsgroups. You would be better
off reading a good C++ book (eg. Accelerated C++ http://www.acceleratedcpp.com).

Rgds,
anna

 

[Juha Nieminen]

I really like to use stl as much as possible in my code. But I
found it really hard to understand by looking into there source code.
I have no idea about what iterator traits, heaps and allocators are.

You don't need to know what iterator traits, heaps or allocators are
in order to *use* the STL (which is what you are saying above).

Or do you mean that you want to create your own data container which
works in the same way as the standard library data containers?

 

[DJ Dharme]

do you mean that you want to create your own data container which

works in the same way as the standard library data containers?

Yes my intension was to write my own container class (a modified set)
which supports dynamic order statistics (which allows me to access
items by it's index in lgN time instead of N time).

Why aren't you using a std::vector in your type instead of reinventing
the wheel?

I have no intension of re-writing a vector class, I am just writing it
to learn stl as it was the simplest container class that I could
imagine.

The type's name is misleading to me unless you sort upon insertion

Hmm.., I thought someone would like to put all the elements at once
(without sorting) and the do a single sort as it would be more optimum
than sort upon insertion. But there is also an option to sort upon
insertion if you want (which assumes the current elements are already
in the sorted order). May be you were curious about the other insert
option ?

Thanks everyone for the support!

DJD

 

[DJ Dharme]

http://www.amazon.co.uk/C-Standard-Library-Tutorial-Reference/dp/0201...

This book rocks, thanks you very much OU

Regards,
DJD

 

[James Kanze]

You don't need to know what iterator traits, heaps or
allocators are in order to *use* the STL (which is what you
are saying above).

Or do you mean that you want to create your own data container
which works in the same way as the standard library data
containers?

Isn't this really mainly an issue of providing standard
conformant iterators? I know that the standard does specify a
certain number of container requirements, but I don't see any
place in the standard which depends on them being implemented in
other containers. All of the use of arbitrary containers in the
standard is via iterators. (Almost---the container adapters
would be an exception.)

At any rate, if I were implementing a standard-like container,
I'd certainly concentrate on making the iterators conform. I'd
throw in the relevant typedef's, and use the same names for the
member functions, because that doesn't cost anything; I'd even
model my choice of functions after the standard, providing not
just insert() and erase(), but push_back(), for example, and
back() and front(), if relevant. But I wouldn't waste my time
worrying about allocators, and providing an allocator template
parameter. (For that matter, I'm not alone, since the next
version of the standard will have std::array, which won't have
an allocator either.)

 

[DJ Dharme]

At any rate, if I were implementing a standard-like container,
I'd certainly concentrate on making the iterators conform.  I'd
throw in the relevant typedef's, and use the same names for the
member functions, because that doesn't cost anything; I'd even
model my choice of functions after the standard, providing not
just insert() and erase(), but push_back(), for example, and
back() and front(), if relevant.

--
James Kanze (GABI Software)             email:[email protected]
Conseils en informatique orientée objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Thanks James, that is exactly what I was trying to do.

 

[Juha Nieminen]

But I wouldn't waste my time
worrying about allocators, and providing an allocator template
parameter. (For that matter, I'm not alone, since the next
version of the standard will have std::array, which won't have
an allocator either.)

I know from your past posts in this newsgroups that, for whatever
reason, you do not believe allocators can be used to make existing data
containers more efficient (speedwise, memorywise, or both), regardless
of all the evidence of the contrary. I don't really understand why you
have this firm opinion, given that it would be so easy to test for yourself.

If standard containers stopped supporting user-defined allocators,
that would certainly be a setback in versatility. I don't really
understand why support for them should be dropped. It's not like you
would have to care about them (or even know about their existence) if
you don't use them.