I have static arrays. How do I change them to dynamic ?

[vindiou]

Hi Everyone !

I have 3 static 1-dimension arrays, each of them having 200000 elements:

_____d______c____v___
1347764000 13U 452892
1347763500 1TU 482872
1347762830 1MU 459832
... ... ...

I have declared them this way:

const unsigned int max=200000;

static unsigned int  d[max];
static char  c[max][3];
static  int  v[max];

These data have changed. Now, for a single "d", there is a variable number of "c v" pairs (instead of one). Example:

_____d______c____v____c____v____c_____v____c____v_____c____v____c___v
1347764000 13U 454562 1J3 554451 RH9 654146 56Z 150000 1RC 846616 R56 464698
1347763500 1TU 459662 4XH 844641
1347762830 1MU 452877 R4J 654651 8YH 654466 ZE1 150000
...

1) What is the simplest way to dynamically declare this?
2) How can I allocate and assign a value to these new variables elements?
3) How can I read a value of an element which is in the middle?
4) How can I free the memory when I won't use these new arrays?

I'd be grateful if you could give me an example, I'm a beginner.

Thank you!

[48T7M4Gy]

.

[vindiou]

Thank you but I already read these webpages.
I can tell you that, as a beginner, this problem I have that I submitted above isn't easy at all to solve (as I now have 200000 elements variable in size...), so I would appreciate more help if you don't mind. Thanks.

[48T7M4Gy]

.

[vindiou]

Sorry but I'm afraid you didn't fully understand what I wrote.
Let's say it is the 22nd element (remember, I have 200000 elements).

_____d______c____v____c____v____c_____v____c____v_____c____v____c___v
1347764000 13U 454562 1J3 554451 RH9 654146 56Z 150000 1RC 846616 R56 464698
1347763500 1TU 459662 4XH 844641
1347762830 1MU 452877 R4J 654651 8YH 654466 ZE1 150000

d[22]= 1347764000 with
#1 c[22][0]='1', c[22][1]='3', c[22][2]='U', v[22]=454562
#2 c[22][0]='1', c[22][1]='J', c[22][2]='3', v[22]=554451
#3 c[22][0]='R', c[22][1]='H', c[22][2]='9', v[22]=654146
#4 c[22][0]='5', c[22][1]='6', c[22][2]='Z', v[22]=150000
#5 c[22][0]='1', c[22][1]='R', c[22][2]='C', v[22]=846616
#6 c[22][0]='R', c[22][1]='5', c[22][2]='6', v[22]=464698

d[23]= 1347763500 with
#1 c[23][0]='1', c[23][1]='3', c[23][2]='U', v[23]=454562
#2 c[23][0]='1', c[23][1]='3', c[23][2]='U', v[23]=454562

d[24]= 1347762830 with
#1 c[24][0]='1', c[24][1]='3', c[24][2]='U', v[24]=454562
#2 c[24][0]='1', c[24][1]='J', c[24][2]='3', v[24]=554451
#3 c[24][0]='R', c[24][1]='H', c[24][2]='9', v[24]=654146
#4 c[24][0]='5', c[24][1]='6', c[24][2]='Z', v[24]=150000

How would you change these static elements to dynamic?? C++ declaration?

Thanks!

[48T7M4Gy]

.

[vindiou]

Thank you! I'm going to try to fully understand this new concept and adapt it to my case.

[JLBorges]

#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <iomanip>

using cv_pair = std::pair< std::string, int > ;

struct datum
{
    datum( long long dd = 0 ) : d(dd) {}
    long long d ;
    std::vector<cv_pair> cv ;
};

