std::vector memory allocation/free: always heap@@

https://stackoverflow.com/questions/8036474/when-vectors-are-allocated-do-they-use-memory-on-the-heap-or-the-stack is concise.

  • The vector “shell” can be on stack or heap or static memory, as you wish.
  • The continuous array + the payload objects are always allocated on the heap, so that the vector can grow or deallocate them.

Deallocation is explained in https://stackoverflow.com/questions/13944886/is-stdvector-memory-freed-upon-a-clear

max profit #max subarray sum is similar


/* max profit or biggest drop. one pass
max subarray sum -- is a similar problem, if you visualize the items as price changes
*/
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

template<typename T> void dump(vector<T> const & v){
	copy(v.begin(), v.end(), ostream_iterator<T>(cout, " "));
	cout<<endl;
}
int main(){
    vector<int> v={9,1,3,7,8,1,6,5}; //prices
	dump(v);

	// HighestProfit, LowestPx
	int hp=0, lpx=v[0];
	for (unsigned int i=1; i<v.size();++i){
		int aa=v[i];
		if (aa<lpx){
			lpx=aa;
			continue;
		}
		int profit = aa-lpx;
		if (profit > static_cast<int>(hp)){
			cout<<profit<<" > "<<hp<<endl;
			hp=profit;
		}
	}
	cout<<"ret = "<<hp;
}

combine cheatsheets on cStr+std::string@@

If a coding test requires string operations A1 A2 A3 A4… and B1 B2 B3…, and I know how to do A1 .. on cStr and B1… on std::string, is it practical to rely on 2-way conversion? Will we be able to get the job done?

If possible, then could we save the effort or learning two solutions on every string operation.

It’s more elegant to use only std::string exclusively, but I don’t have the bandwidth…

range-check in c++ vector^raw array

[[safe c++]] points out that static array or dynamic array are both (unfortunately) silent about access beyond their limits. Vector has operator[] and at() —

[[]] says c++ new array type supports .size()…


#include <iostream>
#include <vector>
using namespace std;

int main(){
    vector<int> v;
    v.push_back(15);
    size_t sz = v.size();
    try{
        cout<<v[0]<<" "<<v[sz]<<" <- operator[]: out-of-range treated as non-error!"<<endl;
        cout<<v.at(sz)<<" <- at(): throws:)"<<endl;
    }catch(exception & ex){
        cerr<<"Must catch by ref (what() virtual) " << ex.what()<<endl;
    }
}

cStr checkHasText()

bool checkHasText(char const* c){
    unsigned int const len = strlen(c);
    unsigned int i = 0;
    for (; i <= len – 1; ++i) {
        if (!isspace(c[i]))
            break;
    }
    if (i == len) {
        cout << "all space\n";
        return false;
    } else {
        cout << "has text\n";
        return true;
    }
}

Alternatively, here’s a pointer-arithmetic version, more direct, less readable

bool checkHasText(char const* c){
    for (; *c; ++c)
        if (!isspace(*c))
            break; //better than return true — can check *c
    return *c; //implicitly cast to bool.
//    if (*c) {
//        cout << "has text\n";
//    } else {
//        cout << "all space\n";
//    }
}

basics of 2-D array in C

Array of strings are the least confusing. Matrix-double is also widely used.

A[33][22] is a 2D matrix with 33 rows 22 columns. For element A[3][2] , 3 is the first subscript, i.e. row-number. Row number can go up to 33 – 1.

See http://c-programmingbooks.blogspot.com/2011/11/memory-map-of-2-dimensional-array-in-c.html

Physically,

– The 2D array layout is contiguous — a[0][0] a[0][1]….a[1][0] a[1][1]. I think of it as 33 simple arrays connected end-to-end, each 22 cells

– The array of pointer is 33 pointers.

http://ee.hawaii.edu/~tep/EE160/Book/chap9/section2.1.4.html

Char namesA[count][size]; //size = limit on long names

Char *namesB[count]; //this many strings; this many pointers

string member – char array ^ char ptr

I have no practical experienced on this topic. I seldom see people discussing it. Perhaps many didn’t know the char-array option or dare to try it.

Good use case for char-array — Suppose you know you will have a million instances of the struct, and all of them have an Address string about the same length. Then the char-array is a viable option.

Our /Cast of characters/ — lets say we have a Person struct (or class) with an Address field of a 99-char string.

[[headfirstC]] P286/220 point out (arguably) the most fundamental difference — the entire 99 bytes of char-array is allocated on-site, whereas in the char-ptr design only the 4-byte pointer [1] is stored on-site.

[1] pointer object, not pointer variable or pure-address

When you duplicate the struct, the char-array case is simpler. The char-ptr solution may require strdup(), malloc() and free().

With char-arrayh, you can get redundant copies of the same data.

The char-ptr solution allows 2 instances to share the same string in memory. Looks efficient and neat but could be tricky later on. Might hit dangling pointers.

Now suppose there’s a Resume field of maximum length 10KB. Char array option would waste memory since some Persons (kids and house wives) have an empty string.

Verdict — I feel in many real projects the char-array works fine and is easier to code and maintain.

coding IV – another reason to master c-str

Here’s another reason to invest solid hours to build c-str manipulation skill — strings are the most important object used in interviews, more than integers. Integers have zero operational complexity, but look at the string operational complexity in http://bigblog.tanbin.com/2008/05/c-string-complete-cheat-sheet.html

As written elsewhere on this blog, i still prefer c-str. Some things c-str can do more than std::string[1], but I feel there’s nothing that c-str can’t do, to the extent that BASIC can do everything c++ can. C-str is a complete and proven toolkit. For everyday coding (+ coding tests), I feel the family of c-string functions (about 20) together qualify as a rather complete toolkit, albeit primitive by today’s standard.

[1] some justifications
* many teams don’t like std::string and want a optimized string, invariably based on c-str.
* many legacy code and system calls use C, ruling out std::string.

Nevertheless, std::string does add value in terms of convenience, though the more fundamental feature added by std::string is memory management.

1) convenience – integration with c++ iostreams
2) convenience – integration with STL
3) convenience – c-string as a raw-array has many syntax constraints. std::string helps.