Отображение станд.:: отобразитесь на Python
Разъяснить на резерве () ответы: необходимо использовать резерв () в сочетании с push_back (). Таким образом, конструктора по умолчанию не называют для каждого элемента, а скорее конструктора копии. Вы все еще подвергаетесь штрафу установки Вашей структуры на стеке и затем копирования его к вектору. С другой стороны, возможно, что, если Вы используете
vect.push_back(MyStruct(fieldValue1, fieldValue2))
, компилятор создаст новый экземпляр непосредственно в памяти thatbelongs к вектору. Это зависит от того, насколько умный оптимизатор. Необходимо проверить сгенерированный код для обнаружения.
4 ответа
Как вы сказали, вы можете свернуть свою собственную реализацию с помощью bisect:
class OrderedDict:
def __init__(self, keyvalues_iter):
self.__srtlst__ = sorted(keyvalues_iter)
def __len__(self):
return len(self.__srtlst__)
def __contains__(self, key):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
return True
else:
return False
def __getitem__(self, key):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
return self.__srtlst__[index][1]
else:
raise KeyError(key)
def __setitem__(sekf, key, value):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
self.__srtlst__[index][1] = value
else:
self.__srtlst__[index]=(key, value)
def __delitem__(sekf, key, value):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
del __srtlst__[index]
else:
raise KeyError(key)
def __iter__(self):
return (v for k,v in self.__srtlst__)
def clear(self):
self.__srtlst__ = []
def get(self, key, default=None):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
return self.__srtlst__[index][1]
else:
return default
def items(self):
return self.__srtlst__[:]
def iteritems(self):
return iter(self.__srtlst__)
def iterkeys(self):
return (k for k,v in self.__srtlst__)
def itervalues(self):
return (v for k,v in self.__srtlst__)
def keys(self):
return [k for k,v in self.__srtlst__]
def values(self):
return [v for k,v in self.__srtlst__]
def setdefault(self, key, default):
index = bisect(self.__srtlst__, key)
if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key:
return self.__srtlst__[index][1]
else:
self.__srtlst__[index]=(key, default)
return default
def update(self, other):
#a more efficient implementation could be done merging the sorted lists
for k, v in other.iteritems():
self[k] = v
хммм ... кажется, я уже сделал это для вас, ооо!
Чтобы список оставался отсортированным, вы можете попробовать модуль heapq.
Списки - жалкая замена дереву.
При вставке необходимо перемещать весь список, чтобы освободить место; при удалении необходимо переместить список вниз. Пакетное добавление или удаление материала - это нормально, когда это возможно, но очень часто это не так или требует неестественных искажений, чтобы упорядочить это. Основным атрибутом дерева является то, что операции вставки и удаления выполняются за O (log n); никакие движения рукой не превратят O (n) в O (log n).
Вставка элемента в дерево, когда вы уже знаете, куда он пойдет, - это O (1). Точно так же удаление элемента из дерева на основе его узла также является O (1). std :: map поддерживает оба из них. Это оба O (n) со списком.
Еще одно фундаментальное свойство дерева состоит в том, что итерация по диапазону значений составляет O (1) за итерацию. Объединение list и dict теряет это, потому что каждая итерация должна выполнять поиск по словарю. (Подход со списком кортежей не имеет этой проблемы.)
Деревья являются одними из самых основных типов данных. Отсутствие в Python типа контейнера дерева - это бородавка. Возможно, существует сторонняя библиотека, реализующая ее (например, та, которую связал мистер «Неизвестный», которую я не пробовал, поэтому не могу поручиться), но для нее нет стандартного типа Python.
У меня была точно такая же потребность, и ответ Алекса Мартелли полностью убедил меня: лучше всего вести словарь и список частично отсортированных ключей, а затем сортировать, когда это необходимо. Это эффективно из-за очень специфического поведения алгоритма сортировки Python (AKA Timsort). Упорядоченный по клавишам dict в Python
Я тестировал его и свою реализацию, и он оказался лучшим (потому что он не вставляет в середину списка)
(я настоятельно рекомендую вам прочитать статью, ссылка на которую приведена в Комментарий AM о тимсорте, жемчужине).