int main()
{
    std::vector<datum> array = { 1347764000, 1347763500,1347762830 } ;

    array[0].cv = { { "13U", 454562 }, { "1J3", 554451 }, { "RH9", 654146 }, { "56Z", 150000 }, { "R56", 464698 } } ;
    array[1].cv = { { "4XH", 844641 } } ;
    array[2].cv = { { "1MU", 452877 }, { "R4J", 654651 }, { "8YH", 654466 }, { "ZE1", 150000 } } ;

    for( const datum& dat : array )
    {
        std::cout << dat.d << "  " ;
        for( const cv_pair& p : dat.cv ) std::cout << '{' << std::quoted(p.first) << ',' << p.second << "} " ;
        std::cout << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/378d42e86b89e25b

[vindiou]

Thank you very much JLBorges but I'm afraid I haven't been very clear, my fault.

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

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!!!)

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.

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
-------------------------------------------------------------------------------------------------------------------------

[48T7M4Gy]

.

[vindiou]

Please just tell me how to code what I asked, I already know how to retrieve a line item from a file, thank you

[48T7M4Gy]

.

[JLBorges]

> Each product reference can have unlimited item codes (by group of 3 char - no string please!)

Why? Yes, std::string would use more memory, but would also make programming simpler. There is no good reason not to use std::string unless memory is a real constraint.


> serial numbers (unsigned int)

I would recommend representing the serial numbers too as a std::string. It is not entirely unlikely that at some time in the future, the manufacturer may introduce a serial number like '238294-A41' - why should we paint ourselves into a corner?

The memory footprint of this

// inherit from std::pair<> to get convenient utility functions for free
struct item_code_and_number : std::pair<std::string,std::string>
{
    using std::pair<std::string,std::string>::pair ; // inherited constructors
    std::string item_code ;
    std::string serial_number ;
};

would be much, much larger than that of

struct item_code_and_number 
{
    char item_code[3] ;
    unsigned int serial_number ;
};

However, we need to worry about it only if we have memory constraits that would be violated with the simpler, more malleable, future-proof representation.


> 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.
> What is the simplest way?

The simplest, and the recommended way is to use a standard associative container:
std::map<> http://en.cppreference.com/w/cpp/container/map
or std::unordered_map<> http://en.cppreference.com/w/cpp/container/unordered_map
where the key is the product reference and the mapped value is a sequence of item_code/serial_number pairs.
The simplest and most efficient standard sequence container with a dynamic size is std::vector<>

// our lookup table is an associative container with key: product_reference,
// mapped value: sequence of item_code_and_number pairs
using lookup_table = std::map< unsigned long long, std::vector<item_code_and_number> > ;

Adding an entry is simplicity itself:

void add_entry( lookup_table& table, unsigned long long product_ref, std::string item_code, std::string serial_number )
{ table[product_ref].emplace_back( std::move(item_code), std::move(serial_number) ) ; }

Lookup is also simple:

std::vector<item_code_and_number> look_up( const lookup_table& table, unsigned long long product_ref )
{
    const auto iter = table.find(product_ref) ;
    return iter != table.end() ? iter->second : std::vector<item_code_and_number>{} ;
}

Now, let us make an estimate of memory usage:

#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <malloc.h>

// inherit from std::pair<> to get convenient utility functions for free
struct item_code_and_number : std::pair<std::string,std::string>
{
    using std::pair<std::string,std::string>::pair ; // inherited constructors
    std::string item_code ;
    std::string serial_number ;
};

// our lookup table is associative container with key: product_reference,
// mapped value: sequence of item_code_and_number pairs
using lookup_table = std::map< unsigned long long, std::vector<item_code_and_number> > ;

void add_entry( lookup_table& table, unsigned long long product_ref, std::string item_code, std::string serial_number )
{ table[product_ref].emplace_back( std::move(item_code), std::move(serial_number) ) ; }

std::vector<item_code_and_number> look_up( const lookup_table& table, unsigned long long product_ref )
{
    const auto iter = table.find(product_ref) ;
    return iter != table.end() ? iter->second : std::vector<item_code_and_number>{} ;
}

int main()
{
    ::malloc_stats() ;

    // test memory usage with:
    const std::size_t NPRODUCTS = 10'000 ; // ten thousand items
    const std::size_t SAMPLE_SZ = 10 ;
    const std::size_t PAIRS_PER_ITEM[SAMPLE_SZ] = { 1, 5, 10, 20, 30, 34, 100, 200, 250, 350 } ; // hundred items per product on an average
    // these make for one million pairs of strings (10000 * 100 )

    std::size_t total = 0 ;
    for( std::size_t n : PAIRS_PER_ITEM ) total += n ;
    const std::size_t average_entries_per_product = total / SAMPLE_SZ ;
    std::cerr << "-----------------\nsizeof(item_code_and_number): " << sizeof(item_code_and_number) << '\n'
              << "average_entries_per_product: " << average_entries_per_product << "\n------------------\n" ;

    const std::string dummy_item_code = "abc" ;
    const std::string dummy_serial_number = "123456789" ;

    lookup_table table ;
    int n_pairs_added = 0 ;
    for( unsigned long long product_ref = 0 ; product_ref < NPRODUCTS ; ++product_ref )
    {
        for( std::size_t i = 0 ; i < PAIRS_PER_ITEM[product_ref%SAMPLE_SZ] ; ++i )
        {
            add_entry( table, product_ref, dummy_item_code, dummy_serial_number ) ;
            ++n_pairs_added ;
        }
    }

    std::cerr << n_pairs_added << " item_code/serial_number pairs were added\n" ;
    ::malloc_stats() ;
} 

...
sizeof(item_code_and_number): 96
average_entries_per_product: 100
------------------
1000000 item_code/serial_number pairs were added
Total (incl. mmap):
system bytes     =  127242240
in use bytes     =  126244768
...

http://coliru.stacked-crooked.com/a/a2f65958d371fb3e

For one million entries, on a 64-bit architecture, LLVM libc++, the memory used is about 128 MB.

We can quite easily make a back-of-the-envelope estimate of the memory usage:
sizeof(item_code_and_number) == 96
memory for one million such objects == 96 MB
if the vector doubles its capacity when resized (a typical implementation strategy),
adding an amortised overhead of 50% would give us 144 MB.
Add a few MB for the map overhead, and we would get a ball-park figure of 150 MB or so.

It is easy to see that this scales linearly; with six million entries, the memory usage would still be well under one GB.

[vindiou]

Sorry but your answer is much too complicated for me & also much too far from my simple request from Oct 25, 2015 at 12:08am

[48T7M4Gy]

.

[chicofeo]

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

Where did you get that idea from? The people are providing the facts that it does not take that much memory as you claimed.

Sorry but your answer is much too complicated for me & also much too far from my simple request from Oct 25, 2015 at 12:08am

Here is the simple request. Understand the below link:

http://www.cplusplus.com/forum/articles/40071/#msg218019

Please just tell me how to code what I asked, I already know how to retrieve a line item from a file, thank you
Prove what you know. Begin working on your code with the information provided to you. Once you work on your code, post it and be specific on the problems. The reason we do not understand your simple request is because we don't know what you don't know. It will be likely that you will get to your "simple requests" if you provide on what you are working on.

[vindiou]

Sorry I'd like to apologize. Please understand that I'm a beginner.
I worked hard all day to try to understand the program and I finally succeeded! (SEE BELOW)
Thank you VERY MUCH JLBorges!!

The only problem I have now is that I don't know how to read/access to my codes & serials #s from a reference #
How do I "cout" from a reference # all its corresponding codes & serials #s?
How do I know that a reference # has 31 corresponding codes & serials #s for instance?? none??
How do I affect to variables the fourth code & serial # of a reference # for instance?
Please be simple, Thanks!

#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct code_serial : pair<string,unsigned int>
{
    using pair<string,unsigned int>::pair;
    string code ;
    unsigned int serial ;
};

using lookup_table= map< unsigned int, vector<code_serial> >;

void add_entry( lookup_table& table, unsigned int refer, string code, unsigned int serial )
{
   table[refer].emplace_back( move(code), move(serial) );
}

vector<code_serial> look_up( lookup_table& table, unsigned int refer )
{
      auto iter = table.find(refer) ;
    return iter != table.end() ? iter->second : vector<code_serial>{} ;
}

int main()
{
    lookup_table table;

    unsigned int ref0 = 54646;
          string cod0 = "abc";
    unsigned int ser0 = 123456789;

    add_entry( table, ref0, cod0, ser0 );  // First Item added

    unsigned int ref1 = 54646;
          string cod1 = "def";
    unsigned int ser1 = 23456789;

    add_entry( table, ref1, cod1, ser1 );  // Second Item added

    unsigned int ref2 = 54646;
          string cod2 = "ghi";
    unsigned int ser2 = 3456789;

    add_entry( table, ref2, cod2, ser2 );  // Third Item added

    lookup_table table2;

    look_up( table2, 54646);  // The 3 items are now loaded in my new "table2" but how can I read them?

}

[JLBorges]

#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct code_serial : pair<string,unsigned int>
{
    using pair<string,unsigned int>::pair;

    // **** use the members inherited from pair<string,unsigned int>
    // **** base class member 'first' is the code, 'second' is the serial
    // **** I should have done this in my earlier post. mea culpa, sorry about that

    const string& code() const { return first ; }
    string& code() { return first ; }

    unsigned int serial() const { return second ; }
    unsigned int& serial() { return second ; }
};

using lookup_table= map< unsigned int, vector<code_serial> >;

void add_entry( lookup_table& table, unsigned int refer, string code, unsigned int serial )
{
   table[refer].emplace_back( move(code), /*move(serial)*/ serial ); // move for scalar is same as copy
}

vector<code_serial> look_up( const lookup_table& table, unsigned int refer ) // const added
{
    auto iter = table.find(refer) ;
    return iter != table.end() ? iter->second : vector<code_serial>{} ;
}

bool remove_entry( lookup_table& table, unsigned int refer, string code )
{
    auto iter = table.find(refer) ;
    if( iter != table.end() ) // entry was found
    {
        vector<code_serial>& vec = iter->second ; // get a reference to the entries

        // search for the code in the vector; remove it if found
        for( auto iter_vec = vec.begin() ; iter_vec != vec.end() ; ++iter_vec )
        {
            if( iter_vec->code() == code )
            {
                vec.erase(iter_vec) ; // remove the entry from the vector
                return true ; // found, removed
            }
        }
    }
    return false ; // not found
}

bool update_entry( lookup_table& table, unsigned int refer, string code, unsigned int new_serial )
{
    auto iter = table.find(refer) ;
    if( iter != table.end() ) // entry was found
    {
        // search for the code in the vector; update serial if found
        for( auto& cs : iter->second )
        {
            if( cs.code() == code )
            {
                cs.serial() = new_serial ;
                return true ; // found, updated
            }
        }
    }
    return false ; // not found
}

void print_entries( const lookup_table& table, unsigned int refer, std::ostream& stm = std::cout )
{
    // look up
    auto vec = look_up( table, refer ) ;

    // print results
    if( vec.empty() ) stm << "no entry was found for ref " << refer << '\n' ;

    else
    {
        stm << "ref " << refer << " has " << vec.size() << " entries\n" ;
        for( const code_serial& cs : vec ) stm << '{' << cs.code() << ',' << cs.serial() << "} " ;
        stm << "\n----------------------------\n" ;
    }
}

int main()
{
    lookup_table table;

    unsigned int ref0 = 54646;
          string cod0 = "abc";
    unsigned int ser0 = 123456789;
          string cod1 = "def";
    unsigned int ser1 = 23456789;
          string cod2 = "ghi";
    unsigned int ser2 = 3456789;

    add_entry( table, ref0, cod0, ser0 );  // First Item added
    add_entry( table, ref0, cod1, ser1 );  // Second Item added
    add_entry( table, ref0, cod2, ser2 );  // Third Item added
    add_entry( table, ref0, "jkl", 4567890 );  // fourth Item added

    print_entries( table, ref0 ) ;

    // update entry for code == def
    update_entry( table, ref0, "def", 7777777 ) ;
    print_entries( table, ref0 ) ;

    // remove item with code == def
    remove_entry( table, ref0, "def" ) ;
    print_entries( table, ref0 ) ;

    print_entries( table, 3333333 ) ; // no entry was found
}

http://coliru.stacked-crooked.com/a/eb1b776bb0653e55

[vindiou]

Excellent! Thank you!!!
Everything works perfectly, this forum is the best!

[vindiou]

Hi,
How do I free the table from memory?
Thanks