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

Sequence Class

P: n/a
hello,

I have to implement a sequence class, however the header file is
predefined

Expand|Select|Wrap|Line Numbers
  1. class sequence
  2. {
  3. public:
  4. // TYPEDEFS and MEMBER CONSTANTS
  5. typedef double value_type;
  6. typedef std::size_t size_type;
  7. static const size_type DEFAULT_CAPACITY = 30;
  8. // CONSTRUCTORS and DESTRUCTOR
  9. sequence(size_type initial_capacity = DEFAULT_CAPACITY);
  10. sequence(const sequence& source);
  11. ~sequence( );
  12. // MODIFICATION MEMBER FUNCTIONS
  13. void resize(size_type new_capacity);
  14. void start( );
  15. void advance( ); //set the current_index to the next number in
  16. the array
  17. void insert(const value_type& entry); //insert before the
  18. number with the current index
  19. void attach(const value_type& entry); //insert after the number
  20. with the current index
  21. void remove_current( );
  22. void operator =(const sequence& source);
  23. // CONSTANT MEMBER FUNCTIONS
  24. size_type size( ) const;
  25. bool is_item( ) const;
  26. value_type current( ) const;
  27. private:
  28. value_type* data; //das array mit den zahlen drinnen
  29. size_type used; //wieviele zahlen in dem array stehen
  30. size_type current_index;
  31. size_type capacity;
  32. };
  33.  
Unfortunately, I guess something is wrong with the copy constructor, or
the insert, attach or resize function:
Expand|Select|Wrap|Line Numbers
  1. sequence::sequence(const sequence& source)
  2. {
  3. data = new value_type[source.capacity];
  4. capacity = source.capacity;
  5. used = source.used;
  6. current_index = source.current_index;
  7. copy(source.data, source.data + used, data);
  8. }
  9.  
Here the insert, attach and resize function:
Expand|Select|Wrap|Line Numbers
  1.  
  2. void sequence::insert(const value_type& entry)
  3. {
  4. if(used == capacity)
  5. resize(used);
  6.  
  7. if(!(is_item()))
  8. current_index = 0;
  9.  
  10. for(int i = used; i current_index; i--)
  11. {
  12. data[i] = data[i-1];
  13. }
  14. data[current_index] = entry;
  15. ++used;
  16. }
  17.  
  18. void sequence::attach(const value_type& entry)
  19. {
  20. if(used == capacity)
  21. resize(used);
  22.  
  23. if(current_index >= used)
  24. {
  25. start();
  26. advance();
  27. advance();
  28. }
  29. if(used!=0)
  30. {
  31. for(int i = used; i current_index+1; i--)
  32. {
  33. data[i] = data[i-1];
  34. }
  35. data[current_index+1] = entry;
  36. current_index++;
  37. }
  38. else
  39. {
  40. data[current_index] = entry;
  41. }
  42. ++used;
  43. }
  44.  
  45. void sequence::resize (size_type new_capacity)
  46. {
  47. value_type* larger_array;
  48.  
  49. if(new_capacity < used)
  50. new_capacity = used;
  51.  
  52. larger_array = new value_type[new_capacity];
  53. copy(data, data + used + current_index, larger_array);
  54. delete[] data;
  55. data = larger_array;
  56. capacity = new_capacity;
  57. }
  58.  
Has anybody an idea what went wrong here? I am working on the problem
fixing for such a long time but I haven't found the error yet...:((

pat

Sep 27 '06 #1
Share this Question
Share on Google+
14 Replies


P: n/a
pat270881 wrote:
hello,

I have to implement a sequence class, however the header file is
predefined

[large amount of code redacted]

Has anybody an idea what went wrong here? I am working on the problem
fixing for such a long time but I haven't found the error yet...:((
Well, you didn't tell us what you were expecting, or what results you
got that were different from what you were expecting. Tell us that, and
maybe we can help.

Until then, you have an error on line 42 of your code.
Sep 27 '06 #2

