473,847 Members | 1,801 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Copy algorithm with insert iterators...

I have gotten into the habit of often using copy along with an insert
iterator. There are scenarios where I process quite a lot of data this way.
Can someone give me a general feel as to how much of a performance hit I'm
taking using this technique versus using 'copy' to copy directly into a
container with elements in place?

Thanks,
d
Jul 23 '05 #1
18 2311
"deancoo" <s2*******@yaho o.ca> wrote in message
news:k7KWd.1182 3$KI2.9259@clgr ps12...
I have gotten into the habit of often using copy along with an insert
iterator. There are scenarios where I process quite a lot of data this
way. Can someone give me a general feel as to how much of a performance hit
I'm taking using this technique versus using 'copy' to copy directly into a
container with elements in place?

Thanks,
d


As always, if you have critical performance requirements you should do
timing studies. However, you asked for a general feel. Generally it's not
bad. For instance with std::vector you can do

std::vector<dou ble> v(10000);
std::copy(ptr, ptr+10000, &v[0]);

which will save doing 10000 push_back operations, but now you have to
initialize 10000 doubles to 0.0 just before overwriting them. The
alternative you are using which is presumably

std::vector<dou ble> v;
v.reserve(10000 ); // don't forget this
std::copy(ptr, ptr+10000, std::back_inser ter(v));

does a little bookkeeping on each step -- probably incrementing a "last"
pointer -- but initializes using a copy constructor. If you don't reserve
enough memory before your std::copy the object will have to reallocate
memory several times.

--
Cy
http://home.rochester.rr.com/cyhome/
Jul 23 '05 #2
"Cy Edmunds" <ce******@spaml ess.rochester.r r.com> wrote in message
news:wn******** ***********@twi ster.nyroc.rr.c om...
"deancoo" <s2*******@yaho o.ca> wrote in message
news:k7KWd.1182 3$KI2.9259@clgr ps12... The alternative you are using which is presumably

std::vector<dou ble> v;
v.reserve(10000 ); // don't forget this
std::copy(ptr, ptr+10000, std::back_inser ter(v));

does a little bookkeeping on each step -- probably incrementing a "last"
pointer -- but initializes using a copy constructor. If you don't reserve
enough memory before your std::copy the object will have to reallocate
memory several times.


I guess the real question is why you don't do this:

v.insert(v.end( ), ptr, ptr+10000);

That way, vector::insert knows how many elements will be inserted before it
starts its work, so (at least in principle) it can allocate the right amount
of memory once and be done with it.
Jul 23 '05 #3
"Andrew Koenig" <ar*@acm.org> wrote in message
news:PI******** *************@b gtnsc05-news.ops.worldn et.att.net...
"Cy Edmunds" <ce******@spaml ess.rochester.r r.com> wrote in message
news:wn******** ***********@twi ster.nyroc.rr.c om...
"deancoo" <s2*******@yaho o.ca> wrote in message
news:k7KWd.1182 3$KI2.9259@clgr ps12...

The alternative you are using which is presumably

std::vector<dou ble> v;
v.reserve(10000 ); // don't forget this
std::copy(ptr, ptr+10000, std::back_inser ter(v));

does a little bookkeeping on each step -- probably incrementing a "last"
pointer -- but initializes using a copy constructor. If you don't reserve
enough memory before your std::copy the object will have to reallocate
memory several times.


I guess the real question is why you don't do this:

v.insert(v.end( ), ptr, ptr+10000);

That way, vector::insert knows how many elements will be inserted before
it starts its work, so (at least in principle) it can allocate the right
amount of memory once and be done with it.

Your version might be OK depending on the implementation. The function can't
just subtract the iterators to find the length of the sequence because that
would assume random access iterators. And if you use that form with
something other than random access iterators it can't get the sequence
length even in principle. Using reserve() as I suggested works with any type
of iterator.

--
Cy
http://home.rochester.rr.com/cyhome/
Jul 23 '05 #4
On 2005-03-06 23:01:14 -0500, "Cy Edmunds"
<ce******@spaml ess.rochester.r r.com> said:
"Andrew Koenig" <ar*@acm.org> wrote in message
news:PI******** *************@b gtnsc05-news.ops.worldn et.att.net...
"Cy Edmunds" <ce******@spaml ess.rochester.r r.com> wrote in message
news:wn******** ***********@twi ster.nyroc.rr.c om...
"deancoo" <s2*******@yaho o.ca> wrote in message
news:k7KWd.1182 3$KI2.9259@clgr ps12...

