Why does std::vector require its elements to be assignable? - Page 2
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 3 FirstFirst 123 LastLast
Results 16 to 30 of 36

Thread: Why does std::vector require its elements to be assignable?

  1. #16
    Join Date
    Jan 2009
    Posts
    1,689

    Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by HighCommander4 View Post
    I'm still curious as to why this is - why can't the elements be copied using placement new + copy constructor during reallocation?
    Because:
    Code:
    vector<string> vec;
    vec.push_back("hello world");
    string & ref = vec[0];
    vec[0] = "hello mars";
    If you literally replaced vec[0] with a new string, where does ref point?

    Also, some classes have very slow ctors, and very fast assignment operators.

  2. #17
    Join Date
    Apr 1999
    Posts
    27,418

    Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by HighCommander4 View Post
    I need to iterate over the elements after adding them, so stack and queue are out of the question.

    Interestingly, deque seems to work (and meets all my needs). Since the major difference between vector and deque is that deque never has to reallocate its elements, while vector does, this suggests that vector needs to invoke the assignment operator on its elements while reallocating.

    I'm still curious as to why this is - why can't the elements be copied using placement new + copy constructor during reallocation?
    If the template implementation happens to use "=" anywhere in the code, you get the compiler error. If the implementation happens to not use "=" anywhere, you don't get the compiler error.

    What I'm saying is that the C++ compiler is not an "STL compiler". The compiler proper doesn't know the requirements of an STL container. All it knows is the C++ syntax in front of it. There are compilers that compiles STL code that goes against the STL requirements without any errors. Not because the compiler knows the STL requirements and is being tricky, it's just that by chance, the internal code didn't trigger a copy, copy ctor, whatever. You take that same code and try to compile it on another compiler, you may just get those errors.

    I've even seen compilers in "debug" mode compile code that goes against the STL requirements, and fail compilation on the release mode. To be exact, the VC 2005 has this, where if you don't define a predicate function as const, the debug version compiled fine, while the release didn't. The reason is as I stated -- a compiler only knows the syntax that it's given. When "debug" is compiled, a different set of code is compiled that doesn't trigger the "const" being in play, while release did.

    So your std::deque "solution" probably only works by chance if the STL requirements are that the type must be copyable and assignable.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; June 24th, 2010 at 02:23 PM.

  3. #18
    Join Date
    Jan 2009
    Posts
    1,689

    Re: Why does std::vector require its elements to be assignable?

    You can always build your own container. You only have a few functions that you are using, so create your own container and you can have it do whatever you want. STL is there for convenience, it doesn't mean you can't write your own classes. Lots and lots of people write their own containers for various reasons.

  4. #19
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by HighCommander4 View Post

    I'm still curious as to why this is - why can't the elements be copied using placement new + copy constructor during reallocation?
    They might be. However as Paul pointed out if the compiler generates all of the member functions for std::vector, std::deque, or whatever container that you are using and something in those implementations uses operator= then your code will not compile unless operator= is defined for the type T.

    In the earlier example that i showed you the problem had nothing to do with the push_back. When I instantiate a template with a user defined type the compiler is generating all of the member functions and even some algorithms that do require assignment. I do not get any errors related to push_back. I think that your other question about when compiler generates the templates is a better question. In my case I do not understand why the compiler tried to generate code for std::fill when I hadn't even used that algorithm for the type in question. If std::fill hadn't caused the problem then one of the container member functions might have.

  5. #20
    Join Date
    Jul 2005
    Posts
    894

    Re: Why does std::vector require its elements to be assignable?

    I am not sure in what context you claimed pair is not assignable. But look at this example.
    Code:
    pair<int, string> p1(1, "Mike");
    pair<int, string> p2 = p1;
    After the assignment, p2 becomes (1, "Mike").
    Quote Originally Posted by HighCommander4 View Post
    I'm not sure I follow. pair<const T, U> is not assignable:

    Code:
    #include <utility>
    using namespace std;
    
    int main()
    {
        pair<const int, int> a;
        pair<const int, int> b;
        a = b;
    }
    Code:
    /usr/include/c++/4.2/bits/stl_pair.h: In member function std::pair<const int, int>& std::pair<const int, int>::operator=(const std::pair<const int, int>&):
    /usr/include/c++/4.2/bits/stl_pair.h:69: error: non-static const member const int std::pair<const int, int>::first, can't use default assignment operator
    test.cpp: In function int main():
    test.cpp:8: note: synthesized method std::pair<const int, int>& std::pair<const int, int>::operator=(const std::pair<const int, int>&) first required here

  6. #21
    Join Date
    Apr 2004
    Location
    Canada
    Posts
    1,342

    Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by Paul McKenzie View Post
    If the template implementation happens to use "=" anywhere in the code, you get the compiler error. If the implementation happens to not use "=" anywhere, you don't get the compiler error.

    What I'm saying is that the C++ compiler is not an "STL compiler". The compiler proper doesn't know the requirements of an STL container. All it knows is the C++ syntax in front of it. There are compilers that compiles STL code that goes against the STL requirements without any errors. Not because the compiler knows the STL requirements and is being tricky, it's just that by chance, the internal code didn't trigger a copy, copy ctor, whatever. You take that same code and try to compile it on another compiler, you may just get those errors.

    I've even seen compilers in "debug" mode compile code that goes against the STL requirements, and fail compilation on the release mode. To be exact, the VC 2005 has this, where if you don't define a predicate function as const, the debug version compiled fine, while the release didn't. The reason is as I stated -- a compiler only knows the syntax that it's given. When "debug" is compiled, a different set of code is compiled that doesn't trigger the "const" being in play, while release did.

    So your std::deque "solution" probably only works by chance if the STL requirements are that the type must be copyable and assignable.

    Regards,

    Paul McKenzie
    Let's look at default constructibility.

    vector requires its element type to be default constructible precisely when you use an operation that requires default construction, e.g. the constructor that creates n default-constructed elements, or resize(n) which adds default constructed elements if there are fewer than n elements in the vector. If the element type is not default constructible and you don't use these operations, your code compiles just fine.

    Why should the assignability requirement be any different? (And please don't say "because the standard says so". I'd like to know the rationale behind the standard.)
    Last edited by HighCommander4; June 24th, 2010 at 03:01 PM.
    Old Unix programmers never die, they just mv to /dev/null

  7. #22
    Join Date
    Apr 2004
    Location
    Canada
    Posts
    1,342

    Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by LarryChen View Post
    I am not sure in what context you claimed pair is not assignable. But look at this example.
    Code:
    pair<int, string> p1(1, "Mike");
    pair<int, string> p2 = p1;
    After the assignment, p2 becomes (1, "Mike").
    If you read my post carefully you'll see that I said pair<const T, U> is not assignable - that is, whenever one of the elements of the pair is const. Of course there is no problem if neither of the elements are const.
    Old Unix programmers never die, they just mv to /dev/null

  8. #23
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Lightbulb Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by ninja9578 View Post
    In that case I would rethink your container needs. Sounds like you need std::stack instead. The right container for the right job.

    You could always write your own vector, for only a few functions, it really wouldn't be that complicated, you could borrow gcc's implementation and strip it to what you need.
    All sequence containers have the same requirement that the type used to instantiate the template be copyable and assignable. This is a common requirement for them all. Therefore using a stack (which uses a deque by default) might not help depending on your implementation. In my case I get lucky because deque's push_back implementation is totally different then vector's. I poked around a little more and I found out that my vector:ush_back function is implemented in terms of the insert member function which is rather complex. As I digged deeper I found out that it has to do with dependencies on some of the other internal member functions of the vector. Although a push_back could be very simple in some cases the fact that those dependencies on other functions exist mean that they have to be completely compiled. Along the way one of those functions that has to be compiled happens to invoke operator=.

  9. #24
    Join Date
    Apr 2004
    Location
    Canada
    Posts
    1,342

    Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by kempofighter View Post
    All sequence containers have the same requirement that the type used to instantiate the template be copyable and assignable. This is a common requirement for them all. Therefore using a stack (which uses a deque by default) might not help depending on your implementation. In my case I get lucky because deque's push_back implementation is totally different then vector's. I poked around a little more and I found out that my vector:ush_back function is implemented in terms of the insert member function which is rather complex. As I digged deeper I found out that it has to do with dependencies on some of the other internal member functions of the vector. Although a push_back could be very simple in some cases the fact that those dependencies on other functions exist mean that they have to be completely compiled. Along the way one of those functions that has to be compiled happens to invoke operator=.
    Right - now we're getting to the heart of the matter.

    What I really want to know is, is it possible to implement vector in a way that certain operations can be performed without the requirement of assignability?

    I suspect the answer is yes, and if so, the next question that naturally arises is, why doesn't the standard mandate such an implementation?
    Old Unix programmers never die, they just mv to /dev/null

  10. #25
    Join Date
    Apr 1999
    Posts
    27,418

    Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by HighCommander4 View Post
    Let's look at default constructibility.

    vector requires its element type to be default constructible precisely when you use an operation that requires default construction, e.g. the constructor that creates n default-constructed elements, or resize(n) which adds default constructed elements if there are fewer than n elements in the vector. If the element type is not default constructible and you don't use these operations, your code compiles just fine.
    Where is the guarantee that the code will compile on all standard conforming compilers? It may have compiled on your compiler, but there is no guarantee it will compile on another one successfully.

    The VC 2005 example I illustrated is part and parcel of why you can't assume that you can "beat the system" by providing classes that go against what STL says it must provide. If your implementation just so happens to give you the luxury of compiling without errors, give the implementors a handshake and a pat on the back for a good job. That in no way guarantees that you will have the same luck with another compiler, given that the other compiler is still standard conforming.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; June 24th, 2010 at 03:14 PM.

  11. #26
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by HighCommander4 View Post
    Let's look at default constructibility.

    vector requires its element type to be default constructible precisely when you use an operation that requires default construction, e.g. the constructor that creates n default-constructed elements, or resize(n) which adds default constructed elements if there are fewer than n elements in the vector. If the element type is not default constructible and you don't use these operations, your code compiles just fine.

    Why should the assignability requirement be any different? (And please don't say "because the standard says so". I'd like to know the rationale behind the standard.)
    They aren't in that context. As Paul said it depends on HOW the STL designer designed that particular version of the code. In my research I found that the vector's push_back depends on other member functions of the vector. Along the way you have many if..else statements that in some cases results in other member functions being called. Even if in your case you don't do anything complex all of the code that push_back depends on must be compiled completely even if at run-time you don't actually execute all of the paths. Go look inside your vector and deque header files and study the implementation details. Since the C++ std requires that all types used for sequence containers be copyable and assignable the compiler isn't violating the standard. They could have implemented the container in some other way, theoretically but they didn't. oh well.

    I am taking a closer look at your std:air example. That seems to be the root cause of your specific troubles. It would have been a good idea to show us a code example in the beginning so that we can understand the specific problem that you are having.

  12. #27
    Join Date
    Apr 2004
    Location
    Canada
    Posts
    1,342

    Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by Paul McKenzie View Post
    Where is the guarantee that the code will compile on all standard conforming compilers? It may have compiled on your compiler, but there is no guarantee it will compile on another one successfully.

    The VC 2005 example I illustrated is part and parcel of why you can't assume that you can "beat the system" by providing classes that go against what STL says it must provide. If your implementation just so happens to give you the luxury of compiling without errors, give the implementors a handshake and a pat on the back for a good job. That in no way guarantees that you will have the same luck with another compiler, given that the other compiler is still standard conforming.
    Yes, I understand what the standard says and what the implications of using non-standard-conforming behaviour are. I'm just trying to understand the rationale behind the standard.

    We have seen that it is possible to implement vector in a way that operations that don't need to call the default constructor will compile without a default constructor. I suspect the same is true for assignment operator. Since implementing vector in this way makes it more flexible, I wonder why the standard doesn't mandate such an implementation. Is it just an omission (or perhaps they didn't think it's important enough) - or is there a good reason?
    Old Unix programmers never die, they just mv to /dev/null

  13. #28
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Lightbulb Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by HighCommander4 View Post
    Right - now we're getting to the heart of the matter.

    What I really want to know is, is it possible to implement vector in a way that certain operations can be performed without the requirement of assignability?

    I suspect the answer is yes, and if so, the next question that naturally arises is, why doesn't the standard mandate such an implementation?
    What difference does it make? It isn't going to happen so even if it were possible how would it help you today? It is obviously possible since as I said earlier the deque:ush_back in my STL implementation does exactly what you are talking about. I have no idea if all STL implementations for deque are the same. What does the new standard say? Go read it. there is no point in asking if the standard could be changed since it is essentially finished or asking of the compiler writers could have done something different.

  14. #29
    Join Date
    Apr 2004
    Location
    Canada
    Posts
    1,342

    Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by kempofighter View Post
    What difference does it make? It isn't going to happen so even if it were possible how would it help you today?
    It makes a difference because there may be good reason why the standard doesn't require vector to be implemented in this way - perhaps because it's impossible, for some reason that eludes me at the moment - and if so I'd like to know.

    It is obviously possible since as I said earlier the deque:ush_back in my STL implementation does exactly what you are talking about.
    But deque is different from vector. vector's push_back() may need to reallocate existing elements, deque's does not.
    Old Unix programmers never die, they just mv to /dev/null

  15. #30
    Join Date
    Aug 2005
    Location
    San Diego, CA
    Posts
    1,054

    Red face Re: Why does std::vector require its elements to be assignable?

    Quote Originally Posted by HighCommander4 View Post
    I'm not sure I follow. pair<const T, U> is not assignable:

    Code:
    #include <utility>
    using namespace std;
    
    int main()
    {
        pair<const int, int> a;
        pair<const int, int> b;
        a = b;
    }
    Code:
    /usr/include/c++/4.2/bits/stl_pair.h: In member function std::pair<const int, int>& std::pair<const int, int>::operator=(const std::pair<const int, int>&):
    /usr/include/c++/4.2/bits/stl_pair.h:69: error: non-static const member const int std::pair<const int, int>::first, can't use default assignment operator
    test.cpp: In function int main():
    test.cpp:8: note: synthesized method std::pair<const int, int>& std::pair<const int, int>::operator=(const std::pair<const int, int>&) first required here
    You are right - I didn't think that one through well enough. It is impossible for default assignment to work for classes with const attributes. I duplicated your problem with a user defined struct type so I understand now. That is a really interesting issue. For any class with non-static, const members you couldn't always use that type with STL sequence containers. The concept of assignment doesn't make sense for that case since after the assignment the two classes could never be equal. So I guess in your case, why does the pair have to be const for T1? I have never run across this problem in any of my designs. In my experience I have always had situations where a class with constants either has a) static constants for all objects b) non-static constants but the class is a singleton type or c) used enum type for declaring sets of constants. With an enum decl within a class the class you don't have to instantiate the enum to use the constants and the values are the same for all class instances so it is similar to having static constants.

Page 2 of 3 FirstFirst 123 LastLast

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center