C++ STL Question: Using Maps
-
Questions for you genius coders out there: 1) Are the iterators for maps produced random? I need to be able to call random_shuffle, and I want to make sure I can with this type of container. 2) Is there a way to insert to the front of a map, even if the key I want to insert isn't lexiographically the first key listed? (i.e. if I call begin, then I want to see it first) 3) Can I store dynamically created objects in a map? Thanks very much in advance! -- modified at 0:03 Thursday 27th April, 2006
- They are bidirectional iterators, not random access. 2) No. 3) Yes - store a pointer to the object. Calling
random_shufflemakes no sense for amap. Steve
- They are bidirectional iterators, not random access. 2) No. 3) Yes - store a pointer to the object. Calling
-
Questions for you genius coders out there: 1) Are the iterators for maps produced random? I need to be able to call random_shuffle, and I want to make sure I can with this type of container. 2) Is there a way to insert to the front of a map, even if the key I want to insert isn't lexiographically the first key listed? (i.e. if I call begin, then I want to see it first) 3) Can I store dynamically created objects in a map? Thanks very much in advance! -- modified at 0:03 Thursday 27th April, 2006
1 - No, maps are hash tables. So, I believe that they generate a hash and use that to decide what bucket to put stuff into 2 - I don't believe so 3 - sure. If you do, it's the memory address that will be hashed, I would think, and I would think that would be as close as you'd get to a random insert order, although I still don't think you can shuffle it. Christian Graus - Microsoft MVP - C++
-
1 - No, maps are hash tables. So, I believe that they generate a hash and use that to decide what bucket to put stuff into 2 - I don't believe so 3 - sure. If you do, it's the memory address that will be hashed, I would think, and I would think that would be as close as you'd get to a random insert order, although I still don't think you can shuffle it. Christian Graus - Microsoft MVP - C++
Ok then what's the best data structure for: 1) Being able do a random_shuffle () on, 2) Being able to search by key to get to a value. I'm using vector right now, but I have a key-value pair combination that I need to update fairly often, so it seems like a map would be ideal for this..., but if this is the case, I need a way of randomly shuffling the map somehow, so when I do an interator and go from the beginning to the end, its random every time.
-
1 - No, maps are hash tables. So, I believe that they generate a hash and use that to decide what bucket to put stuff into 2 - I don't believe so 3 - sure. If you do, it's the memory address that will be hashed, I would think, and I would think that would be as close as you'd get to a random insert order, although I still don't think you can shuffle it. Christian Graus - Microsoft MVP - C++
Christian Graus wrote:
1 - No, maps are hash tables.
Actually in general
std::maps are red-black trees. Steve -
Christian Graus wrote:
1 - No, maps are hash tables.
Actually in general
std::maps are red-black trees. SteveDamn - of course they are. I've been in the C# wilderness for far too long... Christian Graus - Microsoft MVP - C++
-
Damn - of course they are. I've been in the C# wilderness for far too long... Christian Graus - Microsoft MVP - C++
Christian Graus wrote:
C# wilderness
So you started as a C++ programmer? How do you find C#? I'm a C++ programmer who is resistant to the whole dotNET phenomenon and as such interested in what a C++ programmer has to say about it. Steve
-
Ok then what's the best data structure for: 1) Being able do a random_shuffle () on, 2) Being able to search by key to get to a value. I'm using vector right now, but I have a key-value pair combination that I need to update fairly often, so it seems like a map would be ideal for this..., but if this is the case, I need a way of randomly shuffling the map somehow, so when I do an interator and go from the beginning to the end, its random every time.
Can't you turn the keys into a list and then shuffle that ? How often do you need to shuffle them ? I'd think a list of the keys which you shuffle would be the way to go here. Christian Graus - Microsoft MVP - C++
-
Christian Graus wrote:
1 - No, maps are hash tables.
Actually in general
std::maps are red-black trees. SteveIs there anyway of shuffling a map, or other hashtable like thing? For instance, most of the time I want to iterate from the first to last element... but about once an hour, I need to be able to select an element based on a key and update its value. On the hour I am taking data from a list of m elements and updating n elements (where n>m, and n < 100). And there is a key that elements m and n share in common. Do I optimize for the general case which is just general cycling thru a list from beginning to end? I must also shuffle every time. So I was thinking a vector would be ideal. Your thoughts? Thanks!
-
Christian Graus wrote:
C# wilderness
So you started as a C++ programmer? How do you find C#? I'm a C++ programmer who is resistant to the whole dotNET phenomenon and as such interested in what a C++ programmer has to say about it. Steve
Yes, I was a C++ programmer for a long time. When C# was announced, we made fun of it. Then I moved to writing web apps, and ASP.NET was just streets ahead of ASP, hence the move to C#. I think C# is nice, I like it a lot. I think with 2.0, it's finally turning into it's own language, all the more so when 3.0 comes out, with LINQ, etc. However, overall there are definatley things about it that still bug me to this day. I've fairly recently been doing some C++ work, which has just gone full time, and I'm enjoying it very much. Having said that, I write an image processing app in C#, and that's still happening in my spare time. The focus has moved to C++ again, but I am happy to move between the two languages on a daily basis, they both have strengths and weaknesses. For a desktop app, I'd say C# is faster, and better supported. C++ is still more powerful and has the better std library. It's a question for me now of choosing the tool for the job. It still hurts to admit that when I use C#, I'm compiling to the same runtime as VB does now :-) Christian Graus - Microsoft MVP - C++
-
Ok then what's the best data structure for: 1) Being able do a random_shuffle () on, 2) Being able to search by key to get to a value. I'm using vector right now, but I have a key-value pair combination that I need to update fairly often, so it seems like a map would be ideal for this..., but if this is the case, I need a way of randomly shuffling the map somehow, so when I do an interator and go from the beginning to the end, its random every time.
You can get the best of both worlds by combining the two: use a std::map for fast access to data but a std::vector of std::map::iterators into the std::map which you can shuffle. Here's an example using sets. ------------ // Console.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include #include #include #include #include using namespace std; typedef std::set StringSet; typedef StringSet::const_iterator StringSet_CI; typedef std::vector StringSetIterators; typedef StringSetIterators::const_iterator StringSetIterators_CI; int main(int argc, char* argv[]) { const char* Names[] = {"Bob", "Sue", "James", "Ralph", "Steve", "Paul", "Kim", "Mary"}; const char** pEndNames = &Names[sizeof(Names)/sizeof(Names[0])]; // A map of strings. StringSet strings; // Fill the set with the names. copy(Names, pEndNames, inserter(strings, strings.end())); // Output the set to the console. cout << "Names in set:" << endl; copy(strings.begin(), strings.end(), ostream_iterator(cout, "\n")); cout << endl << endl; // Vector of set iterators. StringSetIterators ssi; StringSet_CI e = strings.end(); for ( StringSet_CI i=strings.begin(); i!=e; ++i ) { ssi.push_back(i); } for ( int times=1; times<=3; ++times ) { // Shuffle the iterators. random_shuffle(ssi.begin(), ssi.end()); // Output through the shuffled iterators. cout << "Shuffled names:" << endl; StringSetIterators_CI ee = ssi.end(); for ( StringSetIterators_CI ii=ssi.begin(); ii!=ee; ++ii ) { cout << *(*ii) << endl; } cout << endl << endl; } return 0; } Steve
-
Yes, I was a C++ programmer for a long time. When C# was announced, we made fun of it. Then I moved to writing web apps, and ASP.NET was just streets ahead of ASP, hence the move to C#. I think C# is nice, I like it a lot. I think with 2.0, it's finally turning into it's own language, all the more so when 3.0 comes out, with LINQ, etc. However, overall there are definatley things about it that still bug me to this day. I've fairly recently been doing some C++ work, which has just gone full time, and I'm enjoying it very much. Having said that, I write an image processing app in C#, and that's still happening in my spare time. The focus has moved to C++ again, but I am happy to move between the two languages on a daily basis, they both have strengths and weaknesses. For a desktop app, I'd say C# is faster, and better supported. C++ is still more powerful and has the better std library. It's a question for me now of choosing the tool for the job. It still hurts to admit that when I use C#, I'm compiling to the same runtime as VB does now :-) Christian Graus - Microsoft MVP - C++
When you say, "C# is faster" do you mean faster to program or faster at runtime? Steve
-
When you say, "C# is faster" do you mean faster to program or faster at runtime? Steve
I took it to mean "faster to develop", but it all depends on your "implementation". You can easily write some C++ code that doesn't perform well, as well as some C# code that you think will perform well, but doesn't at all, because it's doing so much for you behind the scenes.
- S 50 cups of coffee and you know it's on!
-
I took it to mean "faster to develop", but it all depends on your "implementation". You can easily write some C++ code that doesn't perform well, as well as some C# code that you think will perform well, but doesn't at all, because it's doing so much for you behind the scenes.
- S 50 cups of coffee and you know it's on!
I accept that if you're going to compare you can't compare a fast algorithm in langauge "a" with a slow one in language "b" and conclude that language "a" is faster. Steve
-
I accept that if you're going to compare you can't compare a fast algorithm in langauge "a" with a slow one in language "b" and conclude that language "a" is faster. Steve
Is there something faster in C# than C++, besides development time? Haven't seen any benchmarks, but I'll bet (something insignificant) C++ will equal or better C#. Bring on the humble pie, I'm hungry... :-D (I mean, same algorithm-wise, like quick sort, etc....)
- S 50 cups of coffee and you know it's on! -- modified at 1:57 Thursday 27th April, 2006
-
Is there something faster in C# than C++, besides development time? Haven't seen any benchmarks, but I'll bet (something insignificant) C++ will equal or better C#. Bring on the humble pie, I'm hungry... :-D (I mean, same algorithm-wise, like quick sort, etc....)
- S 50 cups of coffee and you know it's on! -- modified at 1:57 Thursday 27th April, 2006
Steve Echols wrote:
Is there something faster in C# than C++
I would also say no. But it's one thing so guess and another to know. Also, even if it is slower at runtime, one could still ask "how much slower?" - Did the lack of runtime speed present a problem? Steve
-
Is there anyway of shuffling a map, or other hashtable like thing? For instance, most of the time I want to iterate from the first to last element... but about once an hour, I need to be able to select an element based on a key and update its value. On the hour I am taking data from a list of m elements and updating n elements (where n>m, and n < 100). And there is a key that elements m and n share in common. Do I optimize for the general case which is just general cycling thru a list from beginning to end? I must also shuffle every time. So I was thinking a vector would be ideal. Your thoughts? Thanks!
Yeah, I think a vector sounds like the best choice. Steve
-
Steve Echols wrote:
Is there something faster in C# than C++
I would also say no. But it's one thing so guess and another to know. Also, even if it is slower at runtime, one could still ask "how much slower?" - Did the lack of runtime speed present a problem? Steve
Yeah, I don't know either, but I would guess no. I've only done a few apps in C#, and the speed of something equivalent in C++, on the same machine, was very disappointing. It's not just the runtime load that bothers me, it's the speed of the whole app that seems "sluggish". I thought once it was JITted, then everything is cool, but it seems like every .net app I've used is just painfully slow! (Maybe I should upgrade my 386 :))
- S 50 cups of coffee and you know it's on!
-
When you say, "C# is faster" do you mean faster to program or faster at runtime? Steve
C# is faster to develop in, especially GUI stuff. C++ is plainly faster assuming that both code sets impliment the same algorithms. I did move code from C# to C++ once before tho, and it was a LOT slower. When I was done, it was a fair bit faster, I forget why it was so slow to start with, something to do with passing parameters forcing a copy, I think. Christian Graus - Microsoft MVP - C++
