empty

This is a discussion on empty within the C++ Programming forums, part of the General Programming Boards category; I noticed that it's a common error among that C++ programmers think that STL's empty() actually empties the list. So ...

  1. #1
    Registered User
    Join Date
    Jan 2007
    Posts
    330

    empty

    I noticed that it's a common error among that C++ programmers think that STL's empty() actually empties the list.

    So I see a lot of

    Code:
    ~Destruct() {
      list1.empty();
      list2.empty();
    }
    Has anybody else noticed that?

    Kinda interesting in terms of interface design that many people assume that empty actually empties a list. Understandable as it's a verb too.

  2. #2
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    I've never noticed it.

    What needs to be emphasised though is that empty() is vastly superior to size() == 0, because size() often requires traversing the list to figure out how long it is. If we can educate people about that we can solve two problems at the same time.

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,202
    Quote Originally Posted by KIBO View Post
    Has anybody else noticed that?
    Nope. I see other types of error much more frequently than that. In fact, your post provided the first time I've seen that suggested as a common mistake. I assume you based that observation on having done it yourself .....
    Quote Originally Posted by KIBO View Post
    Kinda interesting in terms of interface design that many people assume that empty actually empties a list. Understandable as it's a verb too.
    Just goes to show the value of reading documentation .... a skill that too many programmers neglect to exercise.
    Right 98% of the time, and don't care about the other 3%.

  4. #4
    Registered User
    Join Date
    Jan 2007
    Posts
    330
    I've seen it in 2 different companies and in one company the code has been maintained by many (20+) programmers....and it's still in there so they didnt notice

  5. #5
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    You mean this is in professional code? I find that strange since there's no need to clear out a member list in a destructor anyway, since those lists will clear themselves when they are destroyed.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,415
    Quote Originally Posted by Mozza314
    What needs to be emphasised though is that empty() is vastly superior to size() == 0, because size() often requires traversing the list to figure out how long it is.
    Don't have a copy of the standard on hand to verify, but if I remember correctly, size() has constant time complexity for all standard containers and std::basic_string.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Jan 2007
    Posts
    330
    Quote Originally Posted by laserlight View Post
    Don't have a copy of the standard on hand to verify, but if I remember correctly, size() has constant time complexity for all standard containers and std::basic_string.
    Scott Meyers explains that in one of his effective C++ books. I dont remember exactly but it had something to do with that in some implementations size() takes lineair time after splicing a linked list

    Effective STL Item 4 (size() vs. empty()) - C / C++ answers

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,294
    It probably has something to do with the fact that the Empty() method of a CComBSTR does empty out its contents.
    Yes it has a capital 'E' though.

    Probably isn't the only thing adding to the confusion.

    Quote Originally Posted by laserlight View Post
    Don't have a copy of the standard on hand to verify, but if I remember correctly, size() has constant time complexity for all standard containers and std::basic_string.
    I recall that GCC didn't store the count of items in a list, which meant it traded constant time size() for constant time splice(). Oh wait, someone has already mentioend this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    That name would indeed be more descriptive as is_empty.

    Since that code does nothing, it doesn't probably mean that all of those 20 programmers thought it is needed. Most of them probably wouldn't fix it because it isn't broken.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,415
    Quote Originally Posted by iMalc
    I recall that GCC didn't store the count of items in a list, which meant it traded constant time size() for constant time splice().
    That could mean that the GCC implementation has a bug, except that someone who posted in the thread KIBO linked to pointed out that there is leeway granted by the current version of the standard. I have verified that in recent drafts of the next version of the standard, size() is indeed absolutely required to have constant time complexity.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The operational semantics of size() is "distance(a.begin(), a.end())". This is how (at least my version of) gcc implements it. What does the term "operational semantics" mean anyhow?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,169
    O_o

    My understanding of the history of the standard and the implementations is that `std::whatever::size()' should have always been constant, but the earlier drafts used the expression "distance(a.begin(), a.end())" in describing the "operational semantics", the expected behavioral results of the function, and was therefore interpreted as a requirement in spite of notes even in earlier drafts that the complexity should be constant.

    Soma

  13. #13
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The operational semantics don't come from an earlier draft. It's in n3225.pdf which should be quite recent.

    Personally I find that a constant complexity range splice from a different list would be better to have than a constant complexity size. The first is special strength of a linked list after all, the second is seldom useful considering the contents are going to be accessed sequentially anyway.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  14. #14
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,169
    The operational semantics don't come from an earlier draft.
    O_o

    How much would you like to bet?

    Seriously, I'm sure the phrase also appears in current drafts; I would expect it too as it appears, like I said, in some of the earlier drafts. (I have one from late 1997.)

    Personally I find that a constant complexity range splice from a different list would be better to have than a constant complexity size.
    I'd prefer that my own implementation's nodes with dynamic controlled allocators were not container aware, but that is necessary given standard behavior requirements.

    *shrug*

    The standard maintainers have to choose between a lot of trades; it would be impossible to choose a set that would satisfy everyone without complicating the implementation and usage.

    The first is special strength of a linked list after all, the second is seldom useful considering the contents are going to be accessed sequentially anyway.
    If you are careful with your design, you can usually get a constant splice operation by using slave lists and splicing the entire contents.

    It isn't ideal, but it can help if you are doing a lot of splicing operations.

    Soma

  15. #15
    C++ Junkie Mozza314's Avatar
    Join Date
    Jan 2011
    Location
    Australia
    Posts
    174
    Quote Originally Posted by laserlight View Post
    I have verified that in recent drafts of the next version of the standard, size() is indeed absolutely required to have constant time complexity.
    Could you check the complexity requirement on std::list::splice in the same draft? As has been mentioned, I don't think it's possible to have constant time size() and splice(), so I guess that means C++0x is switching the two tradeoffs?

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Can anyone help?
    By javalurnin in forum C Programming
    Replies: 11
    Last Post: 12-02-2009, 05:02 AM
  2. Help with binary file c++
    By lucky_mutani in forum C++ Programming
    Replies: 4
    Last Post: 06-05-2009, 09:24 AM
  3. Finding whether UCHAR is empty?
    By Witchfinder in forum C Programming
    Replies: 4
    Last Post: 04-25-2009, 10:19 AM
  4. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  5. skipping empty files using ifstream
    By bradleym83 in forum C++ Programming
    Replies: 14
    Last Post: 08-12-2005, 07:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21