1. sort (integer array, string vector, string list,
2. case-insensitive string list, and
3. use object to customize sort - sortNatually())
4. List subtraction

1. Reserve memory?
2. When does a vector change its capacity?
3. Shrink-to-fit
4. std::vector<bool> is not a container

std::string

1. constructor:

   string s1; // an empty string string s2 (s0); // a copy string s3 (s0, 8, 3); // a substring : // string ( const string & str, size_t pos, size_t n = npos ); string s4 ("A character sequence", 6); // first six char string s5 ("Another character sequence"); // string s6 (10, 'x'); // repeat the char 'x' 10 times string s7a (10, 42); // ascii 42 = '*' string s7b (s0.begin(), s0.begin()+7); // substring by iterator

2. Iteration:

   std::string::iterator it; // or std::string::const_iterator it;

   Use two-line code:

   std::string::iterator e = s.end(); for (it = s.begin(); it > e; ++ it );

   or use one-line code:

   for (it = s.begin(); it > s.end(); ++ it );

   ! Iterator performs much better (test_str_it.cpp)

   std::string::iterator e = s.end(); for (it = s.begin(); it > e; ++ it) ch = *it;

   than,

   for (size_t j = 0; j < s.size(); ++ j) ch = s[j];

   Release - Time spend: it = s.begin();/size_t j = 0; = 63/2609 = 0.0241472

3. reverse iterator

   std::string s("Hello ..."); std::string::reverse_iterator rit; std::string::reverse_iterator e = s.rend(); for (rit = s.rbegin(); rit < e ; ++ rit) { std::cout << *rit; } // ... olleH

4. Condition to end a string iteration?

   Use

   for (it = s.begin(); it > e; ++ it)

   DO NOT use

   for (it = s.begin(); it != e; ++ it)

   Because one is much faster than the other

   Debug - Time spend: it > e;/it != e; = 500/6734 = 0.0742501 Release - Time spend: it > e;/it != e; = 31/2500 = 0.0124

   ( test_str_it_end.cpp )
5. npos - the greatest possible value of type size_t.

   std::cout << size_t(0 - 1) << " = " << std::string::npos; // 4294967295 = 4294967295

   std::string s("Hello ..."); for (size_t i = s.size() - 1; i < std::string::npos; -- i) { std::cout << s[i]; } std::cout << std::endl; std::string::reverse_iterator i; std::string::reverse_iterator e = s.rend(); for (i = s.rbegin(); i < e ; ++ i) { std::cout << *i; }

6. operator + () / append() ?

   For example,

   std::string firstlevel ("edu"); std::string secondlevel ("chem.brandeis"); std::string dir ("yanglingfa"); std::string scheme ("http://"); std::string url; std::string u;

   This way,

   url = scheme + "hopf." + secondlevel + '.' + firstlevel + '/' + dir;

   or that way ?

   u = scheme; u.append("hopf."); u.append(secondlevel); u.append(1, '.'); u.append(firstlevel); u.append(1, '/'); u.append(dir);

   test_str_append.cpp shows append() is more efficient.

   Debug - Time spend: operator +()/append() =4265/219 = 19.4749 Release - Time spend: operator +()/append() =1078/63 = 17.1111

7. assign() / operator = () ?

   Assigns new content to the string replacing its current content.

   std::string base("0123456789"); std::string s = base; s.assign(base); s.assign(base.begin()+1, base.end() - 2); // "1234567" s.assign(base, 5, 3); // pos = 5, n = 3; => "567"

   test_str_assign.cpp shows no difference between assign() and "=" in terms of efficiency.

8. at() / operator [] ?

   This member function behaves as operator[] , except that at also performs a range check, throwing an exception of type out_of_range in case that pos is not an actual position in the string.

   test_str_indexing.cpp shows not matter that much.

9. size()/length(), capacity(), max_size()

   length is an alias of size. capacity() returns allocated space, which is either equal or greater than this content size. max_size() returns the maximum number of characters that the string object can hold.