The alternative you are using which is presumably

std::vector<dou ble> v;
v.reserve(10000 ); // don't forget this
std::copy(ptr, ptr+10000, std::back_inser ter(v));

does a little bookkeeping on each step -- probably incrementing a
"last" pointer -- but initializes using a copy constructor. If you
don't reserve enough memory before your std::copy the object will have
to reallocate memory several times.


I guess the real question is why you don't do this:

v.insert(v.end( ), ptr, ptr+10000);

That way, vector::insert knows how many elements will be inserted
before it starts its work, so (at least in principle) it can allocate
the right amount of memory once and be done with it.

Your version might be OK depending on the implementation. The function
can't just subtract the iterators to find the length of the sequence
because that would assume random access iterators. And if you use that
form with something other than random access iterators it can't get the
sequence length even in principle. Using reserve() as I suggested works
with any type of iterator.


An implementation could have specializations of insert for various
types of input iterators. In such a case, it could very well subtract
the iterators to find the number of items to be inserted. For example:
class MyContainer
{
public:
typedef ... iterator;
...

private:
template<typena me InputIterator>
void insert_impl(ite rator pos, InputIterator first, InputIterator
last, const std::input_iter ator_tag &)
{
...
}

template<typena me ForwardIterator >
void insert_impl(ite rator pos, ForwardIterator first, ForwardIterator
last, const std::forward_it erator_tag &)
{
//Will handle forward, bidirectional and random-access
reserve(std::di stance(first, last));
insert_impl(pos , first, last, const std::input_iter ator_tag())
}

public:
template<typena me InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last)
{
insert_impl(pos , first, last,
std::iterator_t raits<InputIter ator>::iterator _category());
}
};
--
Clark S. Cox, III
cl*******@gmail .com

Jul 23 '05 #5
Cy Edmunds wrote:

Your version might be OK depending on the implementation. The function can't
just subtract the iterators to find the length of the sequence because that
would assume random access iterators.


On the contrary: the function can subtract the iterators because they're
random access iterators. That's what iterator categories are all about:
tuning the algorithm based on the category of the iterator.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jul 23 '05 #6
"Cy Edmunds" <ce******@spaml ess.rochester.r r.com> wrote in message
news:em******** **********@twis ter.nyroc.rr.co m...
I guess the real question is why you don't do this:

v.insert(v.end( ), ptr, ptr+10000);

That way, vector::insert knows how many elements will be inserted before
it starts its work, so (at least in principle) it can allocate the right
amount of memory once and be done with it.

Your version might be OK depending on the implementation. The function
can't just subtract the iterators to find the length of the sequence
because that would assume random access iterators. And if you use that
form with something other than random access iterators it can't get the
sequence length even in principle. Using reserve() as I suggested works
with any type of iterator.


If you know that there will be 10000 elements, you can do this:

v.reserve(v.siz e() + 10000);
v.insert(v.end( ), ptr, ptr + 10000);

If you don't, you can't. Well, you can, but you don't know if it will help
or hurt.

As for saying that v.insert "can't just subtract the iterators to find the
length of the sequence," it is not unusual for implementations to test
(using iterator_catego ry) whether the iterators are random-access and use
different algorithms if they are. It is actually possible to do this test
at compile time if you're clever about it.
Jul 23 '05 #7
"Pete Becker" <pe********@acm .org> wrote in message
news:HN******** ************@rc n.net...
Cy Edmunds wrote:

Your version might be OK depending on the implementation. The function
can't just subtract the iterators to find the length of the sequence
because that would assume random access iterators.


On the contrary: the function can subtract the iterators because they're
random access iterators. That's what iterator categories are all about:
tuning the algorithm based on the category of the iterator.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)


The iterators under discussion are not necessarily the iterators from
std::vector. They could, for instance, be from std::list in which case they
would NOT be random access iterators. Your own documentation describes the
method in question as

void insert(iterator where, InIt first, InIt last);

which I assume means input iterator.

