By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,079 Members | 926 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,079 IT Pros & Developers. It's quick & easy.

stl help needed

P: n/a
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;
};

Oct 29 '08 #1
Share this Question
Share on Google+
7 Replies


P: n/a
On Wed, 29 Oct 2008 09:57:34 -0700, DJ Dharme wrote:
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.
http://www.amazon.co.uk/C-Standard-L...dp/0201379260/

--
OU
Remember 18th of June 2008, Democracy died that afternoon.
http://frapedia.se/wiki/Information_in_English
Oct 29 '08 #2

P: n/a
On Oct 29, 11:57*am, DJ Dharme <donjuandharmap...@gmail.comwrote:
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::ostream&
operator<<( std::ostream& os, const sorted_vector< T >& sv )
{
std::copy( sv.begin(),
sv.end(),
std::ostream_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).
Oct 29 '08 #3

P: n/a
On Oct 29, 11:57*am, DJ Dharme <donjuandharmap...@gmail.comwrote:
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

--
Flow: For Love of Water
http://missingrainbow.blogspot.com/2...-of-water.html
Oct 29 '08 #4

P: n/a
On Oct 29, 10:43*pm, Obnoxious User <O...@127.0.0.1wrote:
On Wed, 29 Oct 2008 09:57:34 -0700, DJ Dharme wrote:
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.

http://www.amazon.co.uk/C-Standard-L...erence/dp/0201...

--
OU
Remember 18th of June 2008, Democracy died that afternoon.http://frapedia..se/wiki/Information_in_English
This book rocks, thanks you very much OU

Regards,
DJD
Oct 30 '08 #5

P: n/a
On Oct 30, 3:46*pm, James Kanze <james.ka...@gmail.comwrote:
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:james.ka...@gmail.com
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.
Oct 30 '08 #6

P: n/a
On 2008-10-30 06:46:22 -0400, James Kanze <ja*********@gmail.comsaid:
(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.)
Hmm, seems like an obvious oversight. std::array does two things: it
provides a fixed size array, and it allocates memory on the stack.
Adding an allocator would allow control over where the array's contents
were allocated, and providing a default allocator could maintain the
current TR1 behavior of allocating on the stack. Of course, you'd have
to be careful not to introduce a non-trivial constructor (since that
would prevent aggregate initialiation), but I'm sure that with some
template magic (enable_if, anyone?) someone could overlay a reasonable
simulation of the current TR1 array. Why didn't the Committee do this?

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Oct 30 '08 #7

P: n/a
James Kanze wrote:
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.

Oct 30 '08 #8

This discussion thread is closed

Replies have been disabled for this discussion.