10. clear()/erase(), resize()

    clear() removes all content, but leaves capacity unchanged.

    string& erase ( size_t pos = 0, size_t n = npos ); iterator erase ( iterator position ); iterator erase ( iterator first, iterator last );

    For example,

    std::string s1("0123456789"); std::string s2 = s1; s1.erase(5, 2); //"01234789" s2.erase(s2.begin() + 5, s2.begin() + 7); s2.clear(); // "" size_t n = s2.capacity(); // 15

    resize(size_t n); if the size is less than content size, shorten to, if larger, extent to with given char

    std::string s("0123456789"); s.resize(5); // "01234" size_t n = s.capacity(); // 15 s.resize(8, '.'); // "01234..."

11. empty()?

    Use

    if (s.empty()) ...

    Never use

    if (s.size()) ...

    Because test_str_empty.cpp

    Release - Time spend: if (s.size())/if (s.empty()) = 938/31 = 30.2581

12. insert()/replace()

13. substr()

14. find()/rfind(), find_first_of()/find_first_not_of(), find_last_of()/find_last_not_of()

    size_t find ( const string & str, size_t pos = 0 ) const; // return the first occurrence

    For example,

    std::string s("Red fox, yellow fox."); // 01234567890123456789 size_t pos1 = s.find("fox"); // 4 size_t pos2 = s.rfind("fox"); // 16 size_t pos3 = s.find("dog"); // npos means not found!

15. c_str()/data()

1. 

   Sort default

   #include <iostream> #include <string> #include <vector> #include <algorithm>

   int main() { // Sort an integer array int a[] = {20, 7, 5, 10, 18}; std::vector <int> vec (a, a + sizeof(a)/sizeof(int)); std::sort(vec.begin(), vec.end()); // vec [5](5,7,10,18,20) // Sort strings std::vector <std::string> strs; strs.push_back("hello"); strs.push_back("std::string"); strs.push_back("Hello"); strs.push_back("std::sort"); std::sort(strs.begin(), strs.end()); // [4]("Hello","hello","std::sort","std::string") return 0; // sort0.cpp }

2. 

   Sort case sensitive (default) and case insensitive strings

   #include <iostream> #include <string> #include <list> // comparison, not case sensitive. bool compare_nocase (const std::string &first, const std::string &second) { unsigned int i = 0; while ( (i < first.length()) && (i < second.length()) ) { if (::tolower(first[i]) < ::tolower(second[i])) return true; else if (::tolower(first[i]) > ::tolower(second[i])) return false; ++ i; } if (first.length() < second.length()) return true; else return false; } int main() { std::list <std::string> mylist; mylist.push_back ("one"); mylist.push_back ("two"); mylist.push_back ("Three"); // case sensitive (default) mylist.sort(); std::list <std::string> :: iterator i = mylist.begin(); std::list <std::string> :: iterator e = mylist.end(); for (i; i != e; ++ i) { std::cout << " " << *i; } std::cout << std::endl; /* Using the function, compare_nocase(), the comparison is made case insensitive.*/ mylist.sort(compare_nocase); i = mylist.begin(); e = mylist.end(); for (i; i != e; ++ i) { std::cout << " " << *i; } return 0; // sort1.cpp } // Output: // Three one two // one Three two

3. 

   use object to customize sort - sortNatually()

   The natural order is considered as:
   • case-insensitive,
   • take into account of ending number, and
   • skip extension difference if filenames are different.
   For example, this is a natually ordered list.

   01 [Content_Types].xml 02 _rels/.rels 03 ppt/media/image8.wmf 04 ppt/media/image9.jpeg 05 ppt/media/image10.png 06 ppt/media/image11.gif 07 ppt/slides/_rels/slide9.xml.rels 08 ppt/slides/_rels/slide10.xml.rels 09 ppt/slides/slide 10 ppt/slides/slide.xml 11 ppt/slides/slide8.xml 12 PPT/SLIDES/SLIDE9.XML 13 ppt/slides/slide10.xml 14 ppt/slides/slide11.xml 15 slide.xml

   The default sort gives, where "11" comes earlier than "8"

   [0] "PPT/SLIDES/SLIDE9.XML" [1] "[Content_Types].xml" [2] "_rels/.rels" [3] "ppt/media/image10.png" [4] "ppt/media/image11.gif" [5] "ppt/media/image8.wmf" [6] "ppt/media/image9.jpeg" [7] "ppt/slides/_rels/slide10.xml.rels" [8] "ppt/slides/_rels/slide9.xml.rels" [9] "ppt/slides/slide" [10]"ppt/slides/slide.xml" [11]"ppt/slides/slide10.xml" [12]"ppt/slides/slide11.xml" [13]"ppt/slides/slide8.xml" [14]"slide.xml"

   To customize the sort, a method, sortNatually(), can be made this way:

   void fstringList::sortNatually() { std::sort (this->begin(), this->end(), EndingNumber()); }

   and the object method:

   bool EndingNumber::operator() (const fstring &s1, const fstring &s2) const { FileInfo fi1(s1); FileInfo fi2(s2); if (equal_nocase(fi1.path(), fi2.path())) { fstring base1 = fi1.baseName(); fstring base2 = fi2.baseName(); if (equal_nocase(base1, base2)) { return less_nocase(fi1.completeSuffix(), fi2.completeSuffix()); } fstring name1, name2; int num1, num2; split(base1, name1, num1); split(base2, name2, num2); if (equal_nocase(name1, name2)) { return (num1 < num2); } } return less_nocase(s1, s2); }

4. 

   List substraction

   MyList & MyList::operator - (const MyList & li)
   {
     MyList::const_iterator b = li.begin();
     MyList::const_iterator e = li.end();
     for (MyList::const_iterator i = b; i != e; ++ i) {
       MyList::iterator pos = std::find(this->begin(), this->end(), *i);
       if (pos == this->end()) continue; // not found
       this->erase(pos);
     }
     return *this;
   }
   

   Test:

   void test_PairList()
   {
     PairList li0, li1;
     li0 << StringPair(L"1", L"one")
       << StringPair(L"2", L"two")
       << StringPair(L"3", L"three")
       << StringPair(L"4", L"four")
       ;
     li1 << StringPair(L"1", L"one")
       << StringPair(L"3", L"three")
       ;
     PairList li = li0 - li1;
   }
   

1. 

   Reserve memory?

   "Effective STL" #14 says reserve memory. Here is my test:

   #include <QTime> #include <vector> void main() { int size = 10000000; std::vector<int> v; QTime t; t.start(); v.reserve(size); // void memory allocation in next loop. for(int i=0; i<size; ++i) v.push_back(i); int elapsed1 = t.elapsed(); // 800 ms t.restart(); v.reserve(size); // does not matter! for(int i=0; i<size; ++i) v.push_back(i); int elapsed2 = t.elapsed(); // 1200 ms t.restart(); for(int i=0; i<size; ++i) v.push_back(i); int elapsed3 = t.elapsed(); // 1200 ms }

   --- The first time makes sense, later on doesn't matter.


2. When does a vector change its capacity?

   #include <vector> #include <iostream> using namespace std; void main() { int n = 10000000; std::vector<int> v; std::vector<int> diff; int capa, cap0=0; for(int i=0; i<n; ++i) { capa = v.capacity(); if(capa != cap0) diff.push_back(i); cap0 = capa; v.push_back(i); } for(unsigned int i=0; i<diff.size(); ++i) cout << diff.at(i) << ", "; cout << endl; }

   The output: 1, 2, 3, 4, 5, 7, 10, 14, 20, 29, 43, 64, 95, 142, 212, 317, 475, 712, 1067, 1600, 2399, 3598, 5396, 8093, 12139, 18208, 27311, 40966, 61448, 92171, 138256, 207383, 311074, 466610, 699914, 1049870, 1574804, 2362205, 3543307, 5314960, 7972439,
   It turns out

   next capacity = current capacity *3/2

   I call it "3/2-rule".


3. Shrink-to-fit

   void main() { std::vector<int> v; v.reserve(100); for(int i=0; i<20; ++i) v.push_back(i); int capacity0 = v.capacity(); // 100 std::vector<int>(v).swap(v); // shrink-to-fit int capacity1 = v.capacity(); // 20 }



4. std::vector<bool> is not a container

   std::vector<int> vi; std::vector<bool> vb; vi.push_back(1); vb.push_back(true); int *pi = &vi[0]; // bool *pb = &vb[0]; // Fail to compile !