--
Cy
http://home.rochester.rr.com/cyhome/
Jul 23 '05 #8
"Andrew Koenig" <ar*@acm.org> wrote in message
news:vS******** *************@b gtnsc05-news.ops.worldn et.att.net...
"Cy Edmunds" <ce******@spaml ess.rochester.r r.com> wrote in message
news:em******** **********@twis ter.nyroc.rr.co m...
I guess the real question is why you don't do this:

v.insert(v.end( ), ptr, ptr+10000);

That way, vector::insert knows how many elements will be inserted before
it starts its work, so (at least in principle) it can allocate the right
amount of memory once and be done with it.

Your version might be OK depending on the implementation. The function
can't just subtract the iterators to find the length of the sequence
because that would assume random access iterators. And if you use that
form with something other than random access iterators it can't get the
sequence length even in principle. Using reserve() as I suggested works
with any type of iterator.


If you know that there will be 10000 elements, you can do this:

v.reserve(v.siz e() + 10000);
v.insert(v.end( ), ptr, ptr + 10000);

If you don't, you can't. Well, you can, but you don't know if it will
help or hurt.

As for saying that v.insert "can't just subtract the iterators to find the
length of the sequence," it is not unusual for implementations to test
(using iterator_catego ry) whether the iterators are random-access and use
different algorithms if they are. It is actually possible to do this test
at compile time if you're clever about it.


I know. But my recommended syntax works with an implementation which isn't
clever. It also works efficiently if you change the iterator type to
something less than a random access iterator. Hence it is more portable and
more maintainable than using insert.

You originally asked why I didn't just do

v.insert(v.end( ), ptr, ptr+10000);

That's why.

--
Cy
http://home.rochester.rr.com/cyhome/
Jul 23 '05 #9
Cy Edmunds wrote:
The iterators under discussion are not necessarily the iterators from
std::vector. They could, for instance, be from std::list in which case they
would NOT be random access iterators.
From your example:
std::copy(ptr, ptr+10000, &v[0]);


Since you're adding 10000 to ptr, it has to be a random access iterator.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jul 23 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
6316
by: sks_cpp | last post by:
map<int, Drive*> dMap; list<Drive*> dList; copy( dMap.begin(), dMap.end(), back_inserter(dList) ); // incorrect The above will not because value_type of dMap is different than dList. Now, I would like to wrap the map iterators inside a class class (let's call it WrapMap) WrapMap wm(dMap.begin(), dMap.end() );
4
2981
by: Simon Elliott | last post by:
Is there an equivalent of std::copy which works on STL containers for overlapping ranges? -- Simon Elliott http://www.ctsn.co.uk
4
1783
by: Generic Usenet Account | last post by:
I am seeing some unexpected behavior while using the STL "includes" algorithm. I am not sure if this is a bug with the template header files in our STL distribution, or if this is how it should work. For your benefit, let me first quote from the STL Standard Reference (Stepanov & Lee): template <class InputIterator1, class InputIterator2> bool includes(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2...
4
4514
by: Nick Keighley | last post by:
Hi, I've checked out various documentation for multimap but can't find anywhere it explicitly stated that insert() invalidates multimap iterators. consider this pseudo code:- int DataItem::genDerived () {
1
2130
by: utab | last post by:
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <iterator> using std::cout; using std::vector; using std::string; using std::endl;
19
2853
by: Khafancoder | last post by:
Hi guys, in my db i have these three tables 1.Stores 2.Products 3.Parts their structure is something like : Stores ----Products ----Parts
10
6086
by: arnuld | last post by:
WANTED: /* C++ Primer - 4/e * * Exercise: 9.26 * STATEMENT * Using the following definition of ia, copy ia into a vector and into a list. Use the single iterator form of erase to remove the elements with odd values from your list * and the even values from your vector.
1
2543
by: subramanian100in | last post by:
Suppose I have vector<intvi; deque<intdi; list<intli; Suppose all of these containers have some elements. Suppose 'v_iter' is an iterator pointing to some element in 'vi'. Suppose 'v_beg' and 'v_end' are valid iterators pointing to some
6
3938
by: Peng Yu | last post by:
Hi, I'm wondering if the following assignment is lazy copy or not? Thanks, Peng std::vector<intv. v.push_back(1); v.push_back(2);
0
9881
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9727
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
10982
Oralloy
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...
1
10706
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,...
0
10331
tracyyun
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...
0
9480
agi2029
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...
1
7880
isladogs
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...
0
5718
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
2
4116
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.