P: n/a
pat270881 wrote:
I have to implement a sequence class, however the header file is
predefined
[...]
Unfortunately, I guess something is wrong with the copy constructor, or
the insert, attach or resize function:
[...]
We're not here to do your homework for you (see
http://parashift.com/c++-faq-lite/ho....html#faq-5.2). If you
post a minimal but complete sample that demonstrates what problem
you're talking about (see
http://parashift.com/c++-faq-lite/ho...t.html#faq-5.8) and ask
specific questions about the language (not "what's wrong with this?"),
then we can try to help you.

Cheers! --M

Sep 27 '06 #3

P: n/a

Sorry for that I tried to execute this test-program:

[/code]
int test5( )
{
sequence original; // A sequence that we'll copy.
double items[2*original.DEFAULT_CAPACITY];
size_t i;

// Set up the items array to conatin 1...2*DEFAULT_CAPACITY.
for (i = 1; i <= 2*original.DEFAULT_CAPACITY; i++)
items[i-1] = i;

// Test copying of an empty sequence. After the copying, we change
the original.
cout << "Copy constructor test: for an empty sequence." << endl;
sequence copy1(original);
original.attach(1); // Changes the original sequence, but not the
copy.
if (!correct(copy1, 0, 0, items)) return 0;

// Test copying of a sequence with current item at the tail.
cout << "Copy constructor test: for a sequence with cursor at
tail." << endl;
for (i=2; i <= 2*original.DEFAULT_CAPACITY; i++)
original.attach(i);
cout << "SIZE: " << original.size() << endl;
sequence copy2(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy2, 2*original.DEFAULT_CAPACITY,
2*original.DEFAULT_CAPACITY-1, items)
)
return 0;

// Test copying of a sequence with cursor near the middle.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);
for (i = 1; i < original.DEFAULT_CAPACITY; i++)
original.advance( );
// Cursor is now at location [DEFAULT_CAPACITY] (counting [0] as
the first spot).
sequence copy3(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy3, 2*original.DEFAULT_CAPACITY, original.DEFAULT_CAPACITY,
items)
)
return 0;

// Test copying of a sequence with cursor at the front.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);
original.start( );
// Cursor is now at the front.
sequence copy4(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy4, 2*original.DEFAULT_CAPACITY, 0, items)
)
return 0;

// Test copying of a sequence with no current item.
cout << "Copy constructor test: for a sequence with no current
item." << endl;
original.insert(2);
while (original.is_item( ))
original.advance( );
// There is now no current item.
sequence copy5(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy5, 2*original.DEFAULT_CAPACITY,
2*original.DEFAULT_CAPACITY, items)
)
return 0;
}
[/code]

After this line cout << "Copy constructor test: for a sequence with
cursor near middle." << endl; the programm breaks and a pop-window
appears where it is quoted that TestApplication.exe has detected a
problem and has to be finished.

I think the actual error occurs at the original.insert(2); line.
Does andybody know now what went wrong...? :(

pat

Sep 27 '06 #4

P: n/a
pat270881 wrote:
Sorry for that I tried to execute this test-program:

[/code]
int test5( )
{
sequence original; // A sequence that we'll copy.
double items[2*original.DEFAULT_CAPACITY];
size_t i;

// Set up the items array to conatin 1...2*DEFAULT_CAPACITY.
for (i = 1; i <= 2*original.DEFAULT_CAPACITY; i++)
items[i-1] = i;

// Test copying of an empty sequence. After the copying, we change
the original.
cout << "Copy constructor test: for an empty sequence." << endl;
sequence copy1(original);
original.attach(1); // Changes the original sequence, but not the
copy.
if (!correct(copy1, 0, 0, items)) return 0;

// Test copying of a sequence with current item at the tail.
cout << "Copy constructor test: for a sequence with cursor at
tail." << endl;
for (i=2; i <= 2*original.DEFAULT_CAPACITY; i++)
original.attach(i);
cout << "SIZE: " << original.size() << endl;
sequence copy2(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy2, 2*original.DEFAULT_CAPACITY,
2*original.DEFAULT_CAPACITY-1, items)
)
return 0;

// Test copying of a sequence with cursor near the middle.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);
for (i = 1; i < original.DEFAULT_CAPACITY; i++)
original.advance( );
// Cursor is now at location [DEFAULT_CAPACITY] (counting [0] as
the first spot).
sequence copy3(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy3, 2*original.DEFAULT_CAPACITY, original.DEFAULT_CAPACITY,
items)
)
return 0;

