Thread: Lists: adding fields (not nodes) & more

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    28

    Question Lists: adding fields (not nodes) & more

    (Console C++ Application, to run on a 486 dx2 32 bit, 16 on dos)

    I have to load this database, where the user gets to choose which fields are to be loaded. Also new fields not in db may be created on request, some may be removed as well.

    Note I'm talking about fields inside the structure, not nodes of the list.

    If you're thinking of making one big struct with all posible fields and some generic fields for those who the user may add, and load all even only displaying those chosen by the user, please don't reply. I can't do that: memory is precious, load time is even more precious!
    The only thing I could think of is making maaaaaaaaany separate lists, one for each field, which later found to be the same time/space waste, only messier...

    If somehow someone achieves this, here's my "& more" problem: what would be an efficient way of sorting this list by n-criteria (criteria and criteria priority chosen by the user), criteria being numeric/alphanumeric order of any of the fields in the list?
    The main problem imo is that fields would need to be somehow generic in order to achieve a generic sorting method.

    The complexity of both problems makes me think that perhaps lists might not be the optimum structure for this, but I can't think of a better one...

    (Hint: somehow almost every db program out there did it...both things. And Grid, and FlexGrid controls on VB do it, Delphi analogue controls do it as well, even though none of those support n-sorting)

    Well, any feedback on the matter will be greatly appreciated even if it doesn't solve my problem. Thx in advance!! Bye!

    Mariano Lopez-Gappa (20) from Argentina

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    I had a similar situation recently, but not quite the same.

    I solved this problem using a vector of vectors. My fields were always strings, whereas it sounds like your fields might include different datatypes. I then sorted the outer vector with a special sorting function object that took the appropriate column to sort by. I used stable_sort in <algorithm> so that you could sort by multiple columns. The sorting function object would then return true if the appropriate column of the first vector was less than the appropriate column of the second vector.

    You might be able to use boost::any instead of strings if you need multiple datatypes, but it's been awhile since I used it so I don't remember if it is perfectly appropriate. Also, while my solution was short, fast and effective, your requirements might make you shy away from the template based tools I used. I think you should give them a look though, since they'll be pretty fast if you use them correctly.

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    28
    About the vector inside vector:

    Yeah, I thought of this, the main reasons from which I discarded it were:

    -Nodes are to be added and removed, and of course both things happen on run-time where the data is already multi sorted. So I would have to move everything below the affected "vector node" one step down or one step up on each case...that ain't looking really fast....

    -I'm not sure of this (I'm kinda migrating from Pascal though I know enough about C), but aren't vectors static memory? If so, they won't work for me. Too much waste memory usage, and time consuming at load time...

    Thx for the reply!!

    Mariano Lopez-Gappa

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    vectors do not use static memory, they use dynamic memory, and grow as necessary. I chose them because in my app, once the data was filled, no new items were added or removed, and sorting a vector is faster than sorting a list (thanks to random access). You could use the same technique with a deque instead of a vector. The cost of inserting and removing from the middle of a deque is much smaller than with a vector, but random access iterators are available to take advantage of stable_sort and the faster sort algorithm.

    For the past few minutes I've been playing with boost::any. It might be a bit more cumbersome than just converting all your data to a string (that can be displayed to the user anyway).

  5. #5
    Registered User
    Join Date
    Nov 2005
    Posts
    28
    Wow Daved, that really sounded interesting!!

    Yeah I've seen something like char variable[] where you don't define length...didn't know it would work. Cool! Can I remove an added row/col?

    Still the big amount of moving when the matrix gets 1MB heavy (and it might get even higher) would be unacceptable, I could though add a "enable flag" for removed rows/cols. This won't work with added ones.

    If I can't remove elements from the matrix, the user won't have the feature to "troubleshoot latency by removing rows/cols" when the db gets too heavy...

    Could you tell me more about those "stable_sort" and "faster sort" algorithms? Also how to apply that "boost::any" technique with vectors...

    I haven't found a translation to spanish to "deque" , it looks like it might be something like stack or queue, in which case I wouldn't know how to add fields to the struct, right how when I started...HEEEEEEEELP!!!

    Thx a lot for your time,

    Mariano Lopez-Gappa


    PS-LIKE EDIT: even though all I've said, the matrix idea looks like the heading choice from now on, given the dynamic growth. If it were able to dynamically delete rows/cols, it would be definetly the best choice.
    Last edited by Mariano L Gappa; 11-09-2005 at 03:10 PM.

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    I played around with it, because this is an interesting topic, and I have some code that runs on VC++ 7.1 as long as you have Boost downloaded and its include directory (Boost\include\boost-1_32) added to the Additional Include Directory field in the Project Properties.
    Code:
    #pragma warning(disable: 4512)
    
    #include <iostream>
    #include <deque>
    #include <string>
    #include <algorithm>
    #include <boost/variant.hpp>
    
    
    typedef std::deque<boost::variant<double, std::string> > data_row;
    typedef std::deque<data_row> data_grid;
    void OutputGrid(const data_grid& the_grid);
    
    class column_sorter
    {
    public:
        column_sorter(data_row::size_type column) : column_(column) { }
        bool operator()(const data_row& left, const data_row& right)
        {
            return left[column_] < right[column_];
        }
    private:
        data_row::size_type column_;
    };
    
    int main()
    {
        // start with 3 empty rows
        data_grid the_grid(3);
    
        // Fill those rows with two columns, int and string.
        the_grid[0].push_back(37);
        the_grid[0].push_back(std::string("thirty-seven"));
        the_grid[1].push_back(-1);
        the_grid[1].push_back(std::string("negative one"));
        the_grid[2].push_back(88);
        the_grid[2].push_back(std::string("eighty-eight"));
    
        OutputGrid(the_grid);
    
        // Add two rows with equal string values.
        data_row new_row;
        new_row.push_back(74);
        new_row.push_back(std::string("seventy-four"));
        the_grid.push_back(new_row);
        new_row[0] = 73;
        the_grid.push_back(new_row);
    
        // Insert a row.
        new_row[0] = -2;
        new_row[1] = std::string("negative two");
        the_grid.insert(the_grid.begin() + 2, new_row);
    
        OutputGrid(the_grid);
    
        // Sort by the second column.
        std::stable_sort(the_grid.begin(), the_grid.end(), column_sorter(1));
    
        OutputGrid(the_grid);
    
        // Sort by the first column.
        std::stable_sort(the_grid.begin(), the_grid.end(), column_sorter(0));
    
        OutputGrid(the_grid);
    
        // Sort by the second column again (notice the 73 and 74 remained the same).
        std::stable_sort(the_grid.begin(), the_grid.end(), column_sorter(1));
    
        OutputGrid(the_grid);
    
        std::cin.get();
    }
    
    void OutputGrid(const data_grid& the_grid)
    {
        for (data_grid::const_iterator cur_row = the_grid.begin(),
            end_row = the_grid.end();
            cur_row != end_row; ++cur_row)
        {
            for (data_row::const_iterator cur_val = cur_row->begin(),
                end_val = cur_row->end();
                cur_val != end_val; ++cur_val)
            {
                if (cur_val != cur_row->begin())
                    std::cout << ", ";
                std::cout << *cur_val;
            }
            std::cout << std::endl;
        }
        std::cout << "\n----------------\n" << std::endl;
    }

  7. #7
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    I haven't found a translation to spanish to "deque" , it looks like it might be something like stack or queue, in which case I wouldn't know how to add fields to the struct, right how when I started...HEEEEEEEELP!!!
    "deque": pronounced deck. A double ended que. Performance differences between vector and deque: http://www.gotw.ca/gotw/054.htm
    Last edited by 7stud; 11-09-2005 at 03:46 PM.

  8. #8
    Registered User
    Join Date
    Nov 2005
    Posts
    28
    Well, there's much of this code that I don't fully understand, though I suspect what it should logically do...but I won't be able to compile it on a 486dx2...VC will need at least W98...

    Still thanks a lot for the code and I will take it on account, at least what I can get of it.

    Could you tell me more about the things I wrote on my last post?

    Thx a lot man!

    Mariano Lopez-Gappa

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    As for your questions:

    >> Yeah I've seen something like char variable[] where you don't define length...didn't know it would work. Cool! Can I remove an added row/col?

    Yes, with the standard containers like vector, deque, and list, you can add or remove rows any time you want. My code above adds rows to the end, and inserts one into the middle.

    >> Still the big amount of moving when the matrix gets 1MB heavy (and it might get even higher) would be unacceptable, I could though add a "enable flag" for removed rows/cols. This won't work with added ones.

    The deque should minimize this problem, since it is implemented to minimize moving (only a single chunk of elements would be moved, instead of every element after the affected one). Your display code might be another issue.

    >> Could you tell me more about those "stable_sort" and "faster sort" algorithms?

    The C++ standard library has algorithms in <algorithm> that sort your containers for you based on your sorting criterion. The sort() method just sorts everything. The stable_sort method is a little slower, but it keeps two items that are equal in the same order that you started with. This is useful for when you want to sort by multiple columns. For example, in windows explorer, if you want to sort by file type, then by Date Modified, it won't let you, because it re-sorts the entire list whenever you pick one column to sort by. A stable_sort would keep the previous sort order for all things that were equal, so you could sort by date first, then by type, and all items of the same type would still be sorted by date.

    >> Also how to apply that "boost::any" technique with vectors...

    I realized after some searching that boost::any might not be right. boost::variant worked well for me above, but again, it depends on your situation and how dynamic the data types are. You have to go to Boost.org and download the latest boost version. Then you just have to add it to your include path (there are no libs to link to for the any or variant classes).

    >> I haven't found a translation to spanish to "deque" , it looks like it might be something like stack or queue, in which case I wouldn't know how to add fields to the struct, right how when I started...HEEEEEEEELP!!!

    A deque (pronounced "deck") is a double-ended queue, which is generally implemented as a series of fixed sized chunks of memory. It is just a C++ container class like std::list or std::vector. There are online reference sites that have examples of its interface, and you can see some usage in my example above.


    My suggested solution might be too advanced if you aren't used to the STL or templates yet, but it worked well for me (without the variant part). You'll probably have to spend lots of time getting used to each new class and function before you can get it working for you, but if this is an important task you are completing, it might be worth it.

  10. #10
    Registered User
    Join Date
    Nov 2005
    Posts
    28

    Thumbs up

    Great!! Well I won't take more of your time since you provided me with a load of information which I'll have hours and hours to research from. Thx for all the help as you've pointed me on the right direction! You'll probably see me again soon around this forum with the outcome of my research and some new elaborate questions.

    Thx!! Byezzzz!!!

  11. #11
    Registered User
    Join Date
    Nov 2005
    Posts
    28
    hey wait wait EUREKA!! I might have found an alternate solution!

    Can't I make a list holding a vector-deque inside?? This way there would be n fields (if user needs one more, vector-deque grows) and I sort nodes as a list!! That would be awesome!! What I don't know is if the struct of the list would hold a vector-deque of unknown size...

    Code:
    struct tnode
    {
            char *fields[];
            tnode *prev, *next;
    };

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    When I'm talking about lists, deques, and vectors, I'm talking about the standard C++ containers, not your own versions like what you are showing in your code example. I don't know if a good standard library implementation is available on your platforms, so you might have to do your own, but all my comments above referred to STL classes.

    As to your question, it is the outer container that matters. So if the outer container is a list, sorting it will be slower, but inserting and removing will be faster. If the outer container is a vector, sorting will be faster, but inserting and removing will be slower. If the outer container is a deque, both operations will be fast. The best solution, if you will be using C++ and its standard library, is a deque of nodes, and each node can hold whatever you want.

    If you can't use C++'s STL like in my code example, and need to use regular arrays and pointers like in your example, you might try asking the question in the C forum, since there might be better C specific solutions for that there.

  13. #13
    Registered User
    Join Date
    Nov 2005
    Posts
    28

    Question

    Nono, I'll use STL, I'm reading a tutorial as I speak. That code was an example of the idea with concepts I could understand.

    If I could pull off the deque inside list thing it'd be great.

    Sorting the list won't be that much slower than deque I think...in both I'll still have to compare the same amount of values, only on deques the random thing will help, on list I'll just iterate till NULL.

    Add/Remove will be instantaneous compared to deque...WHEN it is about nodes, not when we talk about fields.

    I'll still have the n-field thing that the dynamic growth provides...


    Yet the question remains...Do you know if I can nest a STL deque inside a STL list, given that the deque's size would be unknown?

  14. #14
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Yes, you can nest a deque inside a list, or a list inside a deque, or a vector inside a list, etc. Each container can be nested inside of any other. It would take a little extra effort to make sure each inner container had the same size, but it could work fine.

    Another reason that you might want to make the outer container a deque is that the stable_sort won't work on the list, so you'd have to make your version (which might be extra slow) if you wanted to sort by multiple columns. I found the usage of stable_sort to be extremely helpful in my grid. If it's not a requirement of yours, then maybe the list would be ok.

  15. #15
    Registered User
    Join Date
    Nov 2005
    Posts
    28
    Well, all has been said. For now, the chosen method will be deque inside list, and i'll make my own multi sort and = check. Later on I might find nesting deques more efficient, I'll make sure to check both ways. Thanks for helping me for 5 hours, you've been reaaally helpful!

    THX A BUNCH! BYEZ!

    Mariano Lopez-Gappa

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked List Sorting
    By algatt in forum C Programming
    Replies: 5
    Last Post: 09-15-2007, 12:41 PM
  2. Adding nodes to a linked list
    By bluescreen in forum C Programming
    Replies: 4
    Last Post: 11-09-2006, 01:59 AM
  3. SVN Import Causes Crash
    By Tonto in forum Tech Board
    Replies: 6
    Last Post: 11-01-2006, 03:44 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. help with adding fields
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 04-22-2002, 07:15 PM