Thread: How to do it?

  1. #1
    Registered User
    Join Date
    Oct 2006
    Location
    London
    Posts
    14

    How to do it?

    Example 1:
    Code:
    int variable0 = 0; 
    int variable1 = 1;
    int variable2 = 2;
    int varabile3 = 3;
    
    int someArray[4] = {10, 20, 30, 40};
    
    //now i can access array indices like: 
    someArray[variable0];
    someArray[variable1];
    someArray[variable2];
    someArray[variable3];
    Now I would like to do something like example above on the runtime:

    Example 2:
    Code:
    void addVariableName(std::string name) 
    {
    //add variable name and assign following number to it starting from 0
    }
    
    addVariableName("variable0");
    addVariableName("variable1");
    addVariableName("variable2");
    addVariableName("variable3");
    
    someArray[/*????*/]; //want to access element 0 here using string "variable0"
    someArray[/*????*/]; //want to access element 1 here using string "variable1"
    someArray[/*????*/]; //want to access element 2 here using string "variable2"
    someArray[/*????*/]; //want to access element 3 here using string "variable3"
    Is there any way to do it? (in the same time as in example 1)

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    If you use a std::map, you basically get a data structure with which you can use any data type you like to do indexing. For example:
    Code:
    #include <iostream>
    #include <map>
    #include <string>
    
    int main() {
        // a map from strings to ints
        std::map<std::string, int> data;
    
        data["one"] = 1;
        data["two"] = 2;
        data["forty-two"] = 42;
    
        std::string index = "forty-two";
        std::cout << "The decimal equivalent of \"" << index << "\" is "
            << data[index] << std::endl;
    
        return 0;
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Location
    London
    Posts
    14
    I thought about map, but then there will be some time wasted for searching elements in the map...
    Is there a quicker way?
    Last edited by Stiopa; 09-03-2010 at 01:12 PM.

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    On my compiler (g++), maps are implemented as a red-black tree. I guess other implementations could use hash tables or other data structures, but any way it's done it will be very fast. Seriously, I wouldn't worry about it.

    There are quicker ways. In one of my projects I had a sort of settings list, and I converted each string setting into an enumeration value and then always did indexing based on that. It was a really stupid idea, making me work much harder as a programmer for a fractional speed increase that I'd probably never even notice.

    Maybe you could describe more about what you're trying to do? . . . that way you'll receive more informed suggestions.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by dwks
    I guess other implementations could use hash tables or other data structures
    The complexity requirements of std::map does not fit a hash table implementation, but if you want to use a hash table, std::tr1::unordered_map would be something to consider.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Stiopa View Post
    I thought about map, but then there will be some time wasted for searching elements in the map...
    "wasted"?
    How is the time wasted if it is doing exactly what you want it to?
    It's not exactly slow to perform a map.find, it does not search through all entries just to find the one you want. It's far smarter than that.

    Quote Originally Posted by Stiopa View Post
    Is there a quicker way?
    Sure, you could just not do it at all.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

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

  7. #7
    Registered User
    Join Date
    Oct 2006
    Location
    London
    Posts
    14
    Quote Originally Posted by dwks View Post
    Maybe you could describe more about what you're trying to do? . . . that way you'll receive more informed suggestions.
    I will try...

    I have a file:
    Code:
    Field1 | Field2 | Field3 | Field4 | ... | Fieldn
    ------------------------------------------------
    data   | data   | data   | data   | ... | data 
    ------------------------------------------------
    .
    .
    .
    -----------------------------------------------
    data   | data   | data   | data   | ... | data 
    -----------------------------------------------
    File contains up to 30 different Fields and there might be over 100 000 records.


    I want to implement a class reading the whole file into
    Code:
    std::vector<std:vector<std::string> >
    where each inner vector contains all entries of particular field.

    Then I want to have a function, which would allow me to iterate through records:
    Code:
    bool GoToNextRecord(); //returns false if no more records
    And a function to get a particular field from given record:
    Code:
    std::string GetField(std::string fieldName);
    Now if I have a loop:
    Code:
    while(GoToNextRecord()){
           std::string str += GetField("Field8");
           str += GetField("Field1");
           str += GetField("Field2");
           str += GetField("Field4");
           str += GetField("Field10");
          //write str to file
    }
    if GetField() was retrieving field number from a map, then I would waste most of the time in this loop doing just that.

    Quote Originally Posted by iMalc View Post
    Sure, you could just not do it at all.
    Great advice - thanks!

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Well as they say, the fastest instruction is the one that is never executed.
    Though sure, I was totally lacking an explanation of an alternative.

    So in effect you want GetField() to get a value from the correct outer vector, and from the inner vector position corresponding to how many times GoToNextRecord() has ben called, right?

    Well then you're duplicating a lot of work. Each time through the loop you're constructing several strings from string literals, and essentially looking up the index of of the outer vector to find which inner vector corresponds to that field.
    The best thing you can do then is to resolve the field name to an outer vector index before the loop, and then inside the loop, just use the index.

    Then, as I've hoped, there wont be any such lookups by name, inside the loop at all. Not quite "not doing it at all", but "not doing it in the loop" is the next best thing.

    For the actual lookup, you could have a vector< pair<string, int> > and use std::lower_bound, which will be a tad faster than a map lookup.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

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

  9. #9
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by dwks View Post
    On my compiler (g++), maps are implemented as a red-black tree. I guess other implementations could use hash tables or other data structures, but any way it's done it will be very fast. Seriously, I wouldn't worry about it.
    VC++ also has it implemented as a red-black tree. Other implementations could use a different type of tree, though, I suppose.
    Lookup time is O(logn) for map. For hash maps, it is not as clear. The ordo depends on the implementation type of the hash table. If the hash table is proper balanced, the lookup time could be O(1). But then again, if it's fat, it could take linear time.
    Insertions are also a problem. Trees take O(logn) time, but hash tables could take O(N^2) time. It all depends on how well balanced it is when the insertion is done.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    std::map is very fast as Elysia and many have said. The only thing I would caution on, based on experience with the MSVS PJ Plaguer implementation, is you do not iterate through the collection in time critical loops. Iteration through the map is quite slow - sometimes as much as 4 times slower than iterating through a vector.

    But combine the map with a vector or some other data type and you get the best of both worlds. If iteration time is not important or you are not going to iterate the collection often then I would not worry about it. It all depends on what your requirements are as to what approach you will take.

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I suppose it would make more sense to iterate through a skip list. It should be constant time, and fast, if anything.
    Insertion is O(logn) amortized time (or guaranteed if you use a deterministic skip list).
    I have been pondering that, but never actually really tested it. There is no deterministic skip list in the library either
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,130
    How large is this file? Reading a large amount of data into stl structures seems unneccessary waste because of the memory overhead of each structure. Read your file into RAM in one continuous block. If you need to look up certain things fast, create pointer arrays to index this block. Jumping around in this pointer arrays may then be done by maps or something like that.
    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

Popular pages Recent additions subscribe to a feed