I am trying to understand under what circumstances destructors get called
with std::vector. I have an application in which I will put real objects,
not just pointers, in the vector.
1. The standard says that empty() has constant complexity. If it actually
called the destructor for each object, it seems to me it would have
linear complexity. Does empty() call the destructor for each object in the
container? If yes, why is it described as having constant commplexity?
If no, that seems like a problem too.
2. The standard describes clear by saying that it behaves like
erase(begin, end). That seems as if it would erase the first element, copying
all succedding elements over it, and so on, which is obviously very
inefficient. Is it safe to assume something more reasonable is happening
under the covers?
3. Does erase call the destructor for the elements erased?
More properly, I guess I should ask if the elements freed at the end after
being moved over erased items are cleared. I'd probably only be erasing
the whole vector or its last element.
As I'm writing this I realize I may have a basic confusion, and that
constructors and destructors are only called at the beginning and end
of the vector's life (and when its capacity expands). The rest of the
time elements are either in use or not, with the behavior of the assignment
operator being key. Is that what's really going on?
I'm interested both in what can and can't be inferred from the standard, and
in what current compiler practice on different platforms is--in other words,
what's safe to assume in portable code. 12 1818
"Ross Boylan" <Ro********@sta nfordalumni.org > wrote... I am trying to understand under what circumstances destructors get called with std::vector. I have an application in which I will put real objects, not just pointers, in the vector.
1. The standard says that empty() has constant complexity. If it actually called the destructor for each object, it seems to me it would have linear complexity. Does empty() call the destructor for each object in
the container? If yes, why is it described as having constant commplexity? If no, that seems like a problem too.
'empty' is not the same as 'clear'. Do not confuse the two. For C++
library containers, 'empty' is an adjective, not a verb.
2. The standard describes clear by saying that it behaves like erase(begin, end). That seems as if it would erase the first element,
copying all succedding elements over it, and so on, which is obviously very inefficient. Is it safe to assume something more reasonable is happening under the covers?
Absolutely. When semantics are explained, it doesn't mean that the
implementation is precisely the same. Do not confuse semantics and
implementation. 3. Does erase call the destructor for the elements erased?
Yes.
More properly, I guess I should ask if the elements freed at the end after being moved over erased items are cleared.
I am not sure I completely understand the sentence, but elements can
be freed even in the middle of erasing, during the move. std::vector
is a tricky container, it has to reallocate and move things all the
time, so the old elements will get destroyed right after new copies of
them are made.
I'd probably only be erasing the whole vector or its last element.
Don' make no difference, they are still gonna get destroyed. Hafta. As I'm writing this I realize I may have a basic confusion, and that constructors and destructors are only called at the beginning and end of the vector's life (and when its capacity expands).
....and when you insert or remove an element in the middle. IOW, every
time elements get moved around.
The rest of the time elements are either in use or not, with the behavior of the
assignment operator being key. Is that what's really going on?
Plenty. Why not trace all the constructor and destructor calls? It's
fun and it's educational. It's educational fun.
I'm interested both in what can and can't be inferred from the standard,
and in what current compiler practice on different platforms is--in other
words, what's safe to assume in portable code.
Nothing is safe to assume except what's said in the Standard.
V
"Ross Boylan" <Ro********@sta nfordalumni.org > wrote in message
news:pa******** *************** *****@stanforda lumni.org... I am trying to understand under what circumstances destructors get called with std::vector. I have an application in which I will put real objects, not just pointers, in the vector.
1. The standard says that empty() has constant complexity. If it actually called the destructor for each object, it seems to me it would have linear complexity. Does empty() call the destructor for each object in
the container? If yes, why is it described as having constant commplexity? If no, that seems like a problem too.
A conforming implementation of empty() is: return this->size() > 0;
This function does not empty the vector ( unlike clear() ): it only
returns a boolean that indicates whether the container is empty or not.
2. The standard describes clear by saying that it behaves like erase(begin, end). That seems as if it would erase the first element,
copying all succedding elements over it, and so on, which is obviously very inefficient. Is it safe to assume something more reasonable is happening under the covers?
erase() does not remove elements one by one: the whole range is "removed"
by copying/moving the following elements over it. Then the unused trailing
elements are removed.
Say if the first three elements of ABCDEFGH are erased, steps that will
typically happen are:
DEFGH are copied down using the assignment operator --> DEFGHFGH
The trailing elements are destroyed --> DEFGH
3. Does erase call the destructor for the elements erased?
Yes. More properly, I guess I should ask if the elements freed at the end after being moved over erased items are cleared. I'd probably only be erasing the whole vector or its last element.
Which means you can call clear() and pop_back(), respectively,
instead of erase().
As I'm writing this I realize I may have a basic confusion, and that constructors and destructors are only called at the beginning and end of the vector's life (and when its capacity expands). The rest of the time elements are either in use or not, with the behavior of the
assignment operator being key. Is that what's really going on?
The capacity of a vector is only allocated as raw memory.
The number of constructed objects within the vector is always equal to
the value returned by vector::size().
I'm interested both in what can and can't be inferred from the standard,
and in what current compiler practice on different platforms is--in other
words, what's safe to assume in portable code.
No 'ghost' objects can be constructed by std::vector, given than:
- the element contained in an std::vector may not have a default
constructor
- keeping hidden copies of elements that have been erased would have
unexpected effects -- and is not allowed.
hth, Ivan
-- http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form
"Ivan Vecerina" <pl************ *****@ivan.vece rina.com> wrote in message
news:c0******** **@newshispeed. ch... "Ross Boylan" <Ro********@sta nfordalumni.org > wrote in message news:pa******** *************** *****@stanforda lumni.org... I am trying to understand under what circumstances destructors get called with std::vector. I have an application in which I will put real objects, not just pointers, in the vector.
1. The standard says that empty() has constant complexity. If it actually called the destructor for each object, it seems to me it would have linear complexity. Does empty() call the destructor for each object in the container? If yes, why is it described as having constant commplexity? If no, that seems like a problem too.
A conforming implementation of empty() is: return this->size() > 0; This function does not empty the vector ( unlike clear() ): it only returns a boolean that indicates whether the container is empty or not.
Josuttis in his book "The C++ standard library" recommends empty() over
container.size( ) > 0. He says it is _usually_ more efficient.
Given this implementation this might not be true. 2. The standard describes clear by saying that it behaves like erase(begin, end). That seems as if it would erase the first element, copying all succedding elements over it, and so on, which is obviously very inefficient. Is it safe to assume something more reasonable is happening under the covers? erase() does not remove elements one by one: the whole range is "removed" by copying/moving the following elements over it. Then the unused trailing elements are removed. Say if the first three elements of ABCDEFGH are erased, steps that will typically happen are: DEFGH are copied down using the assignment operator --> DEFGHFGH The trailing elements are destroyed --> DEFGH
hmm..IIRC, they are not.
One must take care to erase the trailing elements (i.e FGH).
Best wishes,
Sharad
"Sharad Kala" <no************ *****@yahoo.com > wrote in message
news:c0******** *****@ID-221354.news.uni-berlin.de... "Ivan Vecerina" <pl************ *****@ivan.vece rina.com> wrote in message news:c0******** **@newshispeed. ch... "Ross Boylan" <Ro********@sta nfordalumni.org > wrote in message news:pa******** *************** *****@stanforda lumni.org... I am trying to understand under what circumstances destructors get
called with std::vector. I have an application in which I will put real
objects, not just pointers, in the vector.
1. The standard says that empty() has constant complexity. If it
actually called the destructor for each object, it seems to me it would have linear complexity. Does empty() call the destructor for each object
in the container? If yes, why is it described as having constant
commplexity? If no, that seems like a problem too.
A conforming implementation of empty() is: return this->size() > 0; This function does not empty the vector ( unlike clear() ): it only returns a boolean that indicates whether the container is empty or not.
Josuttis in his book "The C++ standard library" recommends empty() over container.size( ) > 0. He says it is _usually_ more efficient. Given this implementation this might not be true.
nitpick
empty() is the same as size() == 0
surely.
john
"Sharad Kala" <no************ *****@yahoo.com > wrote in message
news:c0******** *****@ID-221354.news.uni-berlin.de...
|
| "Ivan Vecerina" <pl************ *****@ivan.vece rina.com> wrote in message
| news:c0******** **@newshispeed. ch...
....
| > A conforming implementation of empty() is: return this->size() > 0;
^^^^^^^^^^
Note that my comment was about behavior, not performance or style.
| Josuttis in his book "The C++ standard library" recommends empty() over
| container.size( ) > 0. He says it is _usually_ more efficient.
| Given this implementation this might not be true.
Indeed, his advice is not universally true. Some implementations of
vector::empty() are definitely implemented by calling vector::size().
However, style-wise, I would concur that calling empty() is better
than comparing size() to zero. ( just as I recommended calling
clear() and pop_back() instead of erase(), when applicable )
| > > 2. The standard describes clear by saying that it behaves like
| > > erase(begin, end). That seems as if it would erase the first element,
| > copying
| > > all succedding elements over it, and so on, which is obviously very
| > > inefficient. Is it safe to assume something more reasonable is
happening
| > > under the covers?
| > erase() does not remove elements one by one: the whole range is
"removed"
| > by copying/moving the following elements over it. Then the unused
trailing
| > elements are removed.
| > Say if the first three elements of ABCDEFGH are erased, steps that will
| > typically happen are:
| > DEFGH are copied down using the assignment operator --> DEFGHFGH
| > The trailing elements are destroyed --> DEFGH
| hmm..IIRC, they are not.
| One must take care to erase the trailing elements (i.e FGH).
Not correct.
In the context of the OP, it seemed clear that this discussion was about
the vector::erase member function. This member function is not to be
confused with the non-member std::erase algorithm (to which your
comment would applly).
C++ standard 23.2.4.3/4 (about vector::erase):
Complexity: The destructor of T is called the number of times equal to the
number of the elements erased, but the assignment operator of T is called
the number of times equal to the number of elements in the vector after the
erased elements.
Regards,
Ivan
-- http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form
John Harrison wrote in news:c0******** *****@ID-196037.news.uni-berlin.de: nitpick
empty() is the same as size() == 0
surely.
With some implementations of std::list<> this is not the case.
In these implementations size() is calculated (std::distance( ... ))
every time it is called, empty() just needs to check wether the list
is empty or not. So its constant-time vs. O(n).
With these implementations splice() is faster because they don't
maintain a seperate size member.
Rob.
-- http://www.victim-prime.dsl.pipex.com/
"Rob Williscroft" <rt*@freenet.RE MOVE.co.uk> wrote in message
news:Xn******** *************** ***********@195 .129.110.204... John Harrison wrote in news:c0******** *****@ID-196037.news.uni-berlin.de:
nitpick
empty() is the same as size() == 0
surely.
With some implementations of std::list<> this is not the case.
In these implementations size() is calculated (std::distance( ... )) every time it is called, empty() just needs to check wether the list is empty or not. So its constant-time vs. O(n).
With these implementations splice() is faster because they don't maintain a seperate size member.
Rob. -- http://www.victim-prime.dsl.pipex.com/
Well I wasn't talking about efficiency I was just correcting the obvious
mistake that 'empty() is that same as size() > 0' which two posters had
made.
But since you brought up the topic I think that the standard requires size()
to be O(1) and allows splice on different lists to be O(n).
john
"Ivan Vecerina" <pl************ *****@ivan.vece rina.com> wrote in message news:c0******** **@newshispeed. ch... A conforming implementation of empty() is: return this->size() > 0;
Actually, that is specific NOT conforming for containers in general.
As alluded to in the original post, empty has constant complexity.
size() may take longer.
John Harrison wrote in
news:c0******** *****@ID-196037.news.uni-berlin.de: With some implementations of std::list<> this is not the case.
In these implementations size() is calculated (std::distance( ... )) every time it is called, empty() just needs to check wether the list is empty or not. So its constant-time vs. O(n).
With these implementations splice() is faster because they don't maintain a seperate size member. Well I wasn't talking about efficiency I was just correcting the obvious mistake that 'empty() is that same as size() > 0' which two posters had made.
But since you brought up the topic I think that the standard requires size() to be O(1) and allows splice on different lists to be O(n).
In a note (bottom of 23.1 Table 65) it says size() "should have
constant complexity", it requires that splice has complexity
"Contant Time" 23.2.2.4/6
So I was wrong splice() is required to be O(1), I was under the
impression that this was upto the implementor, but this is the first
time I've checked the standard.
Rob.
-- http://www.victim-prime.dsl.pipex.com/ This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Rajesh Garg |
last post by:
Can we have private constructors and destructors? IF yes what is the
use of such constructors or destructors.....in the sense where can
these be implemented in a system.................
I have an idea that we can have private constructors and destructors
but am not able to find a situation where they can be used...
Regards
RVG
rajeshgarg@opussoft.com
|
by: matthurne |
last post by:
I am working through exercise 8-2 in Accelerated C++...I am
implementing the function equal(b, e, b2) where b is an iterator for
the first element in a container, e is an iterator pointing to one
past the last element in that same container, and b2 is an iterator
for the first element in the second container. Here's what I have:
template <class T>
bool equal(T begin, T end, T begin2) {
while (begin != end) {
if (*begin != *begin2) {
|
by: graftonfot |
last post by:
Hi there,
I've programmed in C++ for many years, but I've been away from it for a
while.
I have some JDK 1.4 code that I need to re-implement in C++. I am
wondering, are there any commonly-used libraries for replacing the Java
SDK types (particularly all the containers) that people use these days?
I know about the STL, but was wondering if there was anything more
popular/current.
|
by: Steven T. Hatton |
last post by:
Now that I have a better grasp of the scope and capabilities of the C++
Standard Library, I understand that products such as Qt actually provide
much of the same functionality through their own libraries. I'm not sure
if that's a good thing or not. AFAIK, most of Qt is compatable with the
Standard Library. That is, QLT can interoperate with STL, and you can
convert back and forth between std::string and Qt::QString, etc.
Are there any...
|
by: Tony Johansson |
last post by:
Hello!
Is it possible to mix C++ code for example DLL developed with Visual Studio
6.0 with C++ code developed with Windows Forms Application(.NET)?
Is it possible to mix C++ code for example DLL developed with Visual Studio
6.0 with C# code developed with Windows Forms Application(.NET)?
Have an application developed with Windows Forms Application(.NET) any
advantages compared to an
| |
by: Shark |
last post by:
I read that in the C++ standard library destructors are not supposed to
throw exceptions. Is this true of only the library, or is it true of
C++ classes in general?
|
by: alternativa |
last post by:
Hello,
I have a few questions concerning classes.
1)
Why some people use default constructos, i.e constructors with no
parameters? To me it doesn't make any sense, is there something I
should know? For example, I'd declare a class in a following way:
class Sample {
int number;
string title;
|
by: Digital Puer |
last post by:
I'm not the world's greatest C++ programmer, so I had a hard
time with these. Some help would be appreciated.
1. Comment on the declaration of function Bar() below:
class Foo
{
static int Bar(int i) const;
}
(I said that since Bar is a static method, it can only access
|
by: AzizMandar |
last post by:
C++ Event Coding Questions
I have done some simple programs in C++ and read a lot of good C++
books (Including The C++ Programing Language, and C++ Primer) I am
trying to understand and implement an Event based program and Message
system. I have a very basic event engine that I'm feeling works a bit
backwards. I'm looking for documents, source code, and books that may
help me better understand how to implement this type of code. I am...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
| |
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |