C++ϵͳѧϰ֮¾Å£ºË³ÐòÈÝÆ÷

2018-09-18 06:25:31À´Ô´£º²©¿ÍÔ° ÔĶÁ ()

ÐÂÀÏ¿Í»§´ó»ØÀ¡,ÔÆ·þÎñÆ÷µÍÖÁ5ÕÛ

¡¡¡¡ÔªËØÔÚ˳ÐòÈÝÆ÷ÖеÄ˳ÐòÓëÆä¼ÓÈëÈÝÆ÷ʱµÄλÖÃÏà¶ÔÓ¦¡£¹ØÁªÈÝÆ÷ÖÐÔªËصÄλÖÃÓÉÔªËØÏà¹ØÁªµÄ¹Ø¼ü×ÖÖµ¾ö¶¨¡£ËùÓÐÈÝÆ÷À඼¹²Ïí¹«¹²µÄ½Ó¿Ú£¬²»Í¬ÈÝÆ÷°´²»Í¬·½Ê½¶ÔÆä½øÐÐÀ©Õ¹¡£

¡¡¡¡Ò»¸öÈÝÆ÷¾ÍÊÇһЩÌض¨ÀàÐͶÔÏóµÄ¼¯ºÏ¡£Ë³ÐòÈÝÆ÷Ϊ³ÌÐòÔ±ÌṩÁË¿ØÖÆÔªËØ´æ´¢ºÍ·ÃÎÊ˳ÐòµÄÄÜÁ¦¡£

1. ˳ÐòÈÝÆ÷¸ÅÊö

ÈÝÆ÷µÄÁ½ÖÖÐÔÄÜ£º

  • ÏòÈÝÆ÷ÖÐÌí¼Ó»òɾ³ýÔªËصĴú¼Û
  • ·Ç˳Ðò·ÃÎÊÈÝÆ÷ÖÐÔªËصĴú¼Û

˳ÐòÈÝÆ÷ÀàÐÍ£º

ÈçºÎÈ·¶¨Ê¹ÓÃÄÄÖÖ˳ÐòÈÝÆ÷

NOTE£ºÍ¨³£Çé¿öÏ£¬Ê¹ÓÃvectorÊÇ×îºÃµÄÑ¡Ôñ¡£¸ù¾ÝʹÓõÄÐèÇó¶ÔÈÝÆ÷µÄÄÄÖÖÐÔÄܸü¼Ó¿´ÖØÀ´Ñ¡ÔñºÏÊʵÄÈÝÆ÷¡£

2. ÈÝÆ÷¿â¸ÅÀÀ

 ÈÝÆ÷ÀàÐÍÉϵIJÙ×÷ÓÐÈý¸ö²ã´Î£º

  • ijЩ²Ù×÷ÊÇËùÓÐÈÝÆ÷ÀàÐͶ¼ÌṩµÄ
  • ÁíÍâһЩ²Ù×÷½öÕë¶Ô˳ÐòÈÝÆ÷¡¢¹ØÁªÈÝÆ÷»òÎÞÐòÈÝÆ÷
  • »¹ÓÐһЩ²Ù×÷Ö»ÊÊÓÃÓÚһС²¿·ÖÈÝÆ÷

ÿ¸öÈÝÆ÷¶¼¶¨ÒåÔÚÒ»¸öÍ·ÎļþÖУ¬ÎļþÃûÓëÀàÐÍÃûÏàͬ¡£ÈÝÆ÷¾ù¶¨ÒåΪģ°åÀà¡£

ÒÔÏÂÈÝÆ÷²Ù×÷ÊÇËùÓÐÈÝÆ÷ÀàÐÍËù¹²ÓеIJÙ×÷

2.1 µü´úÆ÷

µü´úÆ÷·¶Î§

Ò»¸öµü´úÆ÷·¶Î§ÓÉÒ»¶Ôµü´úÆ÷±íʾ£¬beginÖ¸ÏòÈÝÆ÷µÄÊ×ÔªËØ£¬endÖ¸ÏòÈÝÆ÷µÄβԪËØÖ®ºóµÄλÖá£

µü´úÆ÷·¶Î§ÊÇÒ»¸ö×ó±ÕºÏÇø¼ä£¬[begin, end)¡£

begin¿ÉÒÔºÍendÖ¸Ïòͬһ¸öλÖ㬵«ÊÇend²»ÄÜÖ¸Ïòbegin֮ǰµÄλÖá£

2.2 ÈÝÆ÷ÀàÐͳÉÔ±

´¦Àíµü´úÆ÷Ö®Í⻹Óз´Ïòµü´úÆ÷£¬¶Ô·´Ïòµü´úÆ÷½øÐÐ++²Ù×÷£¬»áµÃµ½ÉÏÒ»¸öÔªËØ¡£

ͨ¹ývalue_typeµÃµ½ÔªËØÀàÐÍ£¬Í¨¹ýreference»òconst_referenceµÃµ½ÔªËØÀàÐ͵ÄÒ»¸öÒýÓá£

2.3 ±ê×¼¿âarray¾ßÓй̶¨´óС

ÓëÄÚÖÃÊý×éÒ»Ñù£¬arrayµÄ´óСҲÊÇÀàÐ͵ÄÒ»²¿·Ö¡£¶¨Òåarrayʱ£¬³ýÁËÖ¸¶¨ÔªËØÀàÐÍ£¬»¹ÒªÖ¸¶¨ÈÝÆ÷´óС¡£

array<int, 42>  arr;

Æä¹¹Ô캯ÊýºÍÊý×é²î²»¶à£¬Áбí³õʼ»¯Ê±£¬ÁбíÔªËز»Òª³¬¹ýarrayµÄ´óС£¬¿ÉÒÔÉÙ£¬arrayʣϵÄÔªËؾͽøÐÐÖµ³õʼ»¯¡£

array<int, 10> a={1,2,3};

ʣϵÄ7¸öÔªËØÖµ³õʼ»¯Îª0£»

´ËÍ⻹¿ÉÒÔ¶Ôarray½øÐп½±´»ò¶ÔÏó¸³Öµ²Ù×÷£¬µ«ÄÚÖÃÊý×éÊDz»Ö§³ÖµÄ

int a1[3]={0,1,2};
int a2[3]=a1;    //´íÎó
array<int, 3> a3={0,1,2};
array<int, 3> a4=a3;    //ÕýÈ·

 ¿½±´»ò¸³ÖµÒª±£Ö¤ÀàÐÍÏàͬ¡£

2.4 ¸³ÖµºÍswap

×¢ÒâarrayÔÚ³õʼ»¯µÄʱºò¿ÉÒÔ½øÐÐÁбí³õʼ»¯£¬µ«ÊǸ³ÖµµÄʱºò²»Äܽ«Ò»¸ö»¨À¨ºÅÁÐ±í¸³Öµ¸øËü¡£

NOTE£ºarray¸³ÖµµÄʱºò£¬Á½±ßµÄÔËËã¶ÔÏó±ØÐë¾ßÓÐÏàͬµÄÀàÐÍ¡£

array<int, 3> a1 = { 0, 1, 2 };
array<int, 3> a2 = { 0 };
array<int, 3> a3 = { 2, 3, 4 };
a1 = a2;
a3 = { 0 };    //´íÎó

¶Ôa3¸³ÖµµÄʱºò£¬a3µÄÀàÐÍÊÇarray<int,3>£¬¶øÓÒ±ßÊÇÏÈ°Ñ{0}ת»»³ÉÁÙʱ±äÁ¿array<int,1> tmp,È»ºóÔÙ½«tmp¸³Öµ¸øa3£¬ÕâÊÇtmpºÍa3ÀàÐͲ»Ò»Ö¡£

ÓÉÓÚ¿ÉÄÜÒòΪ´óС²»Ò»Öµ¼ÖÂÀàÐͲ»Ò»Ö£¬array²»Ö§³ÖÈÝÆ÷µÄ¸³ÖµÔËËãassign¡£

NOTE£ºassign²Ù×÷½öÊʺÏ˳ÐòÈÝÆ÷

¸³ÖµÔËËã·ûÒªÇó×óÓÒÁ½±ßµÄÔËËã¶ÔÏó¾ßÓÐÏàͬµÄÀàÐÍ£¬½«ÓÒ±ßÔËËã¶ÔÏóËùÓÐÔªËØ¿½±´µ½×ó±ßÔËËã¶ÔÏóÖС£

swap

swap½»»»Á½¸öÏàͬÀàÐÍÈÝÆ÷µÄÄÚÈÝ¡£swap²Ù×÷²¢²»»á½»»»ÔªËر¾Éí£¬ÖªÊ¶½»»»Á½¸öÈÝÆ÷µÄÄÚ²¿Êý¾Ý½á¹¹£¨³ýarrayÍ⣩¡£Õâ¾ÍÒâζ×Å£¬Ö¸ÏòÈÝÆ÷µÄµü´úÆ÷¡¢ÒýÓúÍÖ¸ÕëÔÚswap²Ù×÷Ö®ºó¶¼²»»áʧЧ£¬ÈÔÖ¸Ïòswap²Ù×÷֮ǰµÄÄÇЩԪËØ£¬Ö»ÊÇÕâЩԪËØÊôÓÚ²»Í¬ÈÝÆ÷ÁË¡£

swapÁ½¸öarray»áÕæÕý½»»»ËûÃǵÄÔªËØ¡£

ÓÐÁ½¸ö°æ±¾µÄswap£º³ÉÔ±º¯Êý°æ±¾ÒÔ¼°·Ç³ÉÔ±°æ±¾£¬Í³Ò»Ê¹Ó÷dzÉÔ±°æ±¾µÄswap¡£

2.5 ÈÝÆ÷´óС²Ù×÷

  • size£ºforward_list²»Ö§³Ösize
  • empty
  • max_size

 2.6 ¹ØϵÔËËã·û

ÿ¸öÈÝÆ÷ÀàÐͶ¼Ö§³ÖÏàµÈÔËËã·û£¨=ºÍ£¡=£©£¬³ýÁËÎÞÐòÈÝÆ÷Íⶼ֧³Ö¹ØϵÔËËã·û¡£¹ØϵÔËËã·ûÁ½±ßµÄÔËËã¶ÔÏó±ØÐëÊÇÏàͬÀàÐ͵ÄÈÝÆ÷£¬ÇÒ±ØÐë±£´æÏàͬÀàÐ͵ÄÔªËØ¡£

¹Øϵ±È½Ï¹æÔò£º

¶ÔÔªËؽøÐÐÖð¶Ô±È½Ï¡£´óСÏàͬ¡¢¶ÔÓ¦ÔªËØÏàµÈÔòÏàµÈ£»ÔªËØÏàµÈ£¬´óС²»µÈ£¬Ð¡µÄСÓÚ´óµÄ£»¶¼²»ÏàµÈ£¬Ôò±È½ÏµÚÒ»¸ö²»ÏàµÈµÄÔªËØ¡£

NOTE£ºÖ»Óе±ÈÝÆ÷µÄÔªËض¨ÒåÁËÏàÓ¦µÄ±È½ÏÔËËã·û²Ù×÷ʱ£¬²Å¿ÉÒÔʹÓùØϵÔËËã·û¡£

3. ˳ÐòÈÝÆ÷²Ù×÷

 Ë³ÐòÈÝÆ÷ºÍ¹ØÁªÈÝÆ÷µÄ²»Í¬Ö®´¦ÔÚÓÚÁ½Õß×éÖ¯ÔªËصķ½Ê½¡£ÕâЩ²»Í¬Ö®´¦Ö±½Ó¹Øϵµ½ÁËÔªËØÈçºÎ´æ´¢¡¢·ÃÎÊ¡¢Ìí¼ÓÒÔ¼°É¾³ý¡£½ÓÏÂÀ´µÄ²Ù×÷¶¼ÊÇ˳ÐòÈÝÆ÷Ëù¶ÀÓеIJÙ×÷¡£

3.1 Ïò˳ÐòÈÝÆ÷ÖÐÌí¼ÓÔªËØ

бê×¼ÒýÈëÁËÈý¸öгÉÔ±£ºemplace_front ¡¢emplaceºÍemplace_back£¬ÕâЩ²Ù×÷¹¹Ôì¶ø²»ÊÇ¿½±´ÔªËØ¡£

µ±µ÷ÓÃpush»òinsert³ÉÔ±º¯Êýʱ£¬ÎÒÃǽ«ÔªËØÀàÐ͵ĶÔÏ󴫵ݸøËüÃÇ£¬ÕâЩ¶ÔÏ󱻿½±´µ½ÈÝÆ÷ÖС£¶øµ±ÎÒÃǵ÷ÓÃemplace³ÉÔ±º¯Êýʱ£¬ÔòÊǽ«²ÎÊý´«µÝ¸øÔªËØÀàÐ͵Ĺ¹Ô캯Êý¡£

empalceº¯ÊýµÄ²ÎÊý¸ù¾ÝÔªËØÀàÐͶø±ä»¯£¬²ÎÊý±ØÐëÓëÔªËØÀàÐ͵Ĺ¹Ô캯ÊýÏàÆ¥Åä¡£

c.empalce("978-001",25,15.99);    //ÓÃÈý¸ö²ÎÊýÖ±½Ó¹¹Ôì¶ÔÏó
c.push_back("978-001",25,15.99);    //´íÎó£¬Ã»ÓнÓÊÜÈý¸ö²ÎÊýµÄpush_back°æ±¾
c.push_back(Sales_data("978-001",25,15.99));    //ÕýÈ·

NOTE£ºemplaceº¯ÊýÔÚÈÝÆ÷ÖÐÖ±½Ó¹¹ÔìÔªËØ£¬¶øpush_backÔòÊÇ´´½¨ÁÙʱ¶ÔÏó¡£

3.2 ·ÃÎÊÔªËØ

·ÃÎʳÉÔ±º¯Êý·µ»ØµÄÊÇÒýÓÃ

front¡¢back¡¢Ï±êºÍat£¬Æä·µ»ØµÄ¶¼ÊÇÒýÓá£

Èç¹ûÎÒÃÇʹÓÃauto±äÁ¿À´±£´æÕâЩº¯ÊýµÄ·µ»ØÖµ£¬²¢ÇÒÏ£ÍûʹÓô˱äÁ¿À´¸Ä±äÔªËصÄÖµ£¬±ØÐë¼ÇµÃ½«±äÁ¿¶¨ÒåΪÒýÓÃÀàÐÍ¡£

auto &v=c.back();    //»ñµÃÖ¸Ïò×îºóÒ»¸öÔªËصÄÒýÓÃ
auto v=c.back();    //v²»ÊÇÒ»¸öÒýÓã¬ÊÇc.back()µÄÒ»¸ö¿½±´

 Ï±ê²Ù×÷±ØÐë±£Ö¤ÔÚ·¶Î§ÄÚ²Ù×÷

3.3 ɾ³ýÔªËØ

3.4 ÌØÊâµÄforward_list²Ù×÷

forward_list²¢Î´¶¨Òåinsert¡¢emplaceºÍerase£¬¶øÊǶ¨ÒåÁËÃûΪinsert_after¡¢emplace_afterºÍerase_afterµÄ²Ù×÷¡£

3.5 ¸Ä±äÈÝÆ÷´óС

list<int> ls(10,45);    //10¸öint£¬¶¼ÊÇ45
ls.resize(15);    //½«5¸öֵΪ0µÄÔªËØÌí¼Óµ½lsµÄĩβ
ls.resize(25,-1);    //½«10¸öֵΪ-1µÄÔªËØÌí¼Óµ½lsµÄĩβ
ls.resize(5);    //´Ólsĩβɾ³ý20¸öÔªËØ

 3.6 ÈÝÆ÷²Ù×÷¿ÉÄÜʹµü´úÆ÷ʧЧ

ÓÉÓÚÏòµü´úÆ÷Ìí¼ÓÔªËغʹӵü´úÆ÷ɾ³ýÔªËصĴúÂë¿ÉÄÜ»áʹµü´úÆ÷ʧЧ£¬Òò´Ë±ØÐ뱣֤ÿ´Î¸Ä±äÈÝÆ÷µÄ²Ù×÷Ö®ºó¶¼ÕýÈ·µØÖØж¨Î»µü´úÆ÷¡£

4. vector¶ÔÏóÊÇÈçºÎÔö³¤µÄ

 Ã¿´Î¶¼±Èʵ¼ÊËùÐè¿Õ¼ä¶à·ÖÅäµã¿Õ¼ä£¬¶ø²»ÊÇÿ´Î¶¼°ÑËùÓÐÔªËØÒƶ¯µ½Ð¿ռ䡣

¹ÜÀíÈÝÁ¿µÄ³ÉÔ±º¯Êý

capacityºÍsize

sizeÊÇÖ¸ÒѾ­±£´æµÄÔªËصÄÊýÄ¿£»¶øcapacityÔòÊÇÔÚ²»·ÖÅäеÄÄÚ´æ¿Õ¼äµÄÇ°ÌáÏÂËü×î¶à¿ÉÒÔ±£´æ¶àÉÙÔªËØ¡£

NOTE£ºÖ»Óе±ÆȲ»µÃÒÑʱ²Å¿ÉÒÔ·ÖÅäеÄÄÚ´æ¿Õ¼ä¡£

5. ¶îÍâµÄstring²Ù×÷

 5.1 ¹¹ÔìstringµÄÆäËû·½·¨

