Во-первых, внедрение собственной структуры данных является полезным упражнением.Вы лучше понимаете, что он делает (поэтому вы можете лучше понять, что делают стандартные контейнеры ).В частности, вы лучше понимаете, почему сложность времени так важна.
Тогда возникает проблема качества реализации.Стандартная реализация может не подойти вам.
Позвольте мне привести пример.Действительно, std::stack реализует стек.Это универсальная реализация.Вы измерили sizeof(std::stack<char>)?Вы сравнивали его с миллионами стеков в среднем по 3,2 элемента с распределением Пуассона ?
Возможно, в вашем случае вы знаете,что у вас есть миллионы стеков char -s (никогда NUL ), и что 99% из них имеют менее 4 элементов.Обладая этими дополнительными знаниями, вы, вероятно, сможете реализовать нечто «лучшее», чем то, что обеспечивает стандартный стек C ++.Так что std::stack<char> будет работать, но с учетом этих дополнительных знаний вы сможете реализовать их по-другому.Вы по-прежнему (для удобства чтения и обслуживания) будете использовать те же методы , что и в std::stack<char> - так что ваш WeirdSmallStackOfChar будет иметь метод push и т. Д. Если (позже в ходе проекта) вы поймете илиэтот большой стек может быть полезен (например, в 1% случаев), вы переопределяете свой стек по-другому (например, если ваша кодовая база вырастет до миллиона строк C ++ и вы понимаете, что у вас довольно часто большие стеки, вы можете «удалить»)ваш WeirdSmallStackOfChar класс и добавьте typedef std::stack<char> WeirdSmallStackOfChar; ....)
Если вам случится узнать, что все ваши стеки имеют менее 4 char -х и что \0в них недопустимо, поэтому представление таких «стеков» в виде поля char w[4], вероятно, является самым разумным подходом.Кодирование выполняется быстро и просто.
Так что, если производительность и объем памяти имеют значение, возможно, вы можете закодировать что-то странное, например
class MyWeirdStackOfChars {
bool small;
union {
std::stack<char>* bigstack;
char smallstack[4];
}
Конечно, это очень неполно.Когда small истинно, ваша реализация использует smallstack.В случае 1%, где оно ложно, ваша реализация использует bigstack.Остальное MyWeirdStackOfChars оставлено читателю в качестве упражнения (не так просто).Не забудьте следовать правилу из пяти .
Хорошо, возможно, приведенный выше пример не убедителен.Но как насчет std::map<int,double>?У вас может быть миллионы из них, и вы можете знать, что 99,5% из них меньше 5. Вы, очевидно, могли бы оптимизировать для этого случая.Весьма вероятно, что представление небольших карт массивом пар int & double более эффективно как с точки зрения памяти, так и с точки зрения процессорного времени.
Иногда вы даже знаете, что all на ваших картах менее 16 записей (и std::map<int,double> не знают этого), и ключ равен never 0. Тогда вы можете представить их по-другому.В этом случае, я предполагаю, что я могу реализовать нечто гораздо более эффективное, чем то, что обеспечивает std::map<int,double> (возможно, из-за эффектов cache , массива из 16 записей с int и double является самым быстрым).
Вот почему любой разработчик должен знать классические алгоритмы (и прочитать Введение в алгоритмы ), даже если во многих случаях онбудет использовать существующие контейнеры.Знайте также о как если бы правило .