[Challenge] Container Template Class Improvement
Hi,
(Read the post before looking at the code)
This is the code: https://gist.github.com/rcktscnc/19990f51b9c14f292b75
I came up with the idea of writing my own "vector" template class to learn a bit more about templates in general. The code I will provide is the best I can write at this moment. The "challenge" here is for more experienced people, not for me.
It is important to note that I have never used the template class vector for anything. I wrote this code trying to make my own vector class, and I never looked at the source of vector. All I know about the vector class is the declaration of its members, not the definition of them. I never even looked at them.
All the algorithms in the code came from my head. I didn't steal code from anywhere.
The Purpose of this Thread: Learning
In this thread, I'm asking to be criticized with the hope of learning something.
RULE 1: No libraries allowed
As the purpose is learning, all I'm using in the code are built in keywords. Except for <iostream> -- which was added for testing and will be removed -- there is no library #included in the project. I wanted it to be as raw as possible.
Challenge 1: GOTTA GO FAST
I would like to get opinions on how this template could be written to run as fast as it possibly can, without using any libraries (not even std). You will notice in the code that I added iostream in the beginning of the file. This is only for testing purposes.
Challenge 2: All about the looks
I would also like to get constructive criticism regarding the style of my code, but in a broader sense. Not only regarding naming conventions, but mainly the logic of the algorithms. Maybe I overcomplicated something that could be more simple, for example. Maybe I repeated code that didn't need to be repeated if I created a function for them etc.. If you find things that are too complicated and could be written in a simple way, please mention it.
The Code: The code is too long to be pasted in this thread, so I pasted it in github: https://gist.github.com/rcktscnc/19990f51b9c14f292b75
Expectations: The sad truth
The code is very long. Almost 600 lines. Thus, I'm not expecting everyone to read the whole thing (if you do that, great!). But if you want to criticize a particular function, you can do it. Most of the functions work alone. They communicate with other functions rarely. So if you break the code into each function, you can review one function and post in here!
If I don't get any response in here, I'll look for help in another place. No hard feelings!
Thank you!
(Read the post before looking at the code)
This is the code: https://gist.github.com/rcktscnc/19990f51b9c14f292b75
I came up with the idea of writing my own "vector" template class to learn a bit more about templates in general. The code I will provide is the best I can write at this moment. The "challenge" here is for more experienced people, not for me.
It is important to note that I have never used the template class vector for anything. I wrote this code trying to make my own vector class, and I never looked at the source of vector. All I know about the vector class is the declaration of its members, not the definition of them. I never even looked at them.
All the algorithms in the code came from my head. I didn't steal code from anywhere.
The Purpose of this Thread: Learning
In this thread, I'm asking to be criticized with the hope of learning something.
RULE 1: No libraries allowed
As the purpose is learning, all I'm using in the code are built in keywords. Except for <iostream> -- which was added for testing and will be removed -- there is no library #included in the project. I wanted it to be as raw as possible.
Challenge 1: GOTTA GO FAST
I would like to get opinions on how this template could be written to run as fast as it possibly can, without using any libraries (not even std). You will notice in the code that I added iostream in the beginning of the file. This is only for testing purposes.
Challenge 2: All about the looks
I would also like to get constructive criticism regarding the style of my code, but in a broader sense. Not only regarding naming conventions, but mainly the logic of the algorithms. Maybe I overcomplicated something that could be more simple, for example. Maybe I repeated code that didn't need to be repeated if I created a function for them etc.. If you find things that are too complicated and could be written in a simple way, please mention it.
The Code: The code is too long to be pasted in this thread, so I pasted it in github: https://gist.github.com/rcktscnc/19990f51b9c14f292b75
Expectations: The sad truth
The code is very long. Almost 600 lines. Thus, I'm not expecting everyone to read the whole thing (if you do that, great!). But if you want to criticize a particular function, you can do it. Most of the functions work alone. They communicate with other functions rarely. So if you break the code into each function, you can review one function and post in here!
If I don't get any response in here, I'll look for help in another place. No hard feelings!
Thank you!
| The code is very long. Almost 600 lines. |
First of all: Try to pass your Container instance by const reference and work with it. It is impossible, as it is completely not const-correct.
Second: Your class will not work with range-for loop.
Third: I would expect container class to adhere to Container concept and interface.
Fourth: code provides absolutely no exceptions guarantees. If some operation on it throws, it will likely corrupt all other elements inside too.
Fifth: no use of move semantics detected. This is what makes C++11 really faster than C++98.
Sixth: does not work for non-default constructible objects
Seventh: assigment operator does not handle self-assigment.
Also many of your functions are too long and have multiple responsibilities. You should really move it in other functions (not belonging to class, as they would be general purpose).
As you want to not use any libraries, you will have to reimplement a bunch of standard functions yourself.
In particular std::copy and std::move from <algorithm>, std::move, std::move_if_noexcept, std::forward and std::move from <utility> and half of <type_traits>
Last edited on
Hi, MiiNiPaa! Thanks for answering! I have some questions for you!
I tried it and it failed as you said. I can't pass any references as argument to the template, like: Container<MyClass&> myContainer;
But here's the catch, vector<MyClass&> or vector<const MyClass&> will also fail. I guess it's not wrong then, is it?
I can't understand how the concept of "const-correctness" could solve this problem. My research brought me to this: http://www.parashift.com/c++-faq/const-correctness.html
But I couldn't find the answer there. Can you help me with a simple example?
I found lots of information about this on stackoverflow. I'll try and fix that.
Once again, can you explain a bit more what you mean by Container concept and interface? Or link me to an explanation. :)
I was aware of that. The reason why I didn't implement any kind of exception rule was that I was too focused on getting the basics of the container working. I wrote all that code in 3 days. I'll fix that as well.
Same thing. I know that move semantics exist, but at first it seemed too complicated to implement, considering I don't want to use any libraries, I would have to write the functions myself, as you mentioned in the end of your post. I'll get to that, but this is the last thing I will do, I think.
Yeah, I didn't notice that until you brought it up. How can I fix this? The best answer I found is this: http://stackoverflow.com/questions/8047602/template-class-no-appropriate-default-constructor-avaialable-but-some-of-my-cl
But I can't figure a way to relate the code in the this post to my code.
This one I'm happy to say that I know exactly how to fix! However, why would anyone need to self assign? I mean, X is X. Then you assign X to X like this: X = X. Now X is still X. Sorry if this question is dumb. I just cant find out how self assignment, in this case, would be useful.
Thank you!
| First of all: Try to pass your Container instance by const reference and work with it. It is impossible, as it is completely not const-correct. |
I tried it and it failed as you said. I can't pass any references as argument to the template, like: Container<MyClass&> myContainer;
But here's the catch, vector<MyClass&> or vector<const MyClass&> will also fail. I guess it's not wrong then, is it?
I can't understand how the concept of "const-correctness" could solve this problem. My research brought me to this: http://www.parashift.com/c++-faq/const-correctness.html
But I couldn't find the answer there. Can you help me with a simple example?
| Second: Your class will not work with range-for loop. |
I found lots of information about this on stackoverflow. I'll try and fix that.
| Third: I would expect container class to adhere to Container concept and interface. |
Once again, can you explain a bit more what you mean by Container concept and interface? Or link me to an explanation. :)
| Fourth: code provides absolutely no exceptions guarantees. If some operation on it throws, it will likely corrupt all other elements inside too. |
I was aware of that. The reason why I didn't implement any kind of exception rule was that I was too focused on getting the basics of the container working. I wrote all that code in 3 days. I'll fix that as well.
| Fifth: no use of move semantics detected. This is what makes C++11 really faster than C++98. |
Same thing. I know that move semantics exist, but at first it seemed too complicated to implement, considering I don't want to use any libraries, I would have to write the functions myself, as you mentioned in the end of your post. I'll get to that, but this is the last thing I will do, I think.
| Sixth: does not work for non-default constructible objects |
Yeah, I didn't notice that until you brought it up. How can I fix this? The best answer I found is this: http://stackoverflow.com/questions/8047602/template-class-no-appropriate-default-constructor-avaialable-but-some-of-my-cl
But I can't figure a way to relate the code in the this post to my code.
| Seventh: assigment operator does not handle self-assigment. |
This one I'm happy to say that I know exactly how to fix! However, why would anyone need to self assign? I mean, X is X. Then you assign X to X like this: X = X. Now X is still X. Sorry if this question is dumb. I just cant find out how self assignment, in this case, would be useful.
Thank you!
Last edited on
First of all something I forgot to tell in my previous post: Consider making your class with heavy use of the standard library. Then start to replace parts of it with your own untill all code is yours. That way you would not sink in mire of nedd to learn everything at once.
It means, you cannot use your class like that:
http://en.cppreference.com/w/cpp/concept/Container
http://en.cppreference.com/w/cpp/concept/SequenceContainer
For example I would expect container to have method push_back() which adds eleemnt to the end (like your add() function). I would expect begin() and and() to return iterators (this is what will allow it to work with range-for too). In your current implementation begin() is unnecessary (it is always 0) and end() can be replaced by size()
Actually move-semantics really simplifies code and in C++11 you need to use it anyway to adhere to the rule of 5 / rule of 0. It is way harder to introduce move in code which does not use it. Not to mention that almost any exception-safe copy constructor can be written in 3 lines using move constructor and swap function.
Do not create array of stuff. Allocate raw piece of memory and construct it in place. Look into
http://en.cppreference.com/w/cpp/types/aligned_storage
http://en.cppreference.com/w/cpp/memory/get_temporary_buffer
Have fun with manual destructor calls.
Nobody. It just happens.
std::fill(v.begin(), v.end(), v[1]); — this will fill whole container with copies of 2nd element. There is self-assigment inside. You could separate range in two, but it is extra work, and what if you just receive reference to object outside and cannot know if it is contained in container?
| I tried it and it failed as you said. I can't pass any references as argument to the template, like: Container<MyClass&> myContainer; But here's the catch, vector<MyClass&> or vector<const MyClass&> will also fail. I guess it's not wrong then, is it? |
|
|
| Once again, can you explain a bit more what you mean by Container concept and interface? Or link me to an explanation. :) |
http://en.cppreference.com/w/cpp/concept/SequenceContainer
For example I would expect container to have method push_back() which adds eleemnt to the end (like your add() function). I would expect begin() and and() to return iterators (this is what will allow it to work with range-for too). In your current implementation begin() is unnecessary (it is always 0) and end() can be replaced by size()
| I'll get to that, but this is the last thing I will do |
| does not work for non-default constructible objects Yeah, I didn't notice that until you brought it up. How can I fix this? |
http://en.cppreference.com/w/cpp/types/aligned_storage
http://en.cppreference.com/w/cpp/memory/get_temporary_buffer
Have fun with manual destructor calls.
| why would anyone need to self assign? |
std::fill(v.begin(), v.end(), v[1]); — this will fill whole container with copies of 2nd element. There is self-assigment inside. You could separate range in two, but it is extra work, and what if you just receive reference to object outside and cannot know if it is contained in container?
Topic archived. No new replies allowed.