-
October 25th, 2015, 04:44 AM
#1
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
-
October 25th, 2015, 06:48 AM
#2
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.
-
October 25th, 2015, 11:07 AM
#3
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.
-
October 27th, 2015, 09:35 AM
#4
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.
-
October 27th, 2015, 01:42 PM
#5
Re: from static to vector
I agree that this is a job for a database.
-
October 27th, 2015, 02:37 PM
#6
Re: from static to vector
Originally Posted by OReubens
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.
-
October 28th, 2015, 01:07 AM
#7
Re: from static to vector
Originally Posted by vindieu
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.
-
October 28th, 2015, 04:12 AM
#8
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.
-
October 29th, 2015, 08:28 AM
#9
Re: from static to vector
Originally Posted by tiliavirga
Here's a small test of the code in my revious post. It seems to work fine,
If you like the:
Originally Posted by tiliavirga
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.
-
October 29th, 2015, 12:01 PM
#10
Re: from static to vector
Originally Posted by monarch_dodra
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|