Создание последовательно индексированной упорядоченной карты

В следующем коде показана очень простая, но важная функциональность, которую я хотел бы создать, и в настоящее время я получаю некоторые неприятные ошибки времени выполнения, которые я не смог отладить самостоятельно. Я работал над тем, чтобы написать решение того, что я ищу, и это самое близкое, что я нашел. Мы будем очень признательны за любую помощь в определении исправления или перепроектирования этой реализации!

Это класс. То, что я ищу, - это карта, которая по-прежнему может выполнять свою функциональность оператора [ключ], но также может повторяться в последовательном порядке по мере добавления элементов. Я пытаюсь сделать это, имея карту для поиска, значение которой является указателем на реальное значение, хранящееся в векторе соответствующих пар.

template <typename t>
class IndexedMap {
 public:
  t& operator [] (string s) {
    bool nu = true;

    for (auto& e : actual) // for each pair
      if  (e.first == s) // if exist
    nu = false; 
    if (nu == true) { // if needs created
      actual.push_back(pair <string, t>()); // create proper pair
      actual.back().first = s; // assign key
      // create copy in map @ same key pointing to actual value
      lookup[s] = &actual.back().second;
    }
    return *lookup[s]; // return reference to value
  }

  typename vector <pair <string, t>>::iterator begin () {
    return actual.begin();
  }

  typename vector <pair <string, t>>::iterator end () {
    return actual.end();
  }

 private:
  vector <pair <string, t>> actual;
  map <string, t*> lookup;
};

Эта реализация "работает" со следующим test.cpp - это означает, что он будет запущен, и я действительно вижу результат, который ищу, но после выхода из test.cpp я получаю несколько сумасшедших ошибок, связанных с вызовом free() и Я не уверен, как это происходит или как это исправить.

test.cpp:

int main () {
  IndexedMap <vector <int>> test;

  test["BILLS"]; test["GAS"]; 
  test["GROCERY"]; test["PETS"]; 
  test["TAKEOUT"]; test["OTHER"];

  int i = 0;
  for (auto e : test) // check order
    cout << e.first << endl;
  for (auto& e : test) // assign 3 unique values to each vector
    for (int f = 0; f < 3; ++f, ++i)
      e.second.push_back(i);
  for (auto e : test) { // display them
    cout << e.first << ":" << endl;
    for (auto f : e.second)
      cout << f << endl;
  }
  vector <int> blank; // test modifying a value
  test["GAS"] = blank;
  for (auto e : test["GAS"])
    cout << e << endl;
  cout << "hopefully empty?" << endl;
}

Я надеюсь, что это не слишком запутанно, как я объяснил или записал это. Заранее благодарим за любую помощь, которая может быть предоставлена.

Всех с Новым годом!


person JosephJerrel    schedule 31.12.2017    source источник
comment
Слишком много неправильного в коде для одного вопроса SO. Вы должны сосредоточить свой вопрос на одной четкой проблеме и опубликовать соответствующий минимально воспроизводимый пример. Кроме того, в комментариях к более раннему вопросу уже было объяснено, почему хранение указателей на элементы вектора не будет работать.   -  person juanchopanza    schedule 31.12.2017
comment
@juanchopanza Я оглянулся назад и на самом деле не смог найти достаточно четкого указания, ПОЧЕМУ указатели не будут работать, и это основная причина, по которой я ищу краткое объяснение этой проблемы. Я думал, что мой вопрос был хорошо ограничен по своему объему ...   -  person JosephJerrel    schedule 31.12.2017
comment
Итак, этот комментарий содержит важную информацию: лучше отображать индексы вектора, потому что указатели легко станут недействительными. Затем вы исследуете векторный указатель или аннулирование итератора.   -  person juanchopanza    schedule 31.12.2017
comment
@JosephJerrel Что касается указателей: stackoverflow.com/questions/46991224/   -  person user0042    schedule 31.12.2017
comment
@juanchopanza Я прекрасно понимаю это расплывчатое объяснение .. Я просто не понимаю, где конкретно происходит аннулирование. Я ни в коем случае не уничтожаю элемент ни одного из контейнеров. Не думайте, что я уже не прилагал особых усилий, чтобы вывести этот ответ в одиночку. Просто ищу помощи. Если вы не хотите ничего давать, то не комментируйте. Это полезнее, чем то, что ты пытаешься заставить меня чувствовать себя плохо из-за того, что я еще не нашла ответ в одиночестве. Я провел весь день, лол.   -  person JosephJerrel    schedule 31.12.2017
comment
@juanchopanza Я очень ценю, что вы очень помогаете моему брату, и я подробно рассмотрю эти ссылки. Второй, с которым я знаком, но посмотрю еще раз, чтобы увидеть, поможет ли что-нибудь. Не могли бы вы просто дать мне простое предложение по исправлению этой проблемы, лол? есть ли безопасная операция проверки, которую я должен выполнить, или, возможно, другой тип указателя? Или, если это просто невозможно сделать, не могли бы вы высказать свое мнение по этому поводу? лол .. потому что альтернативы возврата только значения (копии значения) недостаточно для того, что мне нужно сделать.   -  person JosephJerrel    schedule 31.12.2017
comment
Всего пара советов: попробуйте использовать индексы, как в ответе на ваш предыдущий вопрос. А для поиска используйте функциональные возможности std::map вместо развертывания собственных. std::map.   -  person juanchopanza    schedule 31.12.2017
comment
@juanchopanza ВАУ, у меня действительно есть рабочее решение! Это заняло у меня весь день, и теперь благодаря вашим загадочным советам и неполным предложениям о помощи я пришел к рабочей реализации. LOL, так что спасибо, сэр. Вы подтолкнули меня в правильном направлении, и я понял это, так что без сарказма — искренне ценю это.   -  person JosephJerrel    schedule 31.12.2017


