Какой контейнер STL является лучшим для станд.:: вид? (Это даже имеет значение?)
var commnads = 'alias,apt-get,aptitude,aspell,awk,basename,bc,bg,bind,break,builtin,bzip2,cal,case,cat,cd,cfdisk,chattr,chgrp,chmod,chown,chroot,chkconfig,cksum,cmp,comm,command,continue,cp,cron,crontab,csplit,curl,cut,date,dc,dd,ddrescue,declare,df,diff,diff3,dig,dir,dircolors,dirname,dirs,dmesg,du,echo,egrep,eject,enable,env,eval,exec,exit,expect,expand,export,expr,false,fdformat,fdisk,fg,fgrep,file,find,fmt,fold,for,fsck,ftp,function,fuser,gawk,getopts,grep,groupadd,groupdel,groupmod,groups,gzip,hash,head,history,hostname,htop,iconv,id,if,ifconfig,ifdown,ifup,import,install,iostat,ip,jobs,join,kill,killall,less,let,link,ln,local,locate,logname,logout,look,lpc,lpr,lprm,lsattr,lsblk,ls,lsof,lspci,man,mkdir,mkfifo,mkfile,mknod,mktemp,more,most,mount,mtools,mtr,mv,mmv,nc,netstat,nft,nice,nl,nohup,notify-send,nslookup,open,op,passwd,paste,Perf,ping,pgrep,pkill,popd,pr,printenv,printf,ps,pushd,pv,pwd,quota,quotacheck,ram,rar,rcp,read,readonly,rename,return,rev,rm,rmdir,rsync,screen,scp,sdiff,sed,select,seq,set,shift,shopt,shutdown,sleep,slocate,sort,source,split,ss,ssh,stat,strace,su,sudo,sum,suspend,sync,tail,tar,tee,test,time,timeout,times,touch,top,tput,traceroute,trap,tr,true,tsort,tty,type,ulimit,umask,unalias,uname,unexpand,uniq,units,unrar,unset,unshar,until,useradd,userdel,usermod,users,uuencode,uudecode,vi,vmstat,w,wait,watch,wc,whereis,which,while,who,whoami,write,xargs,xdg-open,xz,yes,zip,.,!!,###'.split(',');
if (commands.some(command => text_to_check.startsWith(command + ' ')))
{
//code goes here
}
8 ответов
Я не думаю std::sort работы над списками, поскольку это требует итератора произвольного доступа, который не обеспечивается a list<>. Отметьте это list<> обеспечивает a sort метод, но это является абсолютно отдельным от std::sort.
Выбор контейнера действительно имеет значение. STL std::sort полагается на итераторы к краткому обзору далеко путь данные магазинов товаров для хранения. Это просто использует итераторы, которые Вы обеспечиваете для перемещения элементов. Чем быстрее те итераторы работают с точки зрения доступа и присвоения элемента, тем быстрее std::sort работал бы.
Выбор действительно имеет значение, но предсказание, какой контейнер будет самым эффективным, является очень трудным. Лучший подход должен использовать контейнер, который является самым легким для Вашего рвения с (вероятно, станд.:: вектор), посмотрите, быстра ли сортировка соответственно с тем контейнером, и раз так засуньте wth это. В противном случае сделайте профилирование производительности на своей проблеме сортировки и выберите другой контейнер на основе данных профиля.
Как экс-лектор и экс-тренер, я иногда чувствую себя лично ответственным за общую идею, что связанный список имеет мистические свойства улучшения производительности. Возьмите его от того, кто знает: единственная причина связанный список появляется в таком количестве учебников и учебных руководств, состоит в том, потому что это - covenient для людей, которые записали те книги и учебные руководства, чтобы иметь структуру данных, которая может проиллюстрировать указатели, динамическая память mangement, рекурсия, ища и сортируя все в одном - это не имеет никакого отношения к эффективности.
std::list определенно не хороший (допустимый) выбор для std::sort(), потому что std::sort() требует итераторов произвольного доступа. std::map и друзья также бесполезны, потому что положение элемента не может быть осуществлено; то есть, положение элемента в карте не может быть осуществлено пользователем со вставкой в особое положение или подкачку. Среди стандартных контейнеров мы до std::vector и std::deque.
std::sort() похож на другие стандартные алгоритмы, в которых это только действует путем свопинга значений элементов вокруг (*t = *s). Таким образом, даже если бы список волшебно поддерживал бы O (1), получают доступ к ссылкам, не был бы реорганизован, а скорее их значения были бы подкачаны.
Поскольку std::sort() не изменяет размер контейнера, это не должно иметь никакой разницы в производительности во время выполнения, используете ли Вы std::vector или std::deque. Примитивные массивы должны быть также быстрыми к виду, вероятно, еще быстрее, чем стандартные контейнеры - но я не ожидаю, что различие в скорости будет достаточно значительным для выравнивания по ширине использования их.
Это зависит от типа элемента.
Если Вы просто сохраните указатели (или POD) затем, то вектор будет самым быстрым. Если Вы будете хранить объекты затем, то вид списка будет быстрее, поскольку он подкачает узлы и не физические элементы.
Алгоритм сортировки ничего не знает о Вашем контейнере. Все, о чем это знает, является итераторами произвольного доступа. Таким образом можно отсортировать вещи, которые не находятся даже в контейнере STL. Таким образом, то, как быстро это будет, зависит от итераторов, которые Вы даете ему, и как быстро это должно разыменовать и скопировать то, на что они указывают.
станд.:: вид не будет работать над станд.:: список, так как вид требует итераторов произвольного доступа. Необходимо использовать один из станд.:: виды функции членства списка для того случая. Те функции членства эффективно подкачают вокруг указателей связанного списка вместо того, чтобы копировать элементы.
Вектор.
Всегда используйте вектор в качестве своего значения по умолчанию. Это имеет самые низкие издержки пространства и самый быстрый доступ любого другого контейнера (среди других преимуществ как итераторы расположения и произвольного доступа C-compatible).
Теперь, спросите себя - что еще Вы делающий с Вашим контейнером? Вам нужны сильные гарантии исключения? Список, набор и карта, вероятно, будут более оптимальными вариантами (хотя у них всех есть свои собственные программы сортировки). Необходимо ли регулярно добавлять элементы к передней стороне контейнера? Рассмотрите двухстороннюю очередь. Ваш контейнер должен всегда сортироваться? Набор и карта, вероятно, будут лучшим соответствием.
Наконец, выясните конкретно, что "лучше всего" для Вас, и затем выберите самый соответствующий контейнер и имейте размеры, как он работает для Ваших потребностей.
Это, конечно, имеет значение, просто потому что различные контейнеры имеют различные шаблоны доступа к памяти и т.д., которые могли играть роль.
Однако std::sort не продолжает работать std::list<>::iterators поскольку это не RandomAccessIterators. Кроме того, хотя было бы возможно реализовать специализацию для std::list<> это переставило бы указатели узлов, это будет, вероятно, иметь странные и удивительные семантические последствия - например, если у Вас будет итератор в отсортированном диапазоне в векторе, то его значение изменится после сортировки, которая не была бы верна с этой специализацией.
станд.:: вид требует итераторов произвольного доступа, таким образом, Ваши единственные опции использовать, которые являются вектором или двухсторонней очередью. Это подкачает значения, и в векторе приближения будет, вероятно, работать немного быстрее, чем двухсторонняя очередь, потому что это обычно имеет более простую базовую структуру данных. Различие является, вероятно, очень крайним все же.
Если Вы используете станд.:: список, существует специализация (станд.:: список:: вид), который должен подкачать указатели, а не значения. Однако, потому что это не произвольный доступ, это будет использовать сортировку с объединением вместо quicksort, который будет, вероятно, означать, что сам алгоритм немного медленнее.
Так или иначе я думаю, что ответ обычно является вектором. Если у Вас есть большие классы для каждого элемента, настолько копирующие издержки доминируют над процессом сортировки, список мог бы разбить его. Или альтернативно Вы могли сохранить указатели на них в векторе и предоставить пользовательский предикат для сортировки их соответственно.