string¶¨ÒåµÄÕâЩ¶îÍâ²Ù×÷ҪôÊÇÌṩstringÀàºÍC·ç¸ñ×Ö·ûÊý×éÖ®¼äµÄÏ໥ת»»£¬ÒªÃ´ÊÇÔö¼ÓÁËÔÊÐíÎÒÃÇÓÃϱê´úÌæµü´úÆ÷µÄ°æ±¾¡£

substr²Ù×÷

substr·µ»ØÒ»¸östring£¬ËüÊÇԭʼstringµÄÒ»²¿·Ö»òÈ«²¿µÄ¿½±´£¬¿ÉÒÔ´«µÝ¸øsubstrÒ»¸ö¿ÉÑ¡µÄ¿ªÊ¼Î»ÖúͼÆÊýÖµ¡£

5.2 ¸Ä±ästringµÄÆäËû·½·¨

 

stringÀàÐÍÖ§³Ö˳ÐòÈÝÆ÷µÄ¸³ÖµÔËËã·ûÒÔ¼°assign¡¢insertºÍerase²Ù×÷¡£³ý´ËÖ®Í⣬»¹¶¨ÒåÁ˶îÍâµÄinsertºÍerase°æ±¾¡£

s.insert(s.size(),5,'!');    //ÔÚsĩβ²åÈë5¸ö¸Ð̾ºÅ
s.erase(s.size()-5,5);    //´Ósɾ³ý×îºó5¸ö×Ö·û

const char *cp="Stately, plump Buck";
s.assign(cp,7);    //s=="Stately"
s.insrt(s.size(),cp+7);    //s=="Stately, plump Buck"

string s="some string", s2="some other string";
s.insert(0,s2);    //ÔÚsÖÐλÖÃ0֮ǰ²åÈës2µÄ¿½±´
s.insert(0,s2,0,s2.size());

 5.3 stringËÑË÷²Ù×÷

ËÑË÷ÊÇ´óСдÃô¸ÐµÄ

ÄæÏòËÑË÷

rfind³ÉÔ±º¯ÊýËÑË÷×îºóÒ»¸öÆ¥Å䣬¼´×Ó×Ö·û´®×î¿¿ÓҵijöÏÖλÖá£

5.4 compareº¯Êý

5.5 Êýֵת»»

6. ÈÝÆ÷ÊÊÅäÆ÷

 ³ýÁË˳ÐòÈÝÆ÷Í⣬±ê×¼¿â»¹¶¨ÒåÁËÈý¸ö˳ÐòÈÝÆ÷ÊÊÅäÆ÷£ºstack¡¢queueºÍpriority_queue¡£ÈÝÆ÷¡¢µü´úÆ÷ºÍº¯Êý¶¼ÓÐÊÊÅäÆ÷¡£

±¾ÖÊÉÏ£¬Ò»¸öÊÊÅäÆ÷ÊÇÒ»ÖÖ»úÖÆ£¬ÄÜʹijÖÖÊÂÎïµÄÐÐΪ¿´ÆðÀ´ÏñÁíÒ»ÖÖÊÂÎïÒ»Ñù¡£

Ò»¸öÈÝÆ÷ÊÊÅäÆ÷½ÓÊÜÒ»ÖÖÒÑÓеÄÈÝÆ÷ÀàÐÍ£¬Ê¹ÆäÐÐΪ¿´ÆðÀ´ÏñÒ»ÖÖ²»Í¬µÄÀàÐÍ¡£

 

±êÇ©£º

°æȨÉêÃ÷£º±¾Õ¾ÎÄÕ²¿·Ö×ÔÍøÂ磬ÈçÓÐÇÖȨ£¬ÇëÁªÏµ£ºwest999com@outlook.com
Ìرð×¢Ò⣺±¾Õ¾ËùÓÐתÔØÎÄÕÂÑÔÂÛ²»´ú±í±¾Õ¾¹Ûµã£¬±¾Õ¾ËùÌṩµÄÉãÓ°ÕÕƬ£¬²å»­£¬Éè¼Æ×÷Æ·£¬ÈçÐèʹÓã¬ÇëÓëÔ­×÷ÕßÁªÏµ£¬°æȨ¹éÔ­×÷ÕßËùÓÐ

ÉÏһƪ£ºHDU6312 Game (¶àУµÚ¶þ³¡1004) ¼òµ¥²©ÞÄ

ÏÂһƪ£ºÂå¹ÈP4133 [BJOI2012]×î¶àµÄ·½°¸(¼ÇÒ仯ËÑË÷)