// Test copying of a sequence with cursor at the front.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);
original.start( );
// Cursor is now at the front.
sequence copy4(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy4, 2*original.DEFAULT_CAPACITY, 0, items)
)
return 0;

// Test copying of a sequence with no current item.
cout << "Copy constructor test: for a sequence with no current
item." << endl;
original.insert(2);
while (original.is_item( ))
original.advance( );
// There is now no current item.
sequence copy5(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy5, 2*original.DEFAULT_CAPACITY,
2*original.DEFAULT_CAPACITY, items)
)
return 0;
}
[/code]

After this line cout << "Copy constructor test: for a sequence with
cursor near middle." << endl; the programm breaks and a pop-window
appears where it is quoted that TestApplication.exe has detected a
problem and has to be finished.

I think the actual error occurs at the original.insert(2); line.
Does andybody know now what went wrong...? :(
Sorry. It still isn't minimal but complete. In particular where are the
other functions, such as sequence::start()?

Regardless of that, however, this is a clear case where you need to
learn to use your debugger to step through the code. In particular,
make sure that you are not attempting to write to a memory location
past the end of your allocated array.

Again, if you have a specific language question, we'd be happy to try
to answer it, but we're not here to do your homework for you.

Cheers! --M

Sep 27 '06 #5

P: n/a

I already tried to debug it and the error was a bad_alloc error so that
I write out of the heap. But I simply do not know why this
happens...?:((

here the other functions of my sequenceimple file:

Expand|Select|Wrap|Line Numbers
  1. sequence::sequence(size_type initial_capacity)
  2. {
  3. data = new value_type[initial_capacity];
  4. capacity = initial_capacity;
  5. used = 0;
  6. current_index = 0;
  7. }
  8.  
  9. sequence::~sequence()
  10. {
  11. delete[] data;
  12. }
  13.  
  14. void sequence::operator = (const sequence& source)
  15. {
  16. value_type* new_data;
  17.  
  18. if (this == &source)
  19. return;
  20.  
  21. if(capacity != source.capacity)
  22. {
  23. new_data = new value_type[source.capacity];
  24. delete[] data;
  25. data = new_data;
  26. capacity = source.capacity;
  27. }
  28.  
  29. used = source.used;
  30. current_index = source.current_index;
  31. copy(source.data, source.data + used, data);
  32. }
  33.  
  34. void sequence::start( )
  35. {
  36. current_index = 0;
  37. }
  38.  
  39. void sequence::advance( )
  40. {
  41. if(is_item())
  42. current_index++;
  43. }
  44.  
  45. void sequence::remove_current( )
  46. {
  47. //cout << current_index << " " << used;
  48. for(int i = current_index; i < used; i++)
  49. {
  50. data[i] = data[i+1];
  51. }
  52. used--;
  53.  
  54. }
  55.  
  56. sequence::value_type sequence::current() const
  57. {
  58. return data[current_index];
  59. }
  60.  
  61. bool sequence::is_item( ) const
  62. {
  63. if(current_index < used)
  64. {
  65. return true;
  66. }
  67. else
  68. {
  69. return false;
  70. }
  71. }
  72.  
  73. sequence::size_type sequence::size() const
  74. {
  75. return used;
  76. }
  77.  
I know that you should not do my homework but I simply see not the
error I made...:(

Sep 27 '06 #6

P: n/a
pat270881 wrote:
I already tried to debug it and the error was a bad_alloc error so that
I write out of the heap. But I simply do not know why this
happens...?:((
Ahh, here's the rub and finally a C++ language question! The bad_alloc
exception is thrown when the new operator can't allocate storage of the
requested size. In short, your memory allocation is failing. Is the
requested size too large perhaps?

Cheers! --M

Sep 27 '06 #7

P: n/a
Ahh, here's the rub and finally a C++ language question! The bad_alloc
exception is thrown when the new operator can't allocate storage of the
requested size. In short, your memory allocation is failing. Is the
requested size too large perhaps?
Yes I know but I simply do not see where I write out of the heap, that
is my big problem...?:(

Sep 27 '06 #8

P: n/a
pat270881 wrote:
Ahh, here's the rub and finally a C++ language question! The bad_alloc
exception is thrown when the new operator can't allocate storage of the
requested size. In short, your memory allocation is failing. Is the
requested size too large perhaps?

Yes I know but I simply do not see where I write out of the heap, that
is my big problem...?:(
You don't get a bad_alloc exception when you go outside the bounds of
your array (well, in theory, I suppose you could since writing there is
technically undefined behavior which could do anything -- but it's
quite unlikely that it would generate bad_alloc). You only get it when
storage cannot be *allocated*. Put a breakpoint on your "new"
statements, and see if that's where things go off into the weeds.

Cheers! --M

Sep 27 '06 #9

P: n/a


I have already debug the program and the error occurs here:

// Test copying of a sequence with cursor near the middle.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);

but I simply don't know why...? :((

Sep 27 '06 #10

P: n/a
pat270881 wrote:
>
I have already debug the program and the error occurs here:

// Test copying of a sequence with cursor near the middle.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);

but I simply don't know why...? :((
No, that's the symptom. Mlimber is telling you that if you see
bad_alloc, that means that new is failing. That's your potential
cause. Don't fixate on what you think is wrong. If you were certain,
you wouldn't have come here. If you ask someone's advice, then listen
to it.

If you're seeing bad_alloc somewhere, that means that new is failing
(not that you're overwriting heap, though that may happen as well). Put
a break point on your new statements, and check that you're passing sane
values as the sizes.

Sep 27 '06 #11

P: n/a
pat270881 wrote:
I have already debug the program and the error occurs here:

// Test copying of a sequence with cursor near the middle.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);

but I simply don't know why...? :((
You are making it too hard to help you. Right now if I wanted to debug
your program, I'd have to collect together several pieces of it from
multiple posts, and then I'd still have to write some code of my own to
have anything that would compile and run.

Your best bet is to post a complete program that demonstrates your
problem. This means that I could copy and paste directly from your
post into my editor, compile, and see your problem (Hint: a complete
program has a main function, and you haven't posted one anywhere).

--
Alan Johnson

Sep 27 '06 #12

P: n/a
pat270881 schrieb:
void sequence::insert(const value_type& entry)
{
if(used == capacity)
resize(used);

if(!(is_item()))
current_index = 0;

for(int i = used; i current_index; i--)
{
data[i] = data[i-1];
}
data[current_index] = entry;
++used;
}
[...]
Has anybody an idea what went wrong here? I am working on the problem
fixing for such a long time but I haven't found the error yet...:((
resize(used);
should be
resize(used+1);

Otherwise you are accessing data[used] in the for-loop, which is one past
the last element.

Why don't you use std::vector?

--
Thomas
http://www.netmeister.org/news/learn2quote.html
Sep 27 '06 #13

P: n/a
Thomas J. Gritzan wrote:
Why don't you use std::vector?
Because this is homework.

Cheers! --M

Sep 28 '06 #14

P: n/a

Sorry, that I cost you so much nerves, that was the error - when a
handed over the used to the resize function I haven't increased the
used, now I use 2*used in insert and attach and now it works :))

Thank you very much for your help!!!

Sep 28 '06 #15

This discussion thread is closed

Replies have been disabled for this discussion.