Ответы (2)


Благодаря помощи @juanchopanza я придумал рабочее решение этой проблемы.

Все еще не уверен, где именно и как указатели аннулируются в предыдущей реализации, опубликованной выше, но теперь, используя индексы для определения правильного элемента в векторе, а затем возвращая сам этот элемент, а не указатель на это место, я в безопасности; )

t& operator [] (string s) {
    bool nu = true;

    for (auto& e : actual) // for each pair
      if  (e.first == s) // if exist
        nu = false; 
    if (nu == true) { // if needs created
      actual.push_back(pair <string, t>()); // create proper pair
      actual.back().first = s; // assign key
      lookup[s] = actual.size()-1; // assign proper index in map @ same key 
    }
    return actual[lookup[s]].second; // return reference to value
  }
person JosephJerrel    schedule 31.12.2017
comment
Смотрите мой ответ, почему. - person Surt; 31.12.2017
comment
Вектор требует последовательного размещения своих элементов, поэтому, когда он растет, ему может потребоваться перераспределить свой внутренний массив по другому адресу. Когда это происходит, все указатели на элементы вектора становятся висячими. - person Serge Ballesta; 31.12.2017
comment
@SergeBallesta Я действительно рассматривал это, но поскольку мой вектор рос только до размера 6, и все это было сделано до того, как были сделаны какие-либо вызовы с использованием указателей, я не думал, что перераспределение было причиной аннулирования. - person JosephJerrel; 31.12.2017
comment
Следующий шаг: не делайте свой собственный (неэффективный поиск), а используйте карту, которая у вас уже есть. - person juanchopanza; 31.12.2017

Эта строка выдает ошибку

actual.push_back(pair <string, t>()); // create proper pair

отсюда и беда.

lookup[s] = &actual.back().second; // a pointer to an element in a vector.

Что происходит при изменении размера вектора? для вектора выделяется новый массив, а данные из старого массива копируются в новый массив, а старый массив освобождается. Это делает недействительными указатели на старый массив.

Давайте немного оценим ваше решение, вы перебираете вектор, чтобы увидеть, существует ли s, это O (N), и если найдено, вы все равно делаете lookup на карте O (log N).

И мы хотим использовать фактический индекс вместо указателя, поэтому ваша пара карт должна быть

using mappair = std::pair<std::string,  int>;

Итак, если мы перепишем (непроверенный код)

for (auto& e : actual) // for each pair
  if  (e.first == s) // if exist
    nu = false; 
if (nu == true) { // if needs created
  actual.push_back(pair <string, t>()); // create proper pair
  actual.back().first = s; // assign key
  // create copy in map @ same key pointing to actual value
  lookup[s] = &actual.back().second;
}
return *lookup[s]; // return reference to value

to

auto found = lookup.insert(mappair(s, -1));
if (found.second) { // true if new element
  actual.emplace_back(mappair(s,t());
  found->first.second = actual.size()-1;
}
return *found.first;
person Surt    schedule 31.12.2017
comment
Большое спасибо за эту помощь! Что касается висячих указателей - я учитывал это, но поскольку мой вектор рос только до размера 6, и все это было сделано до того, как были сделаны какие-либо вызовы с использованием указателей, я не думал, что перераспределение было причиной аннулирования. Я предполагал, что это будет иметь место только в том случае, если контейнер продолжит расти. - person JosephJerrel; 31.12.2017
comment
@JosephJerrel, во время добавления 6 элементов он мог вырасти в 6 раз в зависимости от реализации, обычно он увеличивается с коэффициентом sqrt (2), поэтому в вашем случае 1,2,3,5, 7. - person Surt; 31.12.2017