CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10
  1. #1
    Join Date
    Oct 2015
    Posts
    1

    Question from static to vector

    I have a spare parts shop. My supplier gave me his huge database of product references (unsigned int).

    I want to be able to enter the product reference # on my computer and immediately get the corresponding list of item codes & serial numbers for that product.

    Each product reference can have unlimited item codes (by group of 3 char - no string please!) & serial numbers (unsigned int) SEE BELOW

    My level of C++ is weak, however I know how to read a comma separated raw file and load it into static arrays.

    The problem is that some products only have 1 item code + 1 serial number, and others have more than 1000!

    So I need to create dynamic arrays (vectors ?) (otherwise I would need to buy 2048GB of RAM!!!)

    What is the simplest way?

    Thanks!

    ------------------------------------------------------------------------------------------------------------
    Examples :

    Reference #16732 has 4 item codes and 4 serial numbers:
    Reference #116840 has 1 item code and 1 serial number:
    Reference #169699400 has 2 item codes and 2 serial numbers:

    itemCode[16732][0][0]='1' itemCode[16732][0][1]='2' itemCode[16732][0][2]='U' serialNum[16732][0]=454562
    itemCode[16732][1][0]='U' itemCode[16732][1][1]='4' itemCode[16732][1][2]='Z' serialNum[16732][1]=65465
    itemCode[16732][2][0]='M' itemCode[16732][2][1]='6' itemCode[16732][2][2]='A' serialNum[16732][2]=189456
    itemCode[16732][3][0]='Z' itemCode[16732][3][1]='P' itemCode[16732][3][2]='Y' serialNum[16732][3]=894461

    itemCode[116840][0][0]='U' itemCode[116840][0][1]='P' itemCode[116840][0][2]='1' serialNum[116840][0]=65465

    itemCode[169699400][0][0]='T' itemCode[169699400][0][1]='5' itemCode[169699400][0][2]='B' serialNum[169699400][0]=848947
    itemCode[169699400][1][0]='7' itemCode[169699400][1][1]='Y' itemCode[169699400][1][2]='N' serialNum[169699400][1]=561135

  2. #2
    Join Date
    Jul 2008
    Location
    WV
    Posts
    5,362

    Re: from static to vector

    I'm not really a C programmer, been a long time since I even looked at it but the task at hand sounds like it should use a database and SQL queries.
    Always use [code][/code] tags when posting code.

  3. #3
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: from static to vector

    As a rule of thumb, never use (dynamic) arrays. vector and friends are almost always better.

    In your particular case, I suggest you store each itemCode in a an std::array<char, 3>.

    From there, you store the itemCodes and the serial numbers of specific part in a vector.

    Finally, you'll want to put your spare parts in a *(unordered_)map* that will map a reference number (unsigned long, probably), to what you want (itemCodes/serialNums). The reason you want a map here, and not an array/vector, is that the lookup is not a contiguous one, nor does it start at 0. You could have a part whose reference number is ULONG_MAX, and you do NOT want to allocate that much.

    Note that the above describes storage. Wrapping certain things in structs would definitely help For example, you could have a "Part" struct, that holds its reference number, and a list (vector) of its "PartIdentifiers". A PartIdentifier would be a struct that holds an item code, and its matching serialNum (it seems from your example that these come in pairs)? From there you can create a map that will help you lookup a part from its identifier.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  4. #4
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: from static to vector

    The problem with using std::array for this...

    you'll be reserving the size of the array in a modifiable memory segment.
    and you'll have the actual data in a read-only section of memory.
    the read only segment will be copied/assigned into the modifiable one at runtime.

    If the array is large, that's not an efficient way to go about it, and could even mean you can't fit it in memory.

    You either want a static const raw (c-style) array.
    Or you want a C++ wrapper around one.

  5. #5
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: from static to vector

    I agree that this is a job for a database.

  6. #6
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: from static to vector

    Quote Originally Posted by OReubens View Post
    The problem with using std::array for this...
    I can't tell if this is a generic comment, or a direct reply to what I recommended.

    you'll be reserving the size of the array in a modifiable memory segment.
    and you'll have the actual data in a read-only section of memory.
    the read only segment will be copied/assigned into the modifiable one at runtime.
    This makes the assumption that all of your arrays are initialized from string literals, which may not be the case.

    If the array is large, that's not an efficient way to go about it, and could even mean you can't fit it in memory.
    OP stated that it is 3 char elements elements, so their size is compile time known to be small (though there may be many of them)

    You either want a static const raw (c-style) array.
    Or you want a C++ wrapper around one.
    This still assumes that your strings can all known and stored at compile time. Unless you want to dynamically allocate *some* of them and manage their memory cycle.

    If you want to avoid std::array here, I'd just use std::string. Though arguably, string would lead to more allocations and memory use and fragmentation. Though that might be premature optimization

    If memory is really tight, then a shared string, such as boost::const_string could be a good alternative.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  7. #7
    Join Date
    Jun 2015
    Posts
    208

    Re: from static to vector

    Quote Originally Posted by vindieu View Post
    So I need to create dynamic arrays (vectors ?)

    What is the simplest way?
    Here's a simple database. Each record holds a product reference and a variable number of items. The product reference is also the key into the database. It's assumed that the product reference is (or is supposed to be) unique.

    There are two versions of the database, one based on a hash table (unordered_set) and the other on a search tree (set). The first will have O(1) accesses and the other will have O(log N) accesses but with the added benefit of the records being held in sorted (on key) order. It's just to un-comment the wanted version.

    Code:
    #include <vector>
    #include <unordered_set>
    #include <set>
    
    // definitions
    
    using Reference = unsigned int; // the product reference & database key
    
    struct Item { // item with 3 codes and serial number
        char code[3]; // alternatively: char code1, code2, code3; 
        unsigned int serial;
    };
    
    using Items = std::vector<Item>; // variable number of items
    
    struct Record { // the record
        Reference reference;
        Items items; 
    };
    
    struct Hash { // hash function for references
         std::size_t operator() (const Record& r) const {
            return std::hash<Reference>()(r.reference);
        }
    };
    struct Equal { // function defining when two records are considered equal
        bool operator() (const Record& r1, const Record& r2) const {
            return r1.reference == r2.reference;
        }
    };
    struct Less { // function defining when a record is considered less than another
        bool operator() (const Record& r1, const Record& r2) const {
            return r1.reference < r2.reference;
        }
    };
    
    // un-comment wanted version
    using Database = std::unordered_set<Record, Hash, Equal>; // database of records (hash version)
    //using Database = std::set<Record, Less>; // database of records (tree version)
    The database can then be accessed like this,

    Code:
    Database database; // the actual database instance
    
    bool store(const Record& rec) { // store record based on reference (the key)
        bool exists = (database.count(rec) > 0);
        if (exists) database.erase(rec);
        database.insert(rec);
        return exists; // true if record replaced an existing record
    }
    
    bool retrieve(Record& rec) { // retrieve record based on the reference (the key) supplied with the passed in record
        Database::iterator it = database.find(rec);
        bool exists = (it != database.end());
        if (exists) rec = *it;
        return exists; // true if record exists and was returned
    }
    
    bool lookup(Reference ref) { // check whether record with this reference is in database
        static Record rec; 
        rec.reference = ref;
        return database.count(rec) > 0; // true if present
    }
    It's not tested but I'll check it out later.
    Last edited by tiliavirga; October 30th, 2015 at 05:02 AM.

  8. #8
    Join Date
    Jun 2015
    Posts
    208

    Re: from static to vector

    Here's a small test of the code in my revious post. It seems to work fine,

    Code:
    void test() {
    
    	std::cout << "*** storing" << std::endl;
    
    	{ // storing
    		Record record;
    		Item item;
    
    		record.reference = 16732;
    
    		item.code[0] = 'I';	item.code[1] = '2';	item.code[2] = 'U';  item.serial = 454562;
    		record.items.push_back(item);
    		item.code[0] = 'U';	item.code[1] = '4';	item.code[2] = 'Z';  item.serial = 65465;
    		record.items.push_back(item);
    		item.code[0] = 'M';	item.code[1] = '6';	item.code[2] = 'A';  item.serial = 189456;
    		record.items.push_back(item);
    		item.code[0] = 'Z';	item.code[1] = 'P';	item.code[2] = 'Y';  item.serial = 894461;
    		record.items.push_back(item);
    		record.items.shrink_to_fit(); // remove excess vector capacity
    
    		if (store(record)) std::cout << "overwrote existing record" << std::endl;
    		else std::cout << "added new record" << std::endl;
    		if (store(record)) std::cout << "overwrote existing record" << std::endl; // same again
    		else std::cout << "added new record" << std::endl;
    
    		record.reference = 116840;
    		item.code[0] = 'U';	item.code[1] = 'P';	item.code[2] = '1';  item.serial = 65465;
    		record.items.push_back(item);
    		record.items.shrink_to_fit(); // remove excess vector capacity
    
    		if (store(record)) std::cout << "overwrote existing record" << std::endl;
    		else std::cout << "added new record" << std::endl;
    		if (store(record)) std::cout << "overwrote existing record" << std::endl; // same again
    		else std::cout << "added new record" << std::endl;
    	}
    
    	std::cout << "*** retrieving" << std::endl;
    
    	{ // retrieving
    		Record record;
    
    		record.reference = 0;
    		if (retrieve(record)) std::cout << "read record = " << record.reference << std::endl;
    		else std::cout << "missing record = " << record.reference << std::endl;
    
    		record.reference = 16732;
    		if (retrieve(record)) std::cout << "read record = " << record.reference << std::endl;
    		else std::cout << "missing record = " << record.reference << std::endl;
    
    		std::cout << "*** scan" << std::endl;
    		for (const Record& r : database) { 	// sequential scan of database
    			std::cout << "read record = " << r.reference << std::endl;
    		}
    
    		std::cout << "*** lookup" << std::endl;
    		Reference ref = 0;
    		if (lookup(ref)) std::cout << "existing record = " << ref << std::endl;
    		else std::cout << "missing record = " << ref << std::endl;
    
    		ref = 16732;
    		if (lookup(ref)) std::cout << "existing record = " << ref << std::endl;
    		else std::cout << "missing record = " << ref << std::endl;
    	}
    }
    Last edited by tiliavirga; October 30th, 2015 at 05:04 AM.

  9. #9
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: from static to vector

    Quote Originally Posted by tiliavirga View Post
    Here's a small test of the code in my revious post. It seems to work fine,
    If you like the:

    Quote Originally Posted by tiliavirga View Post
    Also note that std::set (and std::unordered_set) can be used as "maps" too. I often find them simpler to apply.
    Then you should look into boost::multi_index. In particular, when used with a single "ordered"/"hased" index, you get an awesome set/map hybrid, where you can do insertions by "full values", but lookups by keys only. This means you don't have to do none of that "Record record; record.reference = 0; retrieve(record)" bullcrap, but rather, a straight up "lookup(0)".

    Here is a minimal and simplified example:
    Code:
    #include <iostream>
    #include <string>
    
    #include <boost/multi_index_container.hpp>
    #include <boost/multi_index/ordered_index.hpp>
    #include <boost/multi_index/member.hpp>
    
    namespace bmi = boost::multi_index;
    
    struct Record {
        using Reference = unsigned int;
        Reference reference;
    
        using Items = std::string;
        Items items;
    };
    
    std::ostream& operator<<(std::ostream& i_ostream, const Record& record) {
      return i_ostream << "{" << record.reference << ":\"" << record.items << "\"}";
    }
    
    using Database = boost::multi_index_container<
      Record,
      bmi::indexed_by<
        bmi::ordered_unique<bmi::member<Record, Record::Reference, &Record::reference> >
      >
    >;
    
    Database database;
    
    void store(const Record& record) {
    	std::cout << "storing " << record << " ... "
          << (database.insert(record).second
              ? "Success"
              : "Failure")
          << std::endl;
    }
    
    void lookup(Record::Reference reference) {
    	std::cout << "looking up {" << reference << "} ... ";
        auto it = database.find(reference);
        if (it != database.end()) {
          std::cout << "Found! " << *it;
        } else {
          std::cout << "Not found.";
        }
        std::cout << std::endl;
    }
    
    int main() {
      store(Record{1, "vindieu"});
      store(Record{2, "monarch_dodra"});
      store(Record{3, "tiliavirga"});
      store(Record{1, "imposter"});
    
      lookup(1);
      lookup(3);
      lookup(4);
    
      std::cout << "Removing key 2" << std::endl;
      database.erase(2);
      store(Record{2, "OReubens"});
    
    	std::cout << "Iterating on everything (ordered on keys)" << std::endl;
      for (const auto& record : database) {
        std::cout << record << std::endl;
      }
    }
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  10. #10
    Join Date
    Jun 2015
    Posts
    208

    Re: from static to vector

    Quote Originally Posted by monarch_dodra View Post
    Then you should look into boost::multi_index. In particular, when used with a single "ordered"/"hased" index, you get an awesome set/map hybrid, where you can do insertions by "full values", but lookups by keys only. This means you don't have to do none of that "Record record; record.reference = 0; retrieve(record)" bullcrap, but rather, a straight up "lookup(0)".
    I'm not particularly keen on going outside the C++ standard unless the gain is substantial. A little extra bling certainly isn't enougth.

    And in this case I'm not convinced boost::multi_index would bring much. If the OP really wants a lookup function and using a dummy record is considered too "bullcrappy" I suggest he instead switches to an unordered_map/map.

    Besides, the solution I presented is at a very low abstraction level because I thought that would suit the OP best. Normally it would be an implementation detail well hidden, warts and all, behind an "awesome" abstraction layer. The occasional internal use of a dummy record would be x-rated information not visible to sensitive young programmers,
    Code:
    bool lookup(Reference ref) { // check whether record with this reference is in database
        static Record rec; // WARNING: bullcrappy use of dummy record
        rec.reference = ref; // hide well and show to un-awesome adults only !!!
        return database.count(rec) > 0; // true if present
    }
    (lookup function added to my previous posts)

    Personally I would consider boost::multi_index only if I needed multiple indexes and only after having first considered a full-fledged database.
    Last edited by tiliavirga; October 30th, 2015 at 05:09 AM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured