Блог

Есть ли какой-нибудь простой способ найти индексы непустых записей предварительно выделенного вектора?
один из способов — просто перебирать вектор. Но это очень медленно, если память, выделенная для вектора, велика, а количество непустых записей очень мало.
Ниже приведен пример кода. Поскольку у меня есть записи для индексов 5,9,9,15 , теперь задача состоит в том, чтобы идентифицировать indices 5,9,15 из вектора x размера 20 . Пожалуйста, предложите какой-нибудь простой способ или даже лучшую структуру данных, чтобы сделать это, будет полезно.

 #include "stdafx.h"
#include <string>
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char* argv[])
{
    vector <map<int,int>> x(20);
    x[5].insert({ 4,10002 });
    x[9].insert({2,20});
    x[9].insert({ 3, 60 });
    x[15].insert({ 11, 60 });

    return 0;
}
 

Во-первых, я предполагаю, что для нулевой записи вы имеете в виду пустую запись (a map без элементов).

Я не думаю, что возможно убрать стоимость итерации, но ее можно перенести в другие точки программы (инициализация, вставка элемента, …) с точки, где вы хотите идентифицировать эти индексы.

Например, вы можете инкапсулировать два контейнера в классе: предлагаемый вами вектор и a set<size_t> с индексами пустых записей в векторе. Оба должны быть недоступны напрямую вне class ( private ) . Вы должны инициализировать набор со всеми индексами в векторе диапазона (итерация здесь). Вставка новых элементов должна осуществляться через интерфейс класса, чтобы удалить этот индекс из набора. Удаление новых элементов тоже (включая удаление элементов из карты любой записи, чтобы определить, когда она будет пустой). Чтобы определить индексы пустых записей, ну, у вас есть все они в наборе.

Как вы можете видеть, этот подход переносит стоимость итерации с точки, где вы хотите идентифицировать пустые индексы записи, на инициализацию, добавляя сложность (и стоимость) в любое другое место.

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

ОБНОВЛЕНИЕ: приведенный выше подход верен, если проблема заключается в поиске пустых индексов записи. Чтобы решить проблему в вопросе (определить непустые индексы записи), подход будет следующим:

• использование set<size_t> для хранения непустых индексов,
• ничего общего с набором при инициализации.
• при вставке нового элемента вставьте этот индекс в набор
• при удалении элемента из любой карты в векторе проверьте, стала ли карта пустой, чтобы удалить индекс в этом случае
• набор будет содержать индексы непустых записей.