After doing a succcessful insert() or find() on a set<Tcontainer
is it possible to get the item number of this item in the set?
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
Additional info:
insert() returns a pair<Tand find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
After the insert() or find() the container won't be modified.
21  1572 
In article <g1**********@aioe.org>, bi*******@bilgekhanbilgekhan.net.tr
says...
After doing a succcessful insert() or find() on a set<Tcontainer
is it possible to get the item number of this item in the set?
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
Additional info:
insert() returns a pair<Tand find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
your_iterator = yourset.find(whatever);
std::distance(yourset.begin(), your_iterator);
--
Later,
Jerry.
The universe is a figment of its own imagination.
bilgekhan writes:
After doing a succcessful insert() or find() on a set<Tcontainer
is it possible to get the item number of this item in the set?
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
There are no "sequence numbers" for members of a set. Individual members of
sets are accessed via iterators.
Additional info:
insert() returns a pair<Tand find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
No, because there is no such a concept as a "sequence number". It doesn't
exist. A set is an opaque collection, with certain properties. The
collection contains a "set" of items. A number of operations are defined on
a set. That's it.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
iEYEABECAAYFAkg5nFIACgkQx9p3GYHlUOJdOACffjSkVb+8zH iUD+HIyucsSB9d
AVUAn20V5OkYlH+SNv0ook90UT02hj0h
=FY7F
-----END PGP SIGNATURE-----
"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrote:
After doing a succcessful insert() or find() on a set<Tcontainer
is it possible to get the item number of this item in the set?
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
Additional info:
insert() returns a pair<Tand find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
After the insert() or find() the container won't be modified.
set<int>::iterator it = s.insert( x ).first;
// or = s.find( x );
int seqNumb = distance( s.begin(), it );
"Jerry Coffin" <jc*****@taeus.comwrote:
bi*******@bilgekhanbilgekhan.net.tr says...
After doing a succcessful insert() or find() on a set<Tcontainer
is it possible to get the item number of this item in the set?
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
Additional info:
insert() returns a pair<Tand find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
your_iterator = yourset.find(whatever);
std::distance(yourset.begin(), your_iterator);
Yes, distance() does what I wanted, but it is VERY slow!
It seems each time it walks all items from the beginning to the
item in question, ie. it practically does a find().
That's unfortunately too inefficient for my needs.
Isn't there a better (a direct) method without traversing the set ?
FYI: If I program this without STL (and then even using an unordered array
--ie. each time doing a sequential search) then it is about 7 times
faster than the STL version that uses set<Tand distance() !
How come? :-)
The culprit is IMO the distance() call. One needs a better, a direct,
method without traversing the tree.
A better way would have been if the insert() and find() functions would
optionally deliver the distance value on the fly;
ie. STL needs to extend these 2 functions with a direct 'distance' option.
"Daniel T." <da******@earthlink.netwrote:
"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrote:
After doing a succcessful insert() or find() on a set<Tcontainer
is it possible to get the item number of this item in the set?
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
Additional info:
insert() returns a pair<Tand find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
After the insert() or find() the container won't be modified.
set<int>::iterator it = s.insert( x ).first;
// or = s.find( x );
int seqNumb = distance( s.begin(), it );
Yes, distance() does what I wanted, but it is VERY slow!
It seems each time it walks all items from the beginning to the
item in question, ie. it practically does a find().
That's unfortunately too inefficient for my needs.
Isn't there a better (a direct) method without traversing the set ?
FYI: If I program this without STL (and then even using an unordered array
--ie. each time doing a sequential search) then it is about 7 times
faster than the STL version that uses set<Tand distance() !
How come? :-)
The culprit is IMO the distance() call. One needs a better, a direct,
method without traversing the tree.
A better way would have been if the insert() and find() functions would
optionally deliver the distance value on the fly;
ie. STL needs to extend these 2 functions with a direct 'distance' option.
In article <g1**********@aioe.org>, bi*******@bilgekhanbilgekhan.net.tr
says...
[ ... ]
Yes, distance() does what I wanted, but it is VERY slow!
That's not terribly surprising.
It seems each time it walks all items from the beginning to the
item in question, ie. it practically does a find().
Yes, that's correct.
That's unfortunately too inefficient for my needs.
Isn't there a better (a direct) method without traversing the set ?
None of which I'm aware.
FYI: If I program this without STL (and then even using an unordered array
--ie. each time doing a sequential search) then it is about 7 times
faster than the STL version that uses set<Tand distance() !
How come? :-)
A set is composed of nodes connected by pointers. Each node is
separately allocated via the allocator for the set (which will use new,
unless you supply an allocator of your own). Those nodes will usually
have fairly poor locality of reference, which leads to poor cache usage
(among other things). The result is relatively slow traversal.
An array is required to be allocated as a single, contiguous block of
storage. This leads to relatively good locality of reference, better
cache usage, and (generally) relatively fast traversal.
The culprit is IMO the distance() call. One needs a better, a direct,
method without traversing the tree.
A better way would have been if the insert() and find() functions would
optionally deliver the distance value on the fly;
ie. STL needs to extend these 2 functions with a direct 'distance' option.
This requirement is sufficiently unusual that I doubt that'll happen.
Anything that supports random access iterators can do distance in
constant time.
Since a set is typically implemented as a balanced tree, you could
theoretically improve the speed of distance() by having each pointer in
a node also record the number of nodes in the subtree at which it points
(or at least in its left sub-tree). This would avoid traversing at least
part of the tree most of the time -- OTOH, maintaining those counts
would slow down insertions and deletions. TANSTAAFL.
--
Later,
Jerry.
The universe is a figment of its own imagination.
On May 26, 8:04 am, Jerry Coffin <jcof...@taeus.comwrote:
In article <g1di7e$8i...@aioe.org>, bilgek...@bilgekhanbilgekhan.net.tr
says...
[ ... ]
Yes, distance() does what I wanted, but it is VERY slow!
That's not terribly surprising.
It seems each time it walks all items from the beginning to the
item in question, ie. it practically does a find().
Yes, that's correct.
That's unfortunately too inefficient for my needs.
Isn't there a better (a direct) method without traversing the set ?
None of which I'm aware.
Perhaps the solution to his problem would be to use an
std::vector, and keep it sorted (using std::lower_bound to find
the insertion point). If insertions aren't too frequent, or
copying is fairly cheap, this can be even faster than an
std::set. And of course, given an iterator to an element, it's
trivial and very fast to find the elements sequence number.
--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
On 2008-05-26 01:34:32 -0400, "bilgekhan"
<bi*******@bilgekhanbilgekhan.net.trsaid:
"Daniel T." <da******@earthlink.netwrote:
>"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrote:
>>After doing a succcessful insert() or find() on a set<Tcontainer
is it possible to get the item number of this item in the set?
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
Additional info:
insert() returns a pair<Tand find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
After the insert() or find() the container won't be modified.
set<int>::iterator it = s.insert( x ).first;
// or = s.find( x );
int seqNumb = distance( s.begin(), it );
Yes, distance() does what I wanted, but it is VERY slow!
It seems each time it walks all items from the beginning to the
item in question, ie. it practically does a find().
That's unfortunately too inefficient for my needs.
Isn't there a better (a direct) method without traversing the set ?
I think you're asking the wrong question. What do you plan to do with
this "sequence number", and are there other ways to do the same thing?
--
Pete
Roundhouse Consulting, Ltd. ( www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
( www.petebecker.com/tr1book)
"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrote:
"Daniel T." <da******@earthlink.netwrote:
"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrote:
After doing a succcessful insert() or find() on a set<Tcontainer
is it possible to get the item number of this item in the set?
>
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
>
Additional info:
insert() returns a pair<Tand find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
After the insert() or find() the container won't be modified.
set<int>::iterator it = s.insert( x ).first;
// or = s.find( x );
int seqNumb = distance( s.begin(), it );
Yes, distance() does what I wanted, but it is VERY slow!
It seems each time it walks all items from the beginning to the
item in question, ie. it practically does a find().
How else could it be done?
FYI: If I program this without STL (and then even using an unordered array
--ie. each time doing a sequential search) then it is about 7 times
faster than the STL version that uses set<Tand distance() !
How come? :-)
Your comparing apples to oranges. In one implementation you are using an
unordered array where all the elements are contiguous, in the other
implementation the elements are ordered but not contiguous. But before
abandoning the set idea, make sure you have all optimizations turned on.
Many standard libraries have extensive error checking built in and make
a lot of calls that can be inlined, but the former doesn't get removed
and the latter doesn't get inlined unless optimizations are turned on.
The culprit is IMO the distance() call. One needs a better, a direct,
method without traversing the tree.
Like how?
A better way would have been if the insert() and find() functions would
optionally deliver the distance value on the fly
They would have to traverse the tree to do that.
As others have pointed out, "sequence numbers" aren't all that useful in
sets. It sounds like you would be better served by using a std::vector
and sorting it (using std::sort,) then you can do lookups with
std::lower_bound, upper_bound, equal_range, and binary_search and
getting the "sequence number" is simply a matter of a little pointer
math.
In article <611c02c0-da39-45cc-95aa-767706d1c0a8
@a70g2000hsh.googlegroups.com>, ja*********@gmail.com says...
[ ... ]
Perhaps the solution to his problem would be to use an
std::vector, and keep it sorted (using std::lower_bound to find
the insertion point). If insertions aren't too frequent, or
copying is fairly cheap, this can be even faster than an
std::set. And of course, given an iterator to an element, it's
trivial and very fast to find the elements sequence number.
Right -- I'd add, however, that my mention of random access iterators
instead of vectors was intentional. Under the circumstances at hand, a
deque might well be a better choice, since it halves the number of
elements that need to be shuffled for an average insertion.
--
Later,
Jerry.
The universe is a figment of its own imagination.
"Daniel T." <da******@earthlink.netwrote:
"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrote:
"Daniel T." <da******@earthlink.netwrote:
"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrote:
>
After doing a succcessful insert() or find() on a set<Tcontainer
is it possible to get the item number of this item in the set?
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
Additional info:
insert() returns a pair<Tand find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
After the insert() or find() the container won't be modified.
>
set<int>::iterator it = s.insert( x ).first;
// or = s.find( x );
>
int seqNumb = distance( s.begin(), it );
Yes, distance() does what I wanted, but it is VERY slow!
It seems each time it walks all items from the beginning to the
item in question, ie. it practically does a find().
How else could it be done?
See below.
FYI: If I program this without STL (and then even using an unordered array
--ie. each time doing a sequential search) then it is about 7 times
faster than the STL version that uses set<Tand distance() !
How come? :-)
Your comparing apples to oranges. In one implementation you are using an
unordered array where all the elements are contiguous, in the other
implementation the elements are ordered but not contiguous. But before
abandoning the set idea, make sure you have all optimizations turned on.
Many standard libraries have extensive error checking built in and make
a lot of calls that can be inlined, but the former doesn't get removed
and the latter doesn't get inlined unless optimizations are turned on.
The culprit is IMO the distance() call. One needs a better, a direct,
method without traversing the tree.
Like how?
See below.
A better way would have been if the insert() and find() functions would
optionally deliver the distance value on the fly
They would have to traverse the tree to do that.
Yes, of course! Therefore the traversion does not need
to be done again in distance() ! That's the point I'm trying
to make clear. If you reread my inital posting then you will see that
I said that I need the distance value immediately after an insert()
or find() call... Do you see what I mean? :-)
Currently the tree is traversed twice: once in insert() and find(),
and the second time in distance(). The second traversion is
IMO unneccessary if insert() and find() would store this value
somewhere internally, and distance() then just returns that value
w/o traversing the tree.
Maybe for this one can make a new function member like
"distance_last_added()" or something that. Another option would be
if insert() and find() would deliver it in a overloaded version...
As others have pointed out, "sequence numbers" aren't all that useful in
sets. It sounds like you would be better served by using a std::vector
and sorting it (using std::sort,) then you can do lookups with
std::lower_bound, upper_bound, equal_range, and binary_search and
getting the "sequence number" is simply a matter of a little pointer
math.
I need to get the seqnbr for each item that gets added to
the sorted collection, so then especially the sorting would be an overkill.
FYI: I'm doing this for the table-lookup routine (ie. a dictionary) of
a special data compressor for data records with common structure;
ie. it's not general purpose.
I just want to make this last point clear: I just have pointed out
IMO a shortcoming, performance issues or missing features
of the language that I in the field have encountered.
It's of course up to the language and library designers to
understand the problem and to fix or implement the functionality.
I'm just informing the people who are more involved in such issues.
If I were the designer of the library I would do it the way I described above.
bilgekhan wrote:
"Daniel T." <da******@earthlink.netwrote:
>"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrote:
"Daniel T." <da******@earthlink.netwrote:
"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrote:
After doing a succcessful insert() or find() on a set<Tcontainer
is it possible to get the item number of this item in the set?
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
Additional info:
insert() returns a pair<Tand find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
After the insert() or find() the container won't be modified.
set<int>::iterator it = s.insert( x ).first;
// or = s.find( x );
int seqNumb = distance( s.begin(), it );
Yes, distance() does what I wanted, but it is VERY slow!
It seems each time it walks all items from the beginning to the
item in question, ie. it practically does a find().
How else could it be done?
See below.
FYI: If I program this without STL (and then even using an unordered
array --ie. each time doing a sequential search) then it is about 7
times faster than the STL version that uses set<Tand distance() !
How come? :-)
Your comparing apples to oranges. In one implementation you are using an
unordered array where all the elements are contiguous, in the other
implementation the elements are ordered but not contiguous. But before
abandoning the set idea, make sure you have all optimizations turned on.
Many standard libraries have extensive error checking built in and make
a lot of calls that can be inlined, but the former doesn't get removed
and the latter doesn't get inlined unless optimizations are turned on.
The culprit is IMO the distance() call. One needs a better, a direct,
method without traversing the tree.
Like how?
See below.
A better way would have been if the insert() and find() functions would
optionally deliver the distance value on the fly
They would have to traverse the tree to do that.
Notice the "would".
Yes, of course! Therefore the traversion does not need
to be done again in distance() ! That's the point I'm trying
to make clear. If you reread my inital posting then you will see that
I said that I need the distance value immediately after an insert()
or find() call... Do you see what I mean? :-)
Currently the tree is traversed twice: once in insert() and find(),
No. Insert and find do _not_ traverse the tree. They only run through a path
from the root to a leave in the tree. During this process, the sequence
number is not established as a by-product.
and the second time in distance().
It's the first time.
[snip]
Best
Kai-Uwe Bux
"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrote:
It sounds like you would be better served by using a std::vector
and sorting it (using std::sort,) then you can do lookups with
std::lower_bound, upper_bound, equal_range, and binary_search and
getting the "sequence number" is simply a matter of a little pointer
math.
I need to get the seqnbr for each item that gets added to
the sorted collection, so then especially the sorting would be an overkill.
Then don't. Use std::lower_bound to do all your insertions and you won't
have to use sort and will be able to find sequence numbers with ease.
Use the right tool for the job and the job will be much easier.
FYI: I'm doing this for the table-lookup routine (ie. a dictionary) of
a special data compressor for data records with common structure;
ie. it's not general purpose.
Maybe you should consider a std::map then.
I just want to make this last point clear: I just have pointed out
IMO a shortcoming, performance issues or missing features
of the language that I in the field have encountered.
It's of course up to the language and library designers to
understand the problem and to fix or implement the functionality.
I'm just informing the people who are more involved in such issues.
If I were the designer of the library I would do it the way I described above.
It is, of course, your prerogative to design classes however you want.
By all means make a container that implements a red-black tree *and*
keeps track of sequence numbers. Maybe in doing so, you will come to
understand why std::set doesn't work that way, or maybe you will build a
container that others are eager to use.
In article <g1*********@aioe.org>, bi*******@bilgekhanbilgekhan.net.tr
says...
[ ... ]
A better way would have been if the insert() and find() functions would
optionally deliver the distance value on the fly
They would have to traverse the tree to do that.
Yes, of course! Therefore the traversion does not need
to be done again in distance() ! That's the point I'm trying
to make clear. If you reread my inital posting then you will see that
I said that I need the distance value immediately after an insert()
or find() call... Do you see what I mean? :-)
I see what you mean, but I think you're wrong. Consider (for example),
inserting an item that's going to be in the right subtree. insert()
compares the new item to the root node, finds that the new item is
larger than the root, and proceeds to the node to the right of the root.
In doing so, it has ignored the _entire_ left sub-tree.
When you use distance to find the position of the new node in the tree,
it cannot ignore the left subtree. Instead, it traverses the entire left
subtree counting each node as it goes. It then proceeds to count through
the right subtree until it reaches the point at which the new node was
inserted.
Currently the tree is traversed twice: once in insert() and find(),
and the second time in distance(). The second traversion is
IMO unneccessary if insert() and find() would store this value
somewhere internally, and distance() then just returns that value
w/o traversing the tree.
See above. The traversals are entirely _different_ from each other. The
traversal involved in an insertion or deletion is NOT sufficient to
determine the overall position of the new node in the tree.
You _could_ determine an _extremely_ rough estimate of the overall
position in the tree with only a little extra work. A set, map, etc., is
normally implemented as a balanced binary tree (e.g. red-black or AVL
tree). To maintain balancing, such a tree stores some information about
the _relative_ depths of the left and right subtrees in each node. They
limit the difference in height between the left and right subtrees
(though r-b trees and AVL trees impose slightly different restrictions).
Based upon that height difference, and the depth of the tree you _did_
traverse, you could very quickly compute upper and lower bounds for the
overall position of the new node in the tree -- but those bounds may
easily differ from each other by a factor of 2 or so. Getting the
correct number is going to be linear.
[ ... ]
I just want to make this last point clear: I just have pointed out
IMO a shortcoming, performance issues or missing features
of the language that I in the field have encountered.
It's of course up to the language and library designers to
understand the problem and to fix or implement the functionality.
I'm just informing the people who are more involved in such issues.
If I were the designer of the library I would do it the way I described above.
Maybe so -- but if you did, I doubt much of anybody would use your
library. In fact, except for this specific situation, even YOU probably
wouldn't use it. Making things work as you seem to want would involve a
_large_ slowdown in common operations in the hope of achieving a _small_
speedup for a relatively rare sequence of operations.
--
Later,
Jerry.
The universe is a figment of its own imagination.
Hi!
bilgekhan schrieb:
>As others have pointed out, "sequence numbers" aren't all that useful in
sets. It sounds like you would be better served by using a std::vector
and sorting it (using std::sort,) then you can do lookups with
std::lower_bound, upper_bound, equal_range, and binary_search and
getting the "sequence number" is simply a matter of a little pointer
math.
I need to get the seqnbr for each item that gets added to
the sorted collection, so then especially the sorting would be an overkill.
Your answer doesn't make sense to me. I guess you misunderstood the
advise. The advise propses what I had done if I were you:
DO NOT USE A STD::SET.
It doesn't fit your needs. The fact that you need the "index" of some
element shows it.
Replace the std::set<Whateverby std::vector<Whateverand try if you
can get along.
FYI: I'm doing this for the table-lookup routine (ie. a dictionary) of
a special data compressor for data records with common structure;
ie. it's not general purpose.
[snip]
If I were the designer of the library I would do it the way I described above.
Maybe all people writing a non general purpose data compressor with a
table-lookup routine will use your library then.
I probably wouldn't. Don't be offensed. It is just that std::set will
never have a "index_last_added" method. It's by design. If you need a
function like that you need to implement a new set class of your own.
Having done that come back and tell us how easy it was to determine the
exact size of a tree branch which is never visited or how to keep the
counts up-to-date which tell you the exact size, how you then managed to
keep the insert in O(log n). I think this is too complicated compared to
a sorted vector solution.
Frank
Frank Birbacher wrote:
Hi!
bilgekhan schrieb:
>>As others have pointed out, "sequence numbers" aren't all that useful
in sets. It sounds like you would be better served by using a
std::vector and sorting it (using std::sort,) then you can do lookups
with std::lower_bound, upper_bound, equal_range, and binary_search
and getting the "sequence number" is simply a matter of a little
pointer math.
I need to get the seqnbr for each item that gets added to
the sorted collection, so then especially the sorting would be an
overkill.
Your answer doesn't make sense to me. I guess you misunderstood the
advise. The advise propses what I had done if I were you:
DO NOT USE A STD::SET.
It doesn't fit your needs. The fact that you need the "index" of some
element shows it.
Replace the std::set<Whateverby std::vector<Whateverand try if you
can get along.
>FYI: I'm doing this for the table-lookup routine (ie. a dictionary) of
a special data compressor for data records with common structure;
ie. it's not general purpose.
[snip]
>If I were the designer of the library I would do it the way I
described above.
Maybe all people writing a non general purpose data compressor with a
table-lookup routine will use your library then.
I probably wouldn't. Don't be offensed. It is just that std::set will
never have a "index_last_added" method. It's by design. If you need a
function like that you need to implement a new set class of your own.
Having done that come back and tell us how easy it was to determine the
exact size of a tree branch which is never visited or how to keep the
counts up-to-date which tell you the exact size, how you then managed to
keep the insert in O(log n). I think this is too complicated compared to
a sorted vector solution.
Frank
I agree with your point, but feel like pointing out that it is possible
(almost trivial) to have every node on a tree keep track of how many
children it has. An insert operation would increment the value on the
return-trip if the insert was successful.
My question to the OP is, do you need to update the insert-position of
the elements *after* the last inserted element? say I have an existing set:
<1, 5, 6 so, 5 and 6 are at position 1 and 2 respectively...
I insert 3:
<1, 3, 5, 6 and determine that 3 is at position 1, do I need to update
the associated data with 5 and 6 to say they are now at position 2 and 3
respectively?
Also to the OP:
If you design your library for your specific use-cases, but in such a
way that it can easily be extended, you'll find yourself much happier.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
Daniel Pitts <ne******************@virtualinfinity.netwrote:
...it is possible (almost trivial) to have every node on a tree
keep track of how many children it has. An insert operation would
increment the value on the return-trip if the insert was successful.
I'm not so sure if an extra unsigned long per element can be considered
"trivial".
Daniel T. wrote:
Daniel Pitts <ne******************@virtualinfinity.netwrote:
>...it is possible (almost trivial) to have every node on a tree
keep track of how many children it has. An insert operation would
increment the value on the return-trip if the insert was successful.
I'm not so sure if an extra unsigned long per element can be considered
"trivial".
I said "almost trivial", which refers to difficulty, not space complexity.
Also, it could easily be a compile-time decision if you needed it or not.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
"Daniel Pitts" wrote:
Frank Birbacher wrote:
Don't be offensed. It is just that std::set will never have a
"index_last_added" method. It's by design. If you need a
function like that you need to implement a new set class of your own.
Having done that come back and tell us how easy it was to determine the
exact size of a tree branch which is never visited or how to keep the
counts up-to-date which tell you the exact size, how you then managed to
keep the insert in O(log n). I think this is too complicated compared to
a sorted vector solution.
I agree with your point, but feel like pointing out that it is possible
(almost trivial) to have every node on a tree keep track of how many
children it has. An insert operation would increment the value on the
return-trip if the insert was successful.
My question to the OP is, do you need to update the insert-position of
the elements *after* the last inserted element? say I have an existing set:
<1, 5, 6 so, 5 and 6 are at position 1 and 2 respectively...
I insert 3:
<1, 3, 5, 6 and determine that 3 is at position 1, do I need to update
the associated data with 5 and 6 to say they are now at position 2 and 3
respectively?
From point of application code it is sufficient to know the position of
just only the *last* successful insert() operation and of the
*last* successful find() operation.
Ie. in the application code there is no need to keep track of the positions
of the other items; just that of the latest successful insert() or find().
"Daniel Pitts" wrote:
Frank Birbacher wrote:
Don't be offensed. It is just that std::set will never have a
"index_last_added" method. It's by design. If you need a
function like that you need to implement a new set class of your own.
Having done that come back and tell us how easy it was to determine the
exact size of a tree branch which is never visited or how to keep the
counts up-to-date which tell you the exact size, how you then managed to
keep the insert in O(log n). I think this is too complicated compared to
a sorted vector solution.
I agree with your point, but feel like pointing out that it is possible
(almost trivial) to have every node on a tree keep track of how many
children it has. An insert operation would increment the value on the
return-trip if the insert was successful.
My question to the OP is, do you need to update the insert-position of
the elements *after* the last inserted element? say I have an existing set:
<1, 5, 6 so, 5 and 6 are at position 1 and 2 respectively...
I insert 3:
<1, 3, 5, 6 and determine that 3 is at position 1, do I need to update
the associated data with 5 and 6 to say they are now at position 2 and 3
respectively?
From point of application code it is sufficient to know the position of
just only the *last* successful insert() operation and of the
*last* successful find() operation.
Ie. in the application code there is no need to keep track of the positions
of the other items; just that of the latest successful insert() or find().
In the example above, after inserting 3 into this set
it just shall be possible to get the position
of this latest new item (ie. here the position of 3, ie. 1).
There is no need for the library to keep track or to update
anything defined in the application code that references items of the set.
Ie. there are no such references (at least not in my code).
Daniel T. wrote:
Daniel Pitts <ne******************@virtualinfinity.netwrote:
>...it is possible (almost trivial) to have every node on a tree
keep track of how many children it has. An insert operation would
increment the value on the return-trip if the insert was successful.
I'm not so sure if an extra unsigned long per element can be considered
"trivial".
It's not really "extra": Any balanced tree has to store some additional
information. This information can be _traded_ for the unsigned long since
size information can be used to rebalance. Then, alignment and memory
quantization from the allocator will very likely imply that
2 pointers + 1 unsigned long + user data
is simply indistinguishable from
2 pointers + balancing info + user data
Best
Kai-Uwe Bux This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: dan |
last post by:
I was recently surprised, and quite shocked in fact, to find that
Python treats negative indices into sequence types as if they were
mod(length-of-sequence), at least up to -len(seq).
This fact...
|
by: Ronak |
last post by:
Hi,
I'm encountering a very erratic behavior of STL function
random_shuffle() in my code. I have vectors s1 and s2 each having
elements {1, 2, 3, 4, 5, 6} which i want to randomly shuffle.
My...
|
by: J. |
last post by:
Hello all,
I need some assistance. I've been out of the C++ game way too long and
I need some help getting back up to speed. I'm taking a class where STL
is mostly covered...I know alot of...
|
by: Sigmathaar |
last post by:
Hi, I'm need some advice about lists and vectors. I'm doing a program
who needs to have sequential access of a non ordered unit of objects
whose size decreases almost each time the sequence is...
|
by: Vadim |
last post by:
Hi!
I have a STL string, which I need to convert to low case.
In VC 6 I used:
string sInputBuffer = _strlwr((char*)sBuffer.c_str());
However, now in MSVC.NET 2005 I am getting a warning, that...
| | |
by: Piotr |
last post by:
In Effective STL item 9 "Choose carefully among erasing options", it
has this example:
bool badValue(int x); // returns whether x is 'bad'
c.erase ( remove_if(c.begin(), c.end(), badValue),...
|
by: Andrew Roberts |
last post by:
Any more info on this? Anyone know when it will be released?
|
by: davydany |
last post by:
Hey guys...a n00b Here for this site.
I'm making a sequence class for my C++ class. And The thing is in the array that I have, lets say i put in {13,17,38,18}, when i see the current values for the...
|
by: ademirzanetti |
last post by:
Hi there !!!
I would like to listen your opinions about inherit from a STL class
like list. For example, do you think it is a good approach if I
inherit from list to create something like...
|
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,...
|
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,...
| | |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
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...
|
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...
|
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 ...
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| | |